Задание 21

Для игры, описанной в задании 19, найдите минимальное значение S, при котором одновременно выполняются два условия:
 – у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
 – у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Теория

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

Решение

По условию задания у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, но нет гарантии выигрыша своим первым ходом. Это значит, что если после второго хода Пети количество камней будет 20 ≤ S ≤ 59, Ваня обязательно выиграет своим вторым ходом. Отсюда следует, что Ваня должен после своего первого хода оставить в куче 60 или 61 камень. Если больше, то Петя может пойти S-2 и количество камней будет S≥60. К примеру 61 камень можно получить 5 способами: 63-2, 66-5, 183//3, 184//3 и 185//3. Аналогично и 60: 62-2, 65-5, 180//3, 181//3 и 182//3. Ищем минимальное значение S, поэтому после первого хода Пети (перед первым ходом Вани) оно равно 62. Получить 62 камня в куче после первого хода Пети также можно 5 способами (S-2=62, S-5=62, S//3=62, (S+1)//3 и (S+2)//3). Откуда из всех пяти исходных чисел минимальное 64.

Ответ

64 (Время не более 10 минут)