Информатика (Выигрышная стратегия)
Два игрока, Паша и Валя, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Паша. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в три раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16 или 45 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.
Игра завершается в тот момент, когда количество камней в куче становится не менее 33. Если при этом в куче оказалось не более 89 камней, то победителем считается игрок, сделавший последний ход. В противном случае победителем становится его противник. Например, если в куче было 30 камней и Паша утроит количество камней в куче, то игра закончится и победителем будет Валя. В начальный момент в куче было S камней, 1 ≤ S ≤ 32.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит, описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.
Выполните следующие задания.
1. а) При каких значениях числа S Паша может выиграть в один ход?
Укажите все такие значения и соответствующие ходы Паши.
б) У кого из игроков есть выигрышная стратегия при S = 31; 30; 29?
Опишите выигрышные стратегии для этих случаев.
2. У кого из игроков есть выигрышная стратегия при S = 10; 9? Опишите соответствующие выигрышные стратегии.
3. У кого из игроков есть выигрышная стратегия при S = 8? Постройте дерево всех партий, возможных при этой выигрышной стратегии (в виде рисунка или таблицы). На рёбрах дерева указывайте, кто делает ход, в узлах — количество камней в позиции.
Ответ
1. а) Паша может выиграть, если S = 32 или S = 11; 12; …; 29. При S = 32 первым ходом нужно добавить в кучу 1 камень, при остальных указанных значениях S нужно утроить количество камней.
б) При S = 29 Паша выигрывает в один ход, утраивая количество камней (см. п. а). При S = 30 или 31 утраивать количество камней не имеет смысла, так как после такого хода выигрывает противник.
Поэтому можно считать, что единственный возможный ход — это добавление в кучу одного камня.
При S = 31 после такого хода Паши в куче станет 32 камня. В этой позиции ходящий (т. е. Валя) выигрывает (см. п. а)), т. е. при S = 31 Паша (игрок, который должен ходить первым) проигрывает.
Выигрышная стратегия есть у Вали.
При S = 30, после того как Паша своим первым ходом добавит один камень, в куче станет 31 камень. В этой позиции ходящий (т. е. Валя) проигрывает (см. выше). Т. е., при S = 30 Паша (игрок, который должен ходить первым) выигрывает. Выигрышная стратегия есть у Паши.
Комментарии для экспертов. Скорее всего, решение экзаменуемого будет не столь подробным. Это не является ошибкой. Ученик может, например, нарисовать деревья всех возможных партий для указанных значений S. Другая возможность — (1) указать на то, что при S = 30 и 31 утраивать кучу смысла не имеет, и (2) последовательно сводить случай S = 31 к случаю S = 32, а случай S = 30 — к случаю S = 31.
2. При S = 10 после первого хода Паши в куче будет либо 11, либо 30 камней. В обоих случаях выигрышная стратегия есть у игрока, который должен ходить, теперь это Валя. Случай S = 11 рассмотрен в задании 1(а), а случай S = 30 — в задании 1(б). Поэтому выигрышная стратегия есть у Вали. При S = 9 выигрышная стратегия есть у Паши. Ему нужно первым ходом добавить 1 камень и получить кучу из 10 камней. Как показано выше, в этой ситуации выигрышная стратегия есть у игрока, который НЕ должен ходить, т. е. у Паши.
3. При S = 8 выигрышная стратегия есть у Вали. После первого хода Паши в куче может стать либо 9 камней, либо 24 камня. В обеих этих позициях выигрывает игрок, который будет делать ход (теперь это Валя). Случай S = 9 рассмотрен в п. 2, случай S = 24 рассмотрен в п. 1 а.
В таблице изображено дерево возможных партий при описанной стратегии Вали. Заключительные позиции (в них выигрывает Валя) подчёркнуты. На рисунке это же дерево изображено в графическом виде (оба способа изображения дерева допустимы).
