8059B3 — Игры и выигрышные стратегии: ответ и решение

Впишите правильный ответ.

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может:

– добавить в одну из куч (по своему выбору) 4 камня;

– увеличить количество камней в одной из куч (по своему выбору) в 3 раза.

Например, пусть в одной куче 20 камней, а в другой 30 камней; такую позицию в игре обозначим (20, 30). Тогда за один ход можно получить любую из четырёх позиций: (24, 30), (20, 34), (60, 30), (20, 90).

Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда суммарное количество камней в двух кучах становится не менее 154. Победителем считается игрок, сделавший последний ход, то есть первым получивший такую игровую позицию, при которой в двух кучах суммарно 154 камня
или больше. В начальный момент в первой куче 11 камней, во второй куче – S камней; 1 ≤ S ≤ 142.

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.

Известно, что Ваня выиграл своим первым ходом после неудачного хода Пети. Укажите минимальное значение S,
при котором такая ситуация возможна.

СВОЙСТВА ЗАДАНИЯ

КЭС:	2.15 Дискретные игры двух игроков с полной информацией. Построение дерева перебора вариантов, описание стратегии игры в табличной форме. Выигрышные и проигрышные позиции. Выигрышные стратегии
Тип ответа:	Краткий ответ

Номер: 8059B3

Статус задания: НЕ РЕШЕНО Ответить

Решение задания EGEINF8059B3

Ответ: 16

Решение.
Позицию обозначим (x; y): это числа камней в двух кучах. Цель хода — получить x + y ≥ 154.
За ход к одной из куч прибавляется 4 или её размер умножается на 3. Меняется только одна куча; первый ход делает Петя.
Здесь требуется возможность победы Вани после неудачного хода Пети. Значит, достаточно одной подходящей пары ходов; после первого хода игра ещё должна продолжаться.
Проверим S = 16. Начальная позиция (11; 16).
Петя получает (11; 48), сумма равна 59, что меньше 154.
Ваня отвечает ходом в (11; 144): сумма 155 ≥ 154. Победа наступает именно на первом ходе Вани.
Докажем минимальность. Каждая из четырёх команд не уменьшает число камней; состав любой пары команд также монотонен по S. Достаточно показать, что при предыдущем S никакие два хода не достигают цели.
Пусть S = 15. Для каждого первого хода перечислим суммы после всех четырёх возможных вторых ходов:
Первый ход в (15; 15): 34, 60, 34, 60; максимум 60.
Первый ход в (33; 15): 52, 114, 52, 78; максимум 114.
Первый ход в (11; 19): 34, 52, 34, 68; максимум 68.
Первый ход в (11; 45): 60, 78, 60, 146; максимум 146.
Общий максимум равен 146 меньше 154. При любом меньшем S все эти суммы только уменьшаются, поэтому выиграть вторым общим ходом невозможно.
Проверка: рассмотрены оба выбора кучи и оба вида команды у каждого игрока, то есть все 16 пар ходов; показанная партия достигает границы минимального S.
Ответ: 16.

Помочь улучшить сайт

Напишите пожелание к сайту или решению либо сообщите о найденной неточности в задании EGEINF8059B3.

Сообщение увидит только команда сайта: на странице оно не публикуется.

Задание EGEINF8059B3: Игры и выигрышные стратегии

Решение задания EGEINF8059B3

Помочь улучшить сайт

Комментарии к решению