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

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

Правила игры

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

Игра завершается в тот момент, когда количество камней в куче становится не менее 67.

Победителем считается игрок, сделавший последний ход, т.е. первым получивший кучу, состоящую из 67 или более камней.

В начальный момент в куче было S камней; 1 ≤ S ≤ 66.

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

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

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

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

Номер: 521F94

1 (8E9976)

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

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

Ответ: 22

Решение.
Пусть x — число камней перед ходом. Допустимые действия: прибавить 1, прибавить 4, а также умножить на 3.
Игра завершается сразу после хода, если число камней становится не меньше 67.
Сначала определим позиции, из которых можно выиграть одним ходом. Для прибавления a требуется x + a ≥ T, для умножения — m · x ≥ T.
Наименьшие целые x для разрешённых команд: 66, 63, 23. Поэтому возможность немедленной победы равносильна x ≥ 23.
Петя не должен выигрывать первым ходом, значит S ≤ 22.
Среди его команд есть прибавление 1. После такого хода Ваня обязан иметь немедленную победу: S + 1 ≥ 23, откуда S ≥ 22.
Обе необходимые границы дают единственного кандидата S = 22. Осталось проверить все ходы Пети, а не только прибавление единицы.
Петя: 22 → 23; Ваня: 23 → 69, и игра заканчивается.
Петя: 22 → 26; Ваня: 26 → 78, и игра заканчивается.
Петя: 22 → 66; Ваня: 66 → 67, и игра заканчивается.
Ни один перечисленный первый ход Пети сам не завершает игру. После каждого из них указан допустимый завершающий ответ Вани.
Проверка: список содержит каждую разрешённую команду Пети; Ваня выбирает ответ после того, как видит ход соперника. Получено именно требуемое «при любом ходе», а минимальность или единственность установлена предварительными границами.
Ответ: 22.

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

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

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

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

Правила игры

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

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

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