Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может увеличить количество камней в куче в три раза, добавить в кучу один камень, или 3 камня, при этом после каждого хода в куче должно быть нечетное количество камней. Например, пусть в куче было 8 камней. Тогда за один ход можно получить кучу из 9 камней или из 11 камней (увеличить количество камней в три раза нельзя, т.к. после этого хода получится четное количество камней – 24). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Выигрывает тот игрок, после хода которого количество камней в куче становится не менее 51.

В начальный момент в куче было S камней; 1 ≤ S ≤ 50.

19. Известно, что Ваня выиграл своим первым ходом после первого хода Пети. Укажите минимальное значение S, когда такая ситуация возможна.

20. Найдите два наибольших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
− Петя не может выиграть за один ход;

− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

Найденные значения запишите в ответе в порядке возрастания.

21. Определите, сколько существует значений S, при которых Ваня выигрывает своим вторым ходом независимо от ходов Пети.

Для того, чтобы перевести целое число из десятичной в двоичную систему счисления, необходимо разделить его на два, а затем делить на два каждое полученное частное до тех пор, пока не получится единица. Искомое двоичное число записывается как последовательность цифр, равных последнему частному (единице) и всем полученным остаткам, начиная с последнего.

Надо перевести сначала 21 в двоичную, потом 2 в двоичную и потом 2002 в двоичную

Получается вот так:
21 = 10101
2=10
2002 = 11111010010

В итоге:
10101.10.11111010010

Обозначим x1 <> x2 через y1, x3 <> x4 через y2 и т.д. Получим систему

y1 or y2 = 1
y2 or y3 = 1
y3 or y4 = 1
y4 or y5 = 1

Количество наборов y1..y5, удовлетворяющих данным условиям - 13. Набор будет являться решением системы, если в нем нет идущих подряд нулей - тогда в каждой из пар (y1,y2), (y2,y3), (y3,y4), (y4,y5) будет хотя бы одна единица, т.е. все операции or также будут давать единицу. Можно перебрать такие наборы вручную:

11111, 11110, 11101, 11011, 11010, 10111, 10110, 10101,
01111, 01110, 01101, 01011, 01010

Либо воспользоваться формулой F(n) = F(n-1) + F(n-2), F(0) = 1, F(1) = 2; Тогда F(5) = 13. Здесь F(n) - количество последовательностей длины n, где нет двух идущих подряд нулей - их можно разбить на две группы, в одной на первой позиции стоит 1 (их F(n-1), т.к. оставшиеся элементы выбираются в соответствии с тем же правилом), в другой - 0 (их F(n-2), т.к. раз в последовательности нет двух идущих подряд нулей, на второй позиции обязана стоять единица).

Далее каждому значению y соответствуют две пары возможных значений x-ов. Т.е., например, y1 = 1 соответствуют x1 = 1, x2 = 0 и x1 = 0, x2 = 1, а y1 = 0 соответствуют x1 = 0, x2 = 0 и x1 = 1, x2 = 1.

В наборе y1..y5 каждому y соответствует два набора x -> всему набору y соответствует 2^5 = 32 набора x.
Всего 13 наборов y -> 13 * 32 = 416 наборов x.

ответ: 416