Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней....

Question

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может 1) добавить в кучу три камня или 2) увеличить количество камней в куче в два раза и убрать из кучи 1 камень. Например, имея кучу из 10 камней, за один ход можно получить кучу из 13 или 19 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершится в тот момент, когда количество камней в куче становится не менее 38 камней. Победителем считает игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 38 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 37. 1. При каких S: 1a) Петя выигрывает первым ходом; 1б) Ваня выигрывает первым ходом? 2. Назовите все значения S, при которых Петя может выиграть своим вторым ходом? 3. Назовите все значения S, при которых Ваня выигрывает своим первым или вторым ходом.

Answer 1

1а) Заметим, что для всех S≥5 операция 2) более выгодна, чем 1). Тогда ясно, что для всех S таких, что S∈N, 2S-1≥38 ⇔ S≥20 Петя может использовать операцию 2) и сразу же выиграть. Очевидно, что для остальных S это невозможно.

1б) Ваня выигрывает первым ходом, если к его ходу в куче не меньше 20 камней, причем до хода Пети в куче был меньше 20 камней. Отсюда S+3≥20 ⇔ S≥17. Получаем, что S ∈ [17;19];

2) Очевидно, что Петя выигрывает своим вторым ходом, если выполняются следующие условия: (i) Петя не выиграл первым ходом (⇔S≤19), (ii) Следующим ходом не выиграл Ваня (⇔S≤16). Эти два условия выполняются при S≤16. Ясно также, что при 11≤S≤13 Петя не сможет выиграть вторым ходом: Петя добавляет 3 камня, точно также может поступить Ваня, то есть будет не более 19 камней, чего недостаточно. Если S≤8, то ко второму ходу будет не более 15 камней, а Ваня может добавить всего 3, итого 18, чего опять недостаточно. При S=9 или 10 все работает: ко второму ходу Пети будет не менее 20 камней (Петя может так сделать). S∈[9;10]∪[14;16]

3) Ваня выигрывает своим первым или вторым ходом - это объединение значений, при которых он выигрывает первым ходом и при которых он выигрывает вторым ходом. Первым ходом он выигрывает при S∈[17;19]. Петя не выигрывает своим вторым ходом (и первым) при S∈[11;13]. Поработаем с остальными значениями. Заметим, что, если после первого хода число попадает в область S∈[9;10]∪[14;16] - то это те и только те значения на момент первого хода Вани, при которых он выигрывает вторым ходом. Это неминуемо при 11≤S≤14 - либо Ваня выиграет первым ходом, либо вторым.

Ответ: 1а) 20≤S≤37

           1б) S=17, 18, 19

           2) S=9, 10, 14, 15, 16

           3) S=11, 12, 13, 14, 17, 19