Два игрока играют в следующую игру. Перед игроками лежит две кучи: в первой куче `5` камней, во второй куче - `S` камней. Игроки по очереди могут за ход провести над одной из куч следующую операцию: добавить `2` камня в кучу или, если количество камней в куче чётно, увеличить количество камней в куче в `2,5` раза. Выиграет игрок, после чьего хода суммарное количество камней в обеих кучах будет не менее `39`.
Укажите все значения `S`, при которых в правильной игре
А) Первый игрок может выиграть первым ходом
Б) Второй игрок может выиграть первым ходом.
В) Первый игрок может выиграть вторым ходом, но не может выиграть первым ходом.
Данный пример очень похож по условию на пример 11, однако здесь возникает проблема в том, что количество куч - две, хоть и задано, что изначально в первой куче `5` камней. Если рассматривать двумерную таблицу позиций, это приведёт к побочному анализу многих позиций, в которых количество камней в первой куче отлично от пяти (в примере 11 таких «лишних» позиций не было). Построение дерева игры также не приведёт к быстрому результату, т. к. начальная позиция неизвестна, и такие деревья нужно будет рисовать при каждом `S`.
В связи с этим проведём предварительный анализ игры, не пользуясь ни таблицей позиций, ни деревом игры.
А) Первый игрок выиграет за ход. Первый игрок не может увеличить количество камней в кучке из `5` камней в `1,5` раза. Следовательно, его возможные ходы – это либо добавление камней к одной из куч, либо увеличение количества камней в второй куче в `2,5` раза. В первом случае суммарное количество камней до увеличения должно равняться `37` или `38` (т. е. во второй куче `32` или `33` камня). Во втором случае: пусть `x` – количество камней во второй куче. Тогда `x` - чётно и `2,5x+5>=40`, откуда `x>=14`. Следовательно, возможное количество камней во второй куче, при котором первый игрок победит за ход - `14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 33` (больше `33` нельзя, т. к. изначальное суммарное количество камней должно быть меньше `39`, чтобы игра имела смысл).
Б) Второй игрок выиграет за ход. Это должны быть позиции, при которых первый игрок не сможет выиграть за ход, а второй игрок – сможет выиграть за ход после любого хода первого игрока. Рассмотрим все возможные ходы первого игрока:
– первый игрок увеличивает количество камней в куче с `S` камнями на `2` (этот ход второй игрок может применить в любой ситуации). Тогда второй выиграет, если после этого `S` станет равно `14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 33` (см. предыдущий пункт, количество камней в первой куче не менялось), т. е. изначально `S` могло быть равно `12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 31`.
Из этих вариантов числа камней `S` только варианты `12,31` соответствуют тому, что первый игрок не может выиграть своим первым ходом. Будем далее рассматривать только `S=12`, `S=31` и проверим оставшиеся возможные ходы первого игрока.
Проверим `S=12:`
– первый игрок увеличивает количество камней в куче с `S` камнями в `2,5` раза, получив `30` камней во второй куче. В таком случае второй игрок сможет выиграть за ход, также увеличив количество камней в этой куче в `2,5` раза.
– первый игрок увеличивает количество камней в куче с `5` камнями в `2,5` раза: невозможный ход.
– первый игрок увеличивает количество камней в первой куче на `2`. Таким образом, в первой куче - `7` камней, во второй - `12`. Однако в данном случае второй игрок не сможет выиграть - ни один из его ходов не приводит к ситуации, когда суммарное количество камней после его хода не менее `39`.
`S=12` не подходит. Проверим `S=31:`
– первый игрок увеличивает количество камней в куче с `S` камнями в `2,5` раза: невозможный ход.
– первый игрок увеличивает количество камней в куче с `5` камнями в `2,5` раза: невозможный ход.
– первый игрок увеличивает количество камней в куче с `5` камнями на `2`. Тогда второй игрок также увеличит количество камней в одной из куч на `2`, получит суммарное количество камней - `39`, и победит!
`S=31` подходит.
В) Первый игрок выиграет вторым ходом. После своего хода он должен прийти в позицию, из которой он (будучи «вторым» игроком), сможет выиграть за ход (т. е. в позицию, соответствующую п. Б).
Если после хода первого игрока количество камней в первой куче останется равным `5`, то мы придём в ситуацию предыдущего пункта (после хода первого игрока, если они поменяются ролями, первому игроку, находящемуся в роли второго игрока, нужно выиграть за оставшийся ход). Ответ пункта Б) гласит, что после хода первого игрока количество камней во второй куче должно стать `31`. Единственная возможная ситуация - `29` камней.
Заметим, что при начальном количестве в `5` камней для первой кучи и `29` камней во второй куче единственно возможные ходы - добавления по `2` камня к одной из куч. При этом никогда чётного количества камней в какой-либо из куч не получится, и применить ход «увеличить в `2,5` раза» также будет невозможно. Поэтому при любых ходах как первого, так и второго игрока, через три хода суммарное количество камней станет `29+5+2+2+2=40`, поэтому игра закончится за три хода победой первого игрока (своим вторым ходом).
Второй случай - если первый игрок в правильной игре своим ходом поменяет количество камней в куче единственно возможным ходом «`+2` камня», при этом после хода первого игрока получится `7` камней в первой куче и `S` - во второй. После этого мы должны для начала полностью повторить анализ, по образцу предыдущего пункта. Рассмотрим следующий ход второго игрока:
– второй игрок увеличивает количество камней в куче с `S` камнями на `2`. Тогда первый выиграет, если после этого `S` станет равно `14, 16, 18, 20, 22, 24, 26, 28, 30, 31 ` `(2,5x+7>=39)`, т. е. изначально `S` могло быть равно `12, 14, 16, 18, 20, 22, 24, 26, 28, 29`.
Из этих вариантов числа камней `S` только варианты `12, 29` соответствуют тому, что второй игрок не может выиграть своим первым ходом. Вариант `S=29` уже был рассмотрен ранее - он подходит. Рассмотрим `S=12` и оставшиеся возможные ходы второго игрока.
– второй игрок увеличивает количество камней в куче с `12` камнями в `2,5` раза. При этом он получит `30` камней во второй куче, и `37` - суммарно в обеих кучах. Любой ход первого игрока приведёт к выигрышу.
– первый игрок увеличивает количество камней в первой куче в `2,5` раза: невозможный ход, т. к. `7` - нечётное число.
– первый игрок увеличивает количество камней в первой куче на `2`. Таким образом, в первой куче - `9` камней, во второй - `12`. В данном случае первый игрок сможет выиграть за ход, увеличив количество камней во второй куче, `12`, в `2,5` раза: `9+30 = 39` камней, ровно столько, сколько и требуется для победы. Любой другой ход первого игрока приведёт к тому, что после этого его соперник увеличит в `2,5` раза кучу из `12` или `14` камней и победит, т. о., этот ход не является ходом первого игрока при правильной игре (см. замечание после данной задачи).
Итак, `S=12` будет подходить под условие «первый игрок всегда выиграет вторым ходом», если первым ходом первый игрок увеличит количество камней в первой куче с `5` до `7`. Заметим, что все остальные ходы первого игрока `(12->14; 12->30)` приведут к тому, что второй игрок увеличит количество камней во второй куче в `2,5` раза и выиграет с суммарным количеством камней `40` и `80`. Следовательно, такие ходы первого игрока не могут быть ходами в правильной игре.