Question

Два игрока, Петя и Ваня, играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 2, а во второй — 3 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди, первый ход делает Петя. Ход состоит в том, что игрок или утраивает число камней в какой-то куче, или добавляет 4 камня в какую-то кучу. Игра завершается в тот момент, когда общее число камней в двух кучах становится не менее 31. Если в момент завершения игры общее число камней в двух кучах не менее 40, то выиграл Петя, в противном случае — Ваня. Кто выигрывает при безошибочной игре обоих игроков? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.

Answer 1

Выигрывает Ваня.

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

Таблица содержит все возможные варианты ходов первого игрока. Из неё видно, что при любом ходе первого игрока у второго имеется ход, приводящий к победе.

Answer 2

Чтобы определить, кто выигрывает при безошибочной игре обоих игроков, можно использовать метод обратной игры или метод назад.

Изначально в первой куче 2 камня, а во второй — 3 камня. Нам нужно добиться общего числа камней не менее 31. При этом, если общее число камней становится не менее 40, то выигрывает Петя.

Используем метод обратной игры:

1. Предположим, что общее число камней достигло 31. В таком случае, у нас осталось еще 9 камней до 40, чтобы выиграть игру.
2. Если было бы 28 камней (31 - 3), то игрок, которому принадлежала бы очередь, смог бы достигнуть 31 на следующем ходу и выиграть.
3. Если было бы 27 камней (31 - 4), то игрок, которому принадлежала бы очередь, мог бы утраивать кучу с 2 камнями до 6, а затем увеличить другую кучу до 21 (6 * 3 + 3) на следующих ходах. Это означает, что игрок, стоящий перед ним, не мог бы предотвратить его выигрыш.
4. Если было бы 24 камня (27 - 3), то игрок, которому принадлежала бы очередь, мог бы утраивать кучу с 2 камнями до 6, а затем увеличить другую кучу до 22 (6 * 3 + 4) на следующих ходах. В таком случае, игрок перед ним не смог бы предотвратить его выигрыш.
5. Если было бы 23 камня (27 - 4), то игрок, которому принадлежала бы очередь, мог бы утраивать кучу с 2 камнями до 6, а затем увеличить другую кучу до 25 (6 * 3 + 7) на следующих ходах. В таком случае, игрок перед ним не смог бы предотвратить его выигрыш.

И так далее...

Можно продолжить анализ, и каждый раз видно, что если общее число камней достигнет 31, то игрок, которому принадлежит очередь, всегда может сделать ход так, чтобы общее число камней стало 23 (6 * 3 + 5), 19 (6 * 3 + 1), 15 (6 * 3 - 3) и т.д. Независимо от того, сколько камней будет на момент его хода, он всегда может добиться, чтобы оставшиеся камни можно было разделить на две кучки 3 и 4, при условии, что общее число камней не достигнет 31.

Таким образом, если общее число камней достигает 31, то игрок, которому принадлежит очередь, всегда может выиграть, удерживая общее число камней в диапазоне от 23 до 30.

Изначально было 5 камней (2 + 3). Таким образом, чтобы добиться числа камней от 23 до 30, игроку, которому принадлежит первый ход (Пете), достаточно увеличить обе кучки на 4, чтобы получить 9 камней (5 + 4), и далее продолжать утраивать кучку с 2 камнями на каждом своем ходе. Это означает, что выигрывает Петя.

Итак, Петя выигрывает при безошибочной игре обоих игроков, и его первый ход должен быть увеличение обеих кучек на 4 камня.

Важно отметить, что этот ответ справедлив только при безошибочной игре обоих игроков. Если бы один из игроков допустил ошибку, то результат партии мог бы быть иным.