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

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

Правила игры

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

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

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

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

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

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

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

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

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

Номер: DC2EDF

1 (4ce0FA)

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

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

Ответ: 29

Решение.
Позицию обозначим (x; y): это числа камней в двух кучах. Цель хода — получить x + y ≥ 133.
За ход к одной из куч прибавляется 4 или её размер умножается на 2. Меняется только одна куча; первый ход делает Петя.
Здесь требуется возможность победы Вани после неудачного хода Пети. Значит, достаточно одной подходящей пары ходов; после первого хода игра ещё должна продолжаться.
Проверим S = 29. Начальная позиция (17; 29).
Петя получает (17; 58), сумма равна 75, что меньше 133.
Ваня отвечает ходом в (17; 116): сумма 133 ≥ 133. Победа наступает именно на первом ходе Вани.
Докажем минимальность. Каждая из четырёх команд не уменьшает число камней; состав любой пары команд также монотонен по S. Достаточно показать, что при предыдущем S никакие два хода не достигают цели.
Пусть S = 28. Для каждого первого хода перечислим суммы после всех четырёх возможных вторых ходов:
Первый ход в (21; 28): 53, 70, 53, 77; максимум 77.
Первый ход в (34; 28): 66, 96, 66, 90; максимум 96.
Первый ход в (17; 32): 53, 66, 53, 81; максимум 81.
Первый ход в (17; 56): 77, 90, 77, 129; максимум 129.
Общий максимум равен 129 меньше 133. При любом меньшем S все эти суммы только уменьшаются, поэтому выиграть вторым общим ходом невозможно.
Проверка: рассмотрены оба выбора кучи и оба вида команды у каждого игрока, то есть все 16 пар ходов; показанная партия достигает границы минимального S.
Ответ: 29.

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

Правила игры

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

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

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