|
|
 |
Условие
На листке бумаги написаны натуральные числа от 1 до N. Игроки по очереди обводят в кружок одно число, соблюдая условие: любые два уже обведённых
числа должны быть взаимно простыми. Два раза число обводить нельзя. Проигрывает тот, у кого нет хода.
а) Кто – начинающий игру или ходящий вторым – победит при
N = 10?
б) А при N = 12?
в) А при N = 15?
г) А при N = 30?
Решение
Число 1 может обвести любой игрок в любой момент. Про остальные числа можно сказать вот что: если мы обводим число, имеющее простые делители p1, p2, ..., pk, то больше ни одно число, делящееся на хотя бы одно из этих простых чисел, обводить нельзя. Фактически игру можно понимать так: выписаны все простые числа, не превосходящие N, и число 1, и можно "брать" одно или несколько таких чисел (если их произведение не больше N). Так, обводя 3, мы "берём" простое число 3, обводя 9, тоже "берём" 3, а обводя, скажем, 12, "берём" 2 и 3 одновременно.
а) Список чисел: 1, 2, 3, 5, 7. Первым ходом начинающий (назовём его Петя) берёт 2. Далее простые числа можно брать только по одному, поэтому по чётности Петя выигрывает.
б) Список чисел: 1, 2, 3, 5, 7, 11. Петя берёт 2 и 3 (обведя 6). Дальше простые числа можно брать только по одному, и Петя выигрывает.
в) Список чисел: 1, 2, 3, 5, 7, 11, 13. Петя не может помешать второму (Васе) взять два числа сразу: какое бы число из набора 2, 3, 5 ни взял Петя, Вася берёт два оставшихся. Если Петя сам возьмёт два числа, дальше они будут брать по одному, и он проиграет. Если Петя возьмёт 1, 7, 11 или 13, Вася возьмёт, например, 2 и 3 и всё равно победит.
г) Список чисел: 1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. Петя, обводя 30, берёт сразу три числа: 2, 3 и 5. Дальше числа можно брать только по одному, и он побеждает.
Замечания
Петя побеждает при всех N ≤ 30, кроме N = 2, 5, 15, 16, 19, 20, 21, 22, 29. Исход игры зависит от распределения в ряду от 1 до N простых чисел и произведений различных простых, но простых закономерностей нет.
