Шешімі: Стратегия игры при значении S
Для игры, описанной в задании 19, найдите наименьшее значение $S$, при котором одновременно выполняются два условия:
— у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
— у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Шешімін қадамдап көрсету
3 қадамПостроим дерево возможных позиций игры и классифицируем позиции по выигрышной стратегии: выигрышные позиции позволяют игроку завершить игру или перейти в проигрышную позицию соперника.
Проверим значения $S$, начиная с наименьших. Для подходящего значения после любого первого хода Пети у Вани существует продолжение, приводящее к победе первым или вторым ходом.
Одновременно проверяем, что ни один первый ход Вани не гарантирует победу независимо от ответа Пети. Первым значением, для которого выполняются оба условия, является $S = 41$.
Где здесь ошибаются
Выбирать значение, при котором Ваня гарантированно выигрывает уже первым ходом.
Проверять только один ответ Пети, а не все возможные ответы.
Искать первое выигрышное значение без проверки условия о невозможности гарантированной победы первым ходом.