ФИПИ · ЕГЭ · все форматы ответа · 2475 заданий
Тип задачи: Игры и выигрышные стратегии.
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может:
добавить в одну из куч (по своему выбору) 3 камня;
увеличить количество камней в одной из куч (по своему выбору) в 2 раза.
Например, пусть в одной куче 20 камней, а в другой 30 камней; такую позицию в игре обозначим (20, 30).
Тогда за один ход можно получить любую из четырёх позиций: (23, 30), (20, 33), (40, 30), (20, 60).
Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда суммарное количество камней в двух кучах становится не менее 135. Победителем считается игрок, сделавший последний ход, то есть первым получивший такую игровую позицию, при которой в двух кучах суммарно
135 камней или больше. В начальный момент в первой куче было 13 камней, во второй куче S камней; 1 ≤ S ≤ 121.
| КЭС: | 2.15 Дискретные игры двух игроков с полной информацией. Построение дерева перебора вариантов, описание стратегии игры в табличной форме. Выигрышные и проигрышные позиции. Выигрышные стратегии |
| Тип ответа: | Краткий ответ |
Ответ: 50
Решение.
Начальная позиция — (13; S), где 1 ≤ S ≤ 121. За ход меняется одна выбранная куча: к ней добавляют 3 камня или увеличивают её в 2 раза. Игра заканчивается, как только сумма двух куч достигает 135 или превышает это число. Петя ходит первым.
Из позиции (a; b) разрешены четыре перехода: (a + 3; b), (a; b + 3), (2a; b), (a; 2b). Порядок куч сохраняем во всех таблицах.
Рассматриваем позицию с точки зрения игрока, которому сейчас ходить. Введём четыре класса позиций. W₁ — можно закончить игру следующим ходом. L₁ — любой разрешённый ход передаёт сопернику позицию W₁, поэтому соперник гарантированно выигрывает своим первым ходом.
Для (a; b) условие W₁ проверяется по получающимся суммам: a + b + 3, 2a + b, a + 2b. Два хода добавления дают одинаковую сумму. Достаточно, чтобы хотя бы одна из этих сумм была не меньше 135.
W₂ — выиграть за один ход нельзя, но есть ход в L₁. После такого хода соперник вынужден передать позицию W₁, и игрок завершает игру своим вторым ходом. Проверка здесь состоит из существования одного подходящего собственного хода и проверки всех ответов противника.
L₂ — позиция не относится к L₁, а каждый разрешённый ход ведёт в W₁ или W₂. Тогда соперник гарантирует победу своим первым либо вторым ходом. Исключение L₁ необходимо: по условию задачи 21 победа первым ходом не должна гарантироваться. Терминальную позицию не относим ни к одному из этих четырёх классов: игра в ней уже закончилась.
Нужные начальные значения S — это позиции L₂, поскольку первым ходит Петя, а указанная в условии стратегия нужна Ване. Проверяем допустимые S по возрастанию и выбираем первое подходящее.
Результат последовательной проверки всех начальных S от 1 до 121 включительно. Для каждого перехода применяем правила выше; для двух куч проверяем и позиции с изменившейся первой кучей.
| Класс начальной позиции | Значения S |
|---|---|
| W₁ | 61–121 |
| L₁ | 60 |
| W₂ | 30, 53–54, 57–59 |
| L₂ | 50–51, 55–56 |
| Не входит в эти четыре класса | 1–29, 31–49, 52 |
Покажем гарантированную стратегию для найденных значений. Каждая строка таблицы — возможное развитие игры; на ходе противника перечислены все допустимые ответы, на ходе победителя выбран один обеспечивающий победу ход. Знак «—» означает, что игра уже закончилась.
При S = 50:
| Начало | Петя, ход 1 | Ваня, ход 1 | Петя, ход 2 | Ваня, ход 2 |
|---|---|---|---|---|
| (13; 50) | (16; 50) | (32; 50) | (35; 50) | (35; 100) |
| (13; 50) | (16; 50) | (32; 50) | (64; 50) | (128; 50) |
| (13; 50) | (16; 50) | (32; 50) | (32; 53) | (32; 106) |
| (13; 50) | (16; 50) | (32; 50) | (32; 100) | (35; 100) |
| (13; 50) | (26; 50) | (26; 53) | (29; 53) | (29; 106) |
| (13; 50) | (26; 50) | (26; 53) | (52; 53) | (104; 53) |
| (13; 50) | (26; 50) | (26; 53) | (26; 56) | (26; 112) |
| (13; 50) | (26; 50) | (26; 53) | (26; 106) | (29; 106) |
| (13; 50) | (13; 53) | (26; 53) | (29; 53) | (29; 106) |
| (13; 50) | (13; 53) | (26; 53) | (52; 53) | (104; 53) |
| (13; 50) | (13; 53) | (26; 53) | (26; 56) | (26; 112) |
| (13; 50) | (13; 53) | (26; 53) | (26; 106) | (29; 106) |
| (13; 50) | (13; 100) | (13; 200) | — | — |
Победу Вани именно первым ходом гарантировать нельзя: Петя может начать переходом в (16; 50). Все возможные ответы Вани из неё: (19; 50), (32; 50), (16; 53), (16; 100). Ни один из них не завершает игру. При этом таблица показывает, как Ваня выигрывает не позднее своего второго хода при любом выборе Пети.
Проверка: все переходы в таблицах разрешены условием, игра нигде не продолжается после достижения порога, а каждая конечная позиция получена ходом нужного игрока. Независимый перебор дерева игры до второго хода каждого игрока подтвердил те же классы для всех проверенных S и все ветви приведённых стратегий.
Следовательно, минимальное подходящее значение S равно 50.
Ответ: 50.
Напишите пожелание к сайту или решению либо сообщите о найденной неточности в задании EGEINFFC92EA.
Сообщение увидит только команда сайта: на странице оно не публикуется.
Комментарии к решению
Комментарии видны всем посетителям сайта.
Комментариев пока нет. Будьте первым.
Чтобы оставить комментарий, войдите или зарегистрируйтесь.