|
|
 |
Условие
Двое играют в следующую игру. Есть кучка камней. Первый каждым своим ходом берет 1 или 10 камней. Второй каждым своим ходом берёт m или n камней. Ходят по очереди, начинает первый. Тот, кто не может сделать ход, проигрывает. Известно, что при любом начальном количестве камней первый всегда может играть так, чтобы выиграть (при любой игре второго). Какими могут быть m и n?
Решение
Пусть хотя бы одно из чисел m и n меньше 9 (например, m). При исходной кучке из m + 1 камня, первый вынужден будет первым ходом взять 1 камень (m + 1 < 10), после чего второй возьмет m камней и выиграет. Противоречие.
Пусть m = n + 9. Снова при исходной кучке из m + 1 = n + 10 камней первый проигрывает.
Докажем, что при остальных значениях m и n первый выигрывает. Для этого достаточно показать, что при любом количестве камней в куче первый может сделать ход так, чтобы в куче осталось число камней, отличное и от m, и от n.
Пусть в куче k камней и ход первого. Если k ≤ 10, то первый выигрывает одним ходом (вычитая 10, если k = 10, или 1, если k ≤ 9).
Пусть k > 10. Первый может оставить в куче либо k – 1 камень, либо k – 10. Если бы в одном случае получалось m, а в другом – n, число |m – n| равнялось бы 9. Противоречие. Число камней в куче будет уменьшаться, и в итоге первый выиграет.
Ответ
m, n ≥ 9 и |m – n| ≤ 9.
Замечания
5 баллов
