Каждое задание на теорию игр разбивается на три задачи (19, 20, 21). В 19 задаче – один ответ в пустую ячейку, в 20 и в 21 – один или два ответа в одну или две пустые ячейки соответственно Задание 19. Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может а) добавить в кучу один камень; б) добавить в кучу два камня; в) добавить в кучу три камня; г) увеличить количество камней в куче в два раза. Игра завершается в тот момент, когда количество камней в куче превышает 33. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 34 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 33. Найдите значение S, при котором Ваня выигрывает своим первым ходом при любой игре Пети.

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

Начнем с анализа. Поскольку игроки могут добавлять 1, 2, 3 камня, или удваивать количество камней, рассмотрим конечное состояние игры. Игра завершится, когда количество камней в куче превысит 33. Соответственно, если в один из ходов игрок сумеет довести кучу до 34 или больше, он выиграет.

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

Рассмотрим критические позиции:

1. Если на текущем ходу в куче 32 камня, то добавив 2 камня (в итог 34), Ваня выиграет.
2. Если в куче 31 камень, то добавив 3 камня (34), Ваня выиграет.
3. Если в куче 30 камней, добавив 4 камня, (не существует такой возможности), Ваня просто увеличит количество камней, но начнет ситуацию, в которой Петя следующим ходом может довести количество камней до 34, увеличив кучу на 4 или 5 камней.
4. Если в куче 29 камней, то Ваня добавит 3 камня; Петя на следующем ходе может добавить 5, и у Вани не будет возможности ответить на этот ход так, чтобы выиграть.

Следовательно, критическими позициями, откуда Ваня имеет явное преимущество при начале, являются:

• нечетные числа от 1 до 29 (т.е. 1, 3, 5, 7, 9, ..., 29), поскольку любое четное число будет выигрышной позицией для Пети.

Чтобы удостовериться в выигрыше Вани, можно воспользоваться аналитикой обратного хода и просчитать необходимое количество для камней до 34. Однако вывод о том, что количество камней S=33 может быть проигрышным, так как если Пети будет свой ход, он всегда будет иметь возможность завершить игровой круг.

Вывод: Ваня сможет гарантированно победить при S = 31.