На доске написано число 21. играют двое. За один ход разрешается уменьшить число на любой из его целых положительных делителей в том числе на единицу или на само это число. Если при этом получается ноль, игрок проиграл. Вопрос: сколько выигрышных позиций соответствует значениям от 1 до 21? Решение Игра: На доске написано число. За один ход игрок может уменьшить его на любой делитель этого числа (например, для 6 делители: 1, 2, 3, 6). Кто в свой ход делает ноль — тот и проиграл. Что значит «выигрышная позиция»? Это такое число на доске, что тот, кто сейчас ходит, может при правильной игре всегда победить. А «проигрышная позиция» — это число, при котором как бы ты ни ходил, соперник всё равно сможет победить. Начинаем разбирать маленькие числа: 1: единственный ход — вычесть 1 и получить 0. Но тот, кто получил 0, сразу проигрывает. Значит, 1 — проигрышное число. 2: можно вычесть 1 и оставить противнику 1. А мы уже знаем, что 1 — проигрыш. Значит, у того, кто получил 2, есть хороший ход → 2 — выигрышное число. 3: какие ходы? вычесть 1 → остаётся 2 (а 2 выигрышное, значит противник будет в выигрыше); вычесть 3 → сразу 0, и тогда проигрывает тот, кто сделал ход. То есть у 3 нет «удачного» хода → 3 — проигрышное число. 4: можно вычесть 1 и оставить 3, а 3 проигрышное. Значит, 4 — выигрышное. Видим закономерность: нечётные числа — проигрышные, чётные — выигрышные. Почему так всегда? Если число чётное, то можно просто вычесть 1 → получится нечётное, а нечётные мы уже знаем — проигрышные. Значит, у чётного всегда есть удачный ход. Если число нечётное, то все его делители тоже нечётные (например, у 9 делители 1, 3, 9). Значит, вычитая нечётное из нечётного, всегда получаешь чётное. А чётные — это выигрышные позиции. Получается, у того, кто стоит на нечётном, нет шансов уйти в «плохое» число для соперника → это проигрышная позиция. Итог для чисел от 1 до 21 Проигрышные: все нечётные (1, 3, 5, …, 21) → таких 11. Выигрышные: все чётные (2, 4, 6, …, 20) → таких 10. ОТВЕТ ДЛЯ ДАННОЙ ЗАДАЧИ 10
2 месяца назад