Игра: на столе $n$ камней. Первый игрок берёт от 1 до $n-1$ камней, затем каждый следующий ход можно взять от 1 до удвоенного количества, взятого предыдущим игроком. Проигрывает взявший последний камень. При каких $n$ проигрывает первый игрок?
Правильный ответ
Первый проигрывает тогда и только тогда, когда $n$ является числом Фибоначчи. Это следует из теоремы Зекендорфа и свойств игры Эвклида-Фибоначчи (игра Евклида). Числа Фибоначчи: 1, 2, 3, 5, 8, 13, 21, ... При $n$ — числе Фибоначчи первый проигрывает при правильной игре второго.
💡 Авторизуйтесь, чтобы получить помощь AI-тьютора с подсказками и решениями!