Два игрока играют в следующую игру. Перед игроками лежит куча из `S` камней, игроки по очереди могут за ход провести над кучей следующую операцию: добавить `1` или `4` камня в кучу или, если количество камней в куче чётно, увеличить количество камней в куче в `1,5` раза. Выигрывает игрок, после чьего хода в куче будет не менее `31` камня.

Укажите все значения `S`, при которых в правильной игре

А) Первый игрок может выиграть первым ходом.

Б) Второй игрок может выиграть первым ходом.

В) Первый игрок может выиграть вторым ходом, при этом он не может выиграть своим первым ходом.

Г) Найдите хотя бы одно значение `S`, при котором в правильной игре выигрывает второй игрок, при этом он не может выиграть своим первых ходом.

Нарисуем клеточную прямую и отметим знаком «`+`» выигрышные позиции в конце игры - позиции с количеством камней не менее `31`. Далее отметим знаками «`-`» позиции, из которых до указанных можно дойти за `1` ход: это позиция (`30`), из которой можно выиграть ходом «добавить `1` камень», позиции `(30)`, `(29)`, `(28)`, `(27)` из которых выиграть ходом «прибавление `4` камня» и позиции `(22)`, `(24)`, `(26)`, `(28)`, `(30)`, из которых можно выиграть за ход «увеличить кучу с чётным количеством камней в `1,5` раза»[1]. Из некоторых позиций, как видно выше, существует сразу несколько выигрышных ходов, однако это неважно: должен существовать хотя бы один. Чтобы отличать эти отмеченные позиции от всех других, добавим ещё цифру «`1`» к позиции для удобства, получив «`-1`».

Найдя позиции, которые подпадают под условие пункта А), перейдём к пункту Б). Нас интересует не просто дальнейшая расстановка плюсов и минусов в позициях, а ещё и количество ходов до выигрыша. Фраза «второй игрок выиграет первым ходом» означает, что из данных позиций не должно быть ходов ни в какие другие позиции, кроме как в позиции, отмеченные знаком «`-1`», т. е. позиции, из которых второй игрок сможет выиграть за один ход. Такие позиции лучше перебрать следующим образом:

Сначала отметим все пустые позиции знаком «?», из которых существует хотя бы один ход до позиций, уже отмеченных знаком «`-1`». Ходом «добавить один камень» можно за ход попасть в указанное множество из позиций `(25)`, `(23)`, `(21)`; ходом «добавить `4` камня» за ход можно попасть из позиций `(25)`, `(23)`, `(20)`, `(18)`, и ходом «увеличить в `1,5` раза» - из позиций `(16)`, `(18)`, `(20)`.

Теперь для каждой из отмеченных «?» позиций проверим условие, что все допустимые ходы идут в нарисованное множество минусовых позиций.

`(16)`, `(18)`, `(20)` - ход «`+1`» противоречит условию выше;

`(21)` - ход «`+4`» противоречит условию выше;

`(23)`, `(25)` - подходят. Таким образом `(23)`, `(25)` - являются позициями, в которых второй игрок выиграет за один ход. В этих позициях будет стоять знак «`+`» как в позициях, откуда все ходы идут в позиции со знаком «`-1`».

Теперь, перейдём к пункту В). Перед этим сотрём все знаки «?», поскольку в позициях, отличных от `(23)` и `(25)` нам неизвестно, существует ли хотя бы один ход, ведущий в минусовую позицию.

Первый игрок выиграет вторым ходом тогда и только тогда, когда не может выиграть за ход, но может прийти в позицию, из которой он, как второй игрок, выиграет первым ходом. Эти позиции уже найдены - это позиции `(23)` и `(25)`. Таким образом, нас интересуют все позиции, из которых можно за ход дойти до `(23)` и `(25)`. Это позиции `(19)`, `(21)`, `(22)`, `(24)`. Однако из позиций `(22)` и `(24)` в данный момент уже отмечены знаком «`-`», то есть из них можно выиграть за ход, а нас интересуют в данном пункте позиции, где за ход выиграть нельзя. Таким образом, в пункте В). Ответ - позиции `(19)` и `(21)`.

Наконец, в пункте Г) нас интересуют позиции, в которых выиграет второй игрок, т. е. позиции «`+`». Отметим отличие пункта Г) от пункта Б). В пункте Г) нас интересуют позиции, в которых второй игрок выиграет и он не сможет выиграть первым ходом, как бы не ходил его соперник. В пункте Б) же нас интересуют позиции, в которых второй игрок сможет, наоборот, выиграть первым ходом как бы не ходил его соперник. Позиции «`+`», где в зависимости от хода первого игрока второй сможет выиграть как первым своим ходом, так и не первым, нас не интересуют ни в пункте Б), ни в пункте Г).

Для решения пункта Г) просто продолжим заполнять согласно правилам таблицу позиций.

Нас интересует позиция, в которой выиграет второй игрок, то есть позиция «`+`». С другой стороны, нас интересует позиция, из которой второй игрок не сможет выиграть своим первым ходом. Это означает, что первый игрок всеми своими ходами должен ходить в минусовые позиции, но ни одним своим ходом не сможет походить в позиции «`-1`», из которых существует выигрышный ход. Этим свойством будет обладать, например, позиция `(15)` - возможные ходы из неё будут вести в позиции `(16) ` и `(19)`, отмеченные знаком «`-`», а не «`-1`». Это будет наибольшей позицией, обладающей таким свойством - из позиций `(18)` и `(20)`, выигрышных для второго игрока, существует ход первого игрока «`1,5x`», приводящий к позициям `(27)` и `(30)`. Из этих позиций можно выиграть за ход.

А) `(22), (24), (26), (27), (28), (29), (30)`;

Б) `(23), (25)`;

В) `(19), (21)`

Г) Например, `(15)`.

Два игрока играют в следующую игру. Перед игроками лежит две кучи: в первой куче `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`. Следовательно, такие ходы первого игрока не могут быть ходами в правильной игре.

А) `S=14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 33`;

Б) `S=31`;

В) `S=12,29`.