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

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

Правила игры

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

– убрать из кучи 3 камня;

– убрать из кучи 7 камней;

– уменьшить количество камней в куче в 4 раза (количество камней, полученное при делении, округляется до меньшего).

Например, из кучи в 20 камней за один ход можно получить кучу из 17, 13 или 5 камней.

Игра завершается, когда количество камней в куче становится не более 15. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу из 15 или менее камней. В начальный момент в куче было S камней, S ≥ 16.

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

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

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

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

Номер: B9E723

1 (e53507)

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

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

Ответ: 64

Решение.
Пусть x — число камней перед ходом. Допустимые действия: убрать 3, убрать 7, а также разделить на 4 с округлением вниз.
Игра завершается сразу после хода, если число камней становится не больше 15.
Сначала найдём все позиции, из которых можно закончить игру одним ходом. Для вычитания a условие x − a ≤ T равносильно x ≤ T + a.
Для деления с округлением вниз результат не больше 15 тогда и только тогда, когда x меньше 4 · (15 + 1), то есть x ≤ 63.
Верхние границы для трёх команд: 18, 22, 63. Хотя бы одна команда выигрывает при 16 ≤ x ≤ 63.
Петя не должен выигрывать сразу. Следовательно, S ≥ 64; ни одно меньшее разрешённое S не удовлетворяет условию.
Проверим самое маленькое оставшееся значение S = 64.
Петя: 64 → 61; Ваня: 61 → 15, и игра заканчивается.
Петя: 64 → 57; Ваня: 57 → 14, и игра заканчивается.
Петя: 64 → 16; Ваня: 16 → 13, и игра заканчивается.
Ни один перечисленный первый ход Пети сам не завершает игру. После каждого из них указан допустимый завершающий ответ Вани.
Проверка: список содержит каждую разрешённую команду Пети; Ваня выбирает ответ после того, как видит ход соперника. Получено именно требуемое «при любом ходе», а минимальность или единственность установлена предварительными границами.
Ответ: 64.

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

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

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

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

Правила игры

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

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

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