Задача No. 97942

Двое играющих по очереди увеличивают натуральное число так, чтобы при каждом увеличении разность между новым и старым значениями числа была бы больше нуля, но меньше старого значения. Начальное значение числа равно 2. Выигравшим считается тот, в результате хода которого получится 1987. Кто выигрывает при правильной игре: начинающий или его партнёр?

Скрыть решение

Решение

В последовательности 1987, 993, 496, 248, 124, 62, 31, 15, 7, 3 каждое следующее число является неполным частным от деления предыдущего на 2 с остатком. Докажем, что это последовательность выигрышных чисел (т. е. что игрок, назвавший одно из этих чисел, имеет выигрышную стратегию). Число 1987 является выигрышным по условию. Пусть число 2k или 2k + 1 (k > 2) — выигрышное. Тогда и k — выигрышное число. Действительно, если первый игрок называет число k, то второй может назвать только число из отрезка [k + 1, 2^k – 1], после чего первый может назвать и 2k, и 2k + 1.

Ответ

Первый игрок выигрывает.

Условие

Решение

Ответ