Question

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

Answer 1

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

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

Ответ: Выигрывает первый игрок. Своим первым ходом он должен добавить 2 камня в первую кучу