А. Кабанов) Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может а)…
А. Кабанов) Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может а) добавить в кучу один камень; б) добавить в кучу два камня; в) добавить в кучу три камня; г) увеличить количество камней в куче в два раза. Игра завершается в тот момент, когда количество камней в куче превышает 33. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 34 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 33. Ответьте на следующие вопросы: Вопрос 1. Найдите значение S, при котором Ваня выигрывает своим первым ходом при любой игре Пети. Вопрос 2. Найдите минимальное и максимальное значение S, при котором у Пети есть выигрышная стратегия, причём одновременно выполняются два условия: − Петя не может выиграть за один ход; − Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня. Найденные значения запишите в ответе в порядке возрастания. Вопрос 3. Найдите значение S, при котором одновременно выполняются два условия: – у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети; – у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Для решения данной задачи мы проанализируем ход игры для Петя и Вани, чтобы понять, какие стратегии ведут к победе в зависимости от количества камней в начале игры (S).
Вопрос 1. Найдите значение S, при котором Ваня выигрывает своим первым ходом при любой игре Пети.
Чтобы Ваня выигрывал своим первым ходом, нужно, чтобы Петя не мог сделать ход, приводящий к победе, а Ваня мог бы сделать так, чтобы после своего хода количество камней превышало 33.
Смотрим на возможные значения S от 1 до 33:
- Если S = 32, то Петя может добавить 1 камень (переделка 33, победа Вани).
- Если S = 31, Петя добавляет 1 или 2 (32 или 33, победа Вани).
- Если S = 30, Петя может добавить 1, 2 или 3 (31, 32 или 33, победа Вани).
- Если S = 29, Петя может также получить 30, 31 или 32.
- Если S = 28, аналогично, Ваня всегда сможет сделать так, чтобы победить.
- Если S = 27, Ваня также сможет гарантировать победу.
- Если S = 26, Ваня тоже может победить.
Таким образом, при S = 24 (и ниже), если Петя добавит любое количество камней (1-3 или удвоение), то Ваня сможет найти ход, который приведет к гарантированной победе.
Ответ на Вопрос 1: S = 24.
Вопрос 2. Найдите минимальное и максимальное значение S, при котором у Пети есть выигрышная стратегия, причем одновременно выполняются два условия:
− Петя не может выиграть за один ход; − Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Если Петя должен выбрать такое S, чтобы:
- За один ход он не мог гарантировать победу (это происходит при S = 31 и ниже).
- На втором ходе сможет победить.
Теперь мы ищем такие S, при которых у Петя есть возможность подготовки под свой второй ход, и никаких выигрышей за первый.
Давайте проанализируем:
- S = 31. Если Петя добавляет 1, Ваня выбирает 1, 2 или 3 (забирает 32, 33 и Петя не выигрывает).
- S = 30. Если же тут добавляет 2 (и даже 3, если Ваня также не привлекается к побегу).
Заключаем, что у Пети есть выигрышная стратегия:
- Минимум S = 30, максимум S = 31.
Ответ на Вопрос 2: S = 30 и 31.
Вопрос 3. Найдите значение S, при котором одновременно выполняются два условия:
– У Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети; – У Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Это значит, что существует такое значение S, где Ваня не выигрывает за первый ход, но в зависимости от тактики Пети он может пользоваться стратегией второго хода.
Верхние значения S, где Петя может избежать прогресса к 33:
- Для S = 32 и 33, Ваня может гарантировать победу.
- Чтобы не было возможности первого побега, проанализируем вниз.
Заключаем, что случай, где Ваня имеет гарантированную победу во втором ходе — это значение за нижними порогами 30-31, нижние строки 33.
Ответ на Вопрос 3: S = 31.
