№№ заданий Пояснения Ответы Ключ Добавить инструкцию Критерии
Источник Раздел кодификатора ФИПИ Справка
PDF-версия PDF-версия (вертикальная) PDF-версия (крупный шрифт) PDF-версия (с большим полем) Версия для копирования в MS Word
Задания
Задание 26 № 13556

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

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

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

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

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

Укажите все такие значения и соответствующие ходы Паши.

б) У кого из игроков есть выигрышная стратегия при S = 34; 33; 32?

Опишите выигрышные стратегии для этих случаев.

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

Опишите соответствующие выигрышные стратегии.

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

Решение.

1. а) Паша может выиграть, если S = 35 или S = 12; 13; …; 32. При S = 35 первым ходом нужно добавить в кучу 1 камень, при остальных указанных значениях S нужно утроить количество камней.

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

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

При S = 33 после того, как Паша своим первым ходом добавит один камень, в куче станет 34 камня. В этой позиции ходящий (т. е. Валя) проигрывает (см. выше). Т. е. при S = 33 Паша (игрок, который должен ходить первым) выигрывает. Выигрышная стратегия есть у Паши. Комментарии для экспертов. Скорее всего, решение экзаменуемого будет не столь подробным. Это не является ошибкой. Ученик может, например, нарисовать деревья всех возможных партий для указанных значений S. Другая возможность — (1) указать на то, что при S = 33 и 34 утраивать кучу смысла не имеет, и (2) последовательно сводить случай S = 34 к случаю S = 35, а случай S = 33 — к случаю S = 34.

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

При S = 10 выигрышная стратегия есть у Паши. Ему нужно первым ходом добавить 1 камень и получить кучу из 11 камней. Как показано выше, в этой ситуации выигрышная стратегия есть у игрока, который НЕ должен ходить, т. е. у Паши.

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

Случай S = 10 рассмотрен в п. 2, случай S = 27 рассмотрен в п. 1(а).

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

 

· ·