Контрольные тренировочные задания
(решения)

Часть 2

Задание 26

Решение примера 1

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

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

Задание 1
а) При каких значениях числа S Паша может выиграть в один ход? Укажите все такие значения и соответствующие ходы Паши.
б) У кого из игроков есть выигрышная стратегия при S = 26, 25, 24? Опишите выигрышные стратегии для этих случаев.

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

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

Решение.

1. а) Паша имеет выигрышную стратегию и может выиграть за один ход, если S=27, тогда ему достаточно добавить один камень, чтобы игра закончилась при 28 камнях в куче; или если S = 14, 15, 16, 17, 18, 19, 20, 21, 22 (44/2 = 22 и 28/2 = 14, т.е. от 14 до 22), тогда необходимо удвоить количество камней в куче.

   б) При S=26 выигрышная стратегия у Вали. Паша ходит первым, у него есть возможность удвоить количество камней в куче, и тогда количество камней превысит 44, — выигрывает Валя, либо возможность увеличить количество на один камень, станет 27 камней, следующий ход за Валей — она может положить один камень и выиграть.

   При S=25 выигрышная стратегия у Паши. Паша ходит первым: удваивать количество камней нет смысла, т.к. количество камней превысит 44, значит Паша добавит один камень, станет 26 камней, следующий ход за Валей, — она может либо добавить камень (станет 27 камней, следующим ходом выиграет Паша) либо удвоить — и сразу проиграть, т.к. станет более 44 камней.

   При S=24 выигрышная стратегия у Вали. Паша ходит первым: удваивать количество камней нет смысла, т.к. количество камней превысит 44, значит Паша добавит один камень, станет 25 камней, следующий ход за Валей, — она может только добавить один камень (станет 26 камней, следующим ходом Паша оказывается в проигрышной ситуации, см. пункт при S=26).

2. При S=13 или S=12 выигрышная стратегия у Паши. Паша ходит первым: удваивает количество камней и в куче остается 26 камней или 24 камня. Это проигрышная позиция для того, кто ходит (см. п. 1 б), а следующий ход за Валей.
3. При S=11 выигрышная стратегия есть у Вали. Паша ходит первым: в куче остается либо 22 камня, либо 12 камней. Обе эти позиции выигрышные для того, кто ходит. При S=12 ход игры описан в пункте 2, а при S=22 — в пункте 1а.

Дерево возможных партий:




* Для Вали отображены только ходы по стратегии
** красный круг означает выигрыш
*** фиолетовый круг — конец игры (проигрыш)

Возврат на страницу    Решение примеров части 2 задание 26