Олимпиадная задача по теории алгоритмов для 7–9 классов от Подлипского О. К.
Задача
Двое по очереди выписывают на доску натуральные числа от 1 до 1000. Первым ходом первый игрок выписывает на доску число 1. Затем очередным ходом на доску можно выписать либо число2a , либо число a+1, если на доске уже написано число a . При этом запрещается выписывать числа, которые уже написаны на доске. Выигрывает тот, кто выпишет на доску число 1000. Кто выигрывает при правильной игре?
Решение
Заметим, что если какой-то из игроков выпишет на доску число 500 или 999 (назовем такой ход проигрышным), то его противник следующим ходом выпишет число 1000 и выиграет.
Какие числа могут быть выписаны на доску до появления чисел 500 и 999?
Во-первых, это все числа от 1 до 499 (их 499). Во-вторых, это все числа от 502 до 998 (их 497), так как 502 можно получить из числа 251.
Заметим также, что число 501 может получиться только из числа 500. То есть перед появлением числа 500 или 999 будет сделано499+497=996непроигрышных ходов. Это означает, что проигрышный ход сделает первый игрок.
Ответ
Выигрывает второй.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь