Условие:
Дано n спичек. За ход разрешается брать любое количество спичек, которое является степенью простого числа (в т.ч. 1 или простое число). Проигрывает тот, у кого нет хода. При каких n выиграет первый, а при каких — второй?
Решение:
Рассмотрим игру с n спичками, где разрешается брать на ход любое количество спичек, которое является степенью простого числа (то есть, можно брать 1, а также любое простое число или число вида p^k, например, 4 = 2^2, 8 = 2^3, 9 = 3^2 и т.д.).
Начнём с анализа небольших значений n и определения выигрышных (позиция, из которой существует ход в проигрышную позицию) и проигрышных (позиция, из которой все ходы ведут в выигрышные для оппонента):
- При n = 0 спичек ход сделать нельзя – позиция проигрышная.
- n = 1. Единственный допустимый ход – взять 1 спич...
Внутри — полный разбор, аргументация, алгоритм решения, частые ошибки и как отвечать на каверзные вопросы препода, если спросит
Попробуй решить по шагам
Попробуй один шаг и продолжи в режиме обучения или посмотри готовое решение
Что нужно знать по теме:
Что нужно знать по теме
Алгоритм решения
Топ 3 ошибок
Что спросит препод
Похожие задачи