"Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну…
"Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Например, пусть в одной куче 10 камней, а в другой 5 камней; такую позицию в игре будем обозначать (10, 5). Тогда за один ход можно получить любую из четырёх позиций: (11, 5), (20, 5), (10, 6), (10, 10). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 217. Победителем считается игрок, сделавший последний ход, т. е. первым получивший такую позицию, при которой в кучах будет 217 или больше камней. В начальный момент в первой куче было семь камней, во второй куче — S камней; 1 ≤ S ≤ 209. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит, описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т. е. не являющиеся выигрышными независимо от игры противника. Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая ситуация возможна. "
Класс, давай разберёмся шаг за шагом и дам подсказку, чтобы ты мог прийти к правильному выводу сам.
Подсказка (плохие и хорошие ходы внятно в одну логику)
- Замечание 1: чтобы Ваня выиграл на своей первой попытке после хода Пети, игра должна завершиться за два хода. То есть после хода Пети сумма камней ещё меньше 217, а уже после хода Вани сумма становится не менее 217.
- Замечание 2: какие ходы Вани могут привести к победе за один ход? Однозначно за один ход он может увеличить одну кучу на 1 или удвоить одну кучу. Чтобы сумма стала >=217 за один ход, удобнее смотриться на вариант удвоения какой-то кучи, потому что прибавить всего 1 в большинстве случаев не хватит.
- Замечание 3: после первого хода Пети вторая куча станет либо S+1 (если Петя добавит камень в вторую кучу), либо 2S (если Петя удвоит вторую кучу). Чтобы Ваня мог выиграть своим ходом за один ход, нужна такая конфигурация, при которой удвоение второй кучи даёт суммарно не менее 217.
- Замечание 4: рассмотрим самый «мощный» ход Пети для второй кучи — удвоение второй кучи. Тогда после первого хода Пети вторая куча равна y = 2S, а сумма после удвоения второй кучи для победы Вани будет 7 + 2y. Чтобы это было >=217, нужно 2y >= 210, то есть y >= 105. Значит 2S >= 105, следовательно S >= 53.
- Замечание 5: проверка минимальности: если S = 52 или меньше, то даже при любом первом ходе Пети вторая куча не достигнет 105 после удвоения или при добавлении 1, и Ваня не сможет выиграть в следующем ходу. Поэтому минимальное S именно 53.
- Пример, чтобы увидеть сработку: возьмём S = 53. Пети удваивает вторую кучу: (7, 106). Сумма 113. Ване достаточно удвоить вторую кучу: (7, 212) и сумма 219 ≥ 217. Значит такая ситуация возможна, и минимальная S не меньше 53.
Если хочешь, могу прогнать ещё один альтернативный путь проверки (например, через вариант, когда Petya добавляет 1 ко второй куче), но с учётом минимальности по условию именно этот путь через удвоение второй кучи даёт наименьшее возможное S, равное 53.
Оцените мой ответ лайком или дизлайком.
