Задание 26 с конфетами (2020 г.)

Задание 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