Стратегия игры двух игроков. Минимальное значение S, при котором один из игроков выигрывает

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу два камня или увеличить количество камней в куче в два раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 17 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 25. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 25 или больше камней.
В начальный момент в куче было S камней, 1 ≤ S ≤ 24.
Ответьте на следующие вопросы:
Вопрос 1. Найдите минимальное значение S, при котором Ваня выигрывает своим первым ходом при любой игре Пети.
Вопрос 2. Сколько существует значений S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Вопрос 3. Найдите два значения S, при которых одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Найденные значения запишите в ответе в порядке возрастания.

Вопрос 1. Найдите минимальное значение S, при котором Ваня выигрывает своим первым ходом при любой игре Пети.

Для начала мы должны описать все возможные ситуации.

1. Если   в куче больше или равно 25 камней – это однозначный выигрыш

Назовем ее позиция “0”. Если мы попадем в эту ситуацию, функция game нам вернет 0 (ноль ходов)

Схема:

     0

 выигрыш

2. Если у нас от 13 до 24(это наше исходное h) камней в куче, то мы можем за один ход выиграть, прийти в позицию 0. либо умножив на 2 --(например 13*2=26), либо +1(например 24+1=25) Те фактически совершим один ход для победы. Назовем ее позиция 1(один ход).

Если этим ходом мы приходим в позицию 0(game==0) -программа вернет нам 1

 None –появилось для тех значений(1-12), которые не попали ни для одного if. и соответственно  программа ничего не возвращает, то можно сказать, что если в куче от 1 до 12 камней мы за один ход не можем выиграть, НО если в куче от 13 до 24 камней(1), то Одним из(Any) (либо *2, либо +1)  следующим ходом мы можем выиграть(достигнем >=25 (можно выиграть первым ходом) и последние == 0 это заведомо выигрышные значения кучи >=25(нулевой ход)

Например, для начального значения кучи = 13 мы сначала проверим, выигрышное ли это количество камней >=25(позиция 0) –НЕТ, значит переходим на след.шаг(позиция 1) – вызывается процедура moves, наше h*2 и h+1 -moves  возвращает два значения 26 и 14, эти значения перебираются в цикле for, передаются в нашу рекурсию game и опять начинают сравниваться с >+25, если одна из них(any)(ИЛИ 26 ИЛИ 14) попадет в ситуацию, когда game возвращает 0—ДА (13*2>+25)   , то возвращаем 1(как бы ставим маркер, что из этой кучи камней 13 после первого шага можно выиграть)

Схема:

      1                                              0

Петя(any ИЛИ *2 ИЛИ +1) àвыигрыш

13-24                                      >=25

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

3. Итак, схема ходов(назовем ее позиция 2-два хода)-- Петя ходит первый и своим ЛЮБЫМ(КАЖДЫМ all) ходом находится вне выигрышной позиции(т.е первоначальная куча для Пети от 1-12, именно отсюда ему невозможно выиграть первым ходом, тк он не попадет своим ходом (И*2 И+1)в больше чем 25, те фактически он своим ходом делает кучу от 13 до 24(приходит в нашу позицию 1 game==1),  и затем ходит Ваня, причем один из его ходов (любой any (ИЛИ *2 ИЛИ +1)) сразу же приводит его к победе.:

Схема:

2      1   0

Петя (каждый(all) +1 И *2) Ваня (какой либо/один из (any)+1 или *2)àвыигрыш

?-12      13-24 >=25

Добавим в программу это условие

Ответ 11

Те как бы ставим маркер на то количество камней из которых можно выиграть каким либо  вторым ходом(при любом первом ходе)

Кстати, если бы спрашивалось, Найдите минимальное значение S, при котором Ваня может выиграть(а может и не выиграть)  своим первым(каким либо)  ходом при коком -либо ходе  Пети

Наша схема поменялась бы так

Схема:

2                                             1                                                                              0

Петя (какой либо any) +1или *2) Ваня (какой либо/один из (any)+1или *2)àвыигрыш

                 ?-12                              13-24                                        >=25

В программе бы строчка поменялась на

Здесь заметно что, при куче =7, и первом ходе +1, со второго хода можно не выиграть, если Петя походит +1 = 8, то тут хоть +1, хоть *2, мы не достигнем 25, но если Петя *2=14, то Ваня выиграет только одним из ходов *2=28, а +1 не подходит.

Поэтому надо всегда точно выяснять где у нас ВСЕ(all) ходы, а где один из(any).

Кстати, обращаем внимание,, если вас просят найти значения только для первого хода(позиции кроме 1), все остальные ходы лучше ЗАКОММЕНТИРОВАТЬ, иначе получим неверный результат

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

Как только появляется слово выигрышная стратегия(Петя  просчитывает, что один из его первых (ИЛИ +1 ИЛИ *2) ходов(any) даст ему выигрыш в дальнейшем), это означает,что ПЕТЯ ходит ИЛИ +1 ИЛИ *2(наша позиция 3), потом Ваня(он не достигает выигрыша в ОБОИХ ходах all) (наша позиция 2),  потом Петя(наша позиция 1 – (одним из ходов  выигрывает (наша позиция 0). Иными словами - для ходов ПЕТИ мы должны брать any(какой либо ход приведет к выигрышу),а ВАНЯ должен не дойти до выигрыша при любом своем ходе («независимо от хода Вани»  И +1 И*2(это all))

Схема такая идем как бы снизу вверх по программе, по ходам.

3                         2                                  1                 0 

ПЕТЯ(любой)- ВАНЯ(каждый)—ПЕТЯ(любой)--выигрыш

(ПЕТЯ один из(any)***)(3) à 11-12(2)(КАЖДЫЙ (all) ХОД ВАНЯ+1 и *2)à 13-24(1)(ОДИН ИЗ ходов ПЕТЯи (any)*2или+1)à25 (0)

 

Ответ 3 значения(6.9.10)

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

Выигрышная стратегия всегда означает один из ходов (any)

При любой игре – каждый (все) ход (all)

Тк у «Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом», значит понимаем, что Ваня может выиграть ИЛИ своим первым ходом, ИЛИ своим вторым,

 те у нас выигрыш должен быть при каждом первом ходе ПЕТИ(любой его игре) (all)(позиция 4) (выигрыш Вани ИЛИ в позиции 3 ИЛИ в позиции 1(причем для позиции 2 и 4 проверить чтобы там было all- ПЕТЯ(каждый ход), а в позиции 1 и 3 –any – Ваня (любой ход))

Схема такая идем как бы снизу вверх по программе, по ходам(всегла начинаем с пети, тк по условию он ходит первый).

4------------------------3                     2                                  1                0 

ПЕТЯ(каждый)- ВАНЯ(любой)—ПЕТЯ(каждый)—Ваня(любой)---выигрыш

Или

2                                     1                 0

ПЕТЯ(каждый)—Ваня(любой)---выигрыш

Ответ 7,8