СДАМ ГИА: РЕШУ ЕГЭ
Образовательный портал для подготовки к экзаменам
Информатика
Информатика
Cайты, меню, вход, новости


Задания
Версия для печати и копирования в MS Word
Задания Д26 C3 № 13637

Два игрока, Паша и Валя, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Паша. За один ход игрок может (1) добавить в кучу один камень или (2) увеличить количество камней в куче в два раза или (3) увеличить количество камней в куче в три раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16, 30 или 45 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.

Игра завершается в тот момент, когда количество камней в куче становится не менее 36. Если при этом в куче оказалось не более 60 камней, то победителем считается игрок, сделавший последний ход. В противном случае победителем становится его противник. Например, если в куче было 30 камней и Паша утроит количество камней в куче, то игра закончится и победителем будет Валя. В начальный момент в куче было S камней, 1 ≤ S ≤ 35.

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

Выполните следующие задания.

1. а) При каких значениях числа S Паша может выиграть в один ход? Укажите все такие значения и соответствующие ходы Паши.

б) У кого из игроков есть выигрышная стратегия при S = 31, 32, 33, 34? Опишите выигрышные стратегии для этих случаев.

2. У кого из игроков есть выигрышная стратегия при S = 11? Опишите соответствующие выигрышные стратегии.

3. У кого из игроков есть выигрышная стратегия при S = 10? Постройте дерево всех партий, возможных при этой выигрышной стратегии (в виде рисунка или таблицы). На рёбрах дерева указывайте, кто делает ход, в узлах – количество камней в позиции.

Решение.

1. а) Паша может выиграть первым ходом, если S = 12, 13, …, 30, 35. При S = 35 Паше достаточно добавить в кучу 1 камень, при 18 ≤ S ≤ 30 достаточно увеличить число камней в два раза, при остальных указанных значениях S нужно утроить количество камней. Замечание для проверяющего. При S = 18, 19, 20 Паша может также утроить количество камней в куче. Ученик не обязан упоминать об этом.

б) При S = 34 увеличивать количество камней в куче в два или три раза не имеет смысла, т. к. после такого хода выигрывает противник. Поэтому можно считать, что единственно возможный ход – это добавление в кучу одного камня. После этого в куче станет 35 камней и Валя выиграет, добавив в кучу один камень. Таким образом, при S = 34 выигрышная стратегия есть у Вали. При S = 33 Паша может добавить в кучу один камень и получить кучу из 34 камней. В этой позиции выигрышная стратегия есть у игрока, который не должен делать ход, т.е. у самого Паши. Таким образом, при S = 33 выигрышная стратегия есть у Паши. Аналогично, при S = 32 выигрышная стратегия есть у Вали, а при S = 31 – у Паши.

2. При S = 11 после первого хода Паши в куче будет либо 12 камней, либо 22 камня, либо 33 камня. Во всех этих случаях (см. п. 1) выигрышная стратегия есть у игрока, который должен ходить, теперь это Валя. Таким образом, при S = 11 выигрышная стратегия есть у Вали.

3. При S = 10 выигрышная стратегия есть у Паши. Своим первым ходом Паша может добавить в кучу один камень и получить кучу, в которой 11 камней. В этой позиции выигрышная стратегия есть у игрока, который не должен ходить (см. п.2), то есть у Паши.

В таблице изображено дерево возможных партий при описанной стратегии Паши. Заключительные позиции (в них выигрывает Паша) подчёркнуты. На рисунке это же дерево изображено в графическом виде (оба способа изображения дерева допустимы).

 

Источник: Тренировочная работа по ИНФОРМАТИКЕ 11 класс 12 мая 2017 года Вариант ИН10504