Задание 26, № 97 (задание с сайта К.Ю. Полякова)
(Д.И.Перминов, г.Барнаул) Два игрока, Петя и Ваня, играют в сле-дующую игру. Перед игроками лежит куча, состоящая из S конфет. Игроки ходят по очереди, первый ход делает Петя. За один ход иг-рок может съесть не более половины от всех оставшихся конфет, но не менее одной конфеты.
Игра завершается в тот момент, когда в куче не остается ни одной конфеты. Победителем считается игрок, который съел последнюю конфету.
Задание 1. Кто из игроков имеет выигрышную стратегию при S= 5, 6, 7 ?
Задание 2.Какое минимальное количество ходов должен совер-шить игрок, чтобы победить при S= 12 ? Назовите имя этого игрока.
Задание 3. Укажите максимальное значение S, меньшее 15, при котором выигрышную стратегию имеет Ваня.
Решение.
Сначала просчитаем выигрышные и проигрышные позиции.
1 конфета: игрок, который ходит из этой позиции выигрывает.
2 конфеты: игрок может съесть не более половины имеющихся конфет, следовательно, тот, кто ходит из этой позиции может съесть только одну конфету. Остается одна конфета, которую съест его противник. Позиция проигрышная.
3 и 4 конфеты: игрок может перевести противника в проигрышную позицию «2» и выиграть. Позиция выигрышная.
5 конфет: игрок может съесть не более 2 конфет. Позиция проиг-рышная
Определим дальнейшие позиции.
Из позиций [6..10] игрок может съесть такое количество конфет, чтобы в куче осталось 5 конфет. Таким образом, он приводит противника в проигрышную позицию и выигрывает.
Следующая позиция – 11. Игрок может съесть максимум от 1 до 5 конфет. И в любом случае, в куче остается от 6 до 10 конфет, т.е он привел противника в выигрышную для него позицию и проиграл.
Представим это на шкале:
Очевидно, что позиции [12..22] – выигрышные 4 ходом, а 23 – проиг-рышная.
Таким образом, номер каждой следующей проигрышной позиции равен 2n + 1, где n – номер текущей проигрышной позиции. Все позиции от одной проигрышной до другой – выигрышные.
Вернемся к решению задачи.
Задание 1. При S= 5 выигрышную стратегию имеет Ваня.
При S= 6, 7 выигрышную стратегию имеет Петя. Ему нужно оста-вить в куче 5 конфет.
Задание 2. При S=12 игрок минимально совершит 4 шага. Из этой пози-ции выиграет Петя.
Задание 3. 11.
Теперь, зная, как высчитать выигрышные и проигрышные пози-ции, решим задачи № 98 и 99.
№ 98. (Д.И.Перминов, г.Барнаул) Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча, состоящая из S кон-фет. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может съесть не более половины от всех оставшихся конфет, но не менее одной конфеты.
Игра завершается в тот момент, когда в куче не остается ни одной конфеты. Победителем считается игрок, который съел последнюю конфету.
Задание 1. Кто из игроков имеет выигрышную стратегию при S= 17, 18, 19 ?
Задание 2.Какое максимальное количество ходов может совер-шить игрок, чтобы победить при S= 20 ? Назовите имя этого игрока.
Задание 3. Укажите минимальное значение S, большее 40, при ко-тором выигрышную стратегию имеет Ваня.
Решение
Задание 1. При S= 17, 18, 19 выигрышную стратегию имеет Петя. Ему нужно оставить в куче 11 конфет.
Задание 2. При S= 20 выигрывает Петя на 4 ходу.
Задание 3. 47 (23*2+1).
№ 99. (Д.И.Перминов, г.Барнаул) Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча, состоящая из S кон-фет. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может съесть не более половины от всех оставшихся конфет, но не менее одной конфеты.
Игра завершается в тот момент, когда в куче не остается ни одной конфеты. Победителем считается игрок, который съел последнюю конфету.
Задание 1. Кто из игроков имеет выигрышную стратегию при S= 150 ?
Задание 2. За какое наименьшее количество ходов может завер-шиться игра при S=23 ?
Кто при этом победит?
Задание 3. Укажите все трехзначные S при которых выигрышную стратегию имеет Ваня.
Задание 1. S= 150 не является проигрышной позицией, поэтому выигрышную стратегию имеет Петя. Ему нужно оставить 95 кон-фет.
Задание 2. При S=23 игра закончится за 8 шагов, выиграет Ваня.
Задание 3. 95*2+1=191,
191*2+1 = 383
383*2+1=767