Всесиб 2025, отборочный этап, 11 класс, задача 5
( баллов) Вершины правильного -угольника занумерованы натуральными числами от до включительно. Петя и Вася играют в следующую игру. Очередным ходом каждый игрок соединяет отрезком любые две различные вершины, номер одной из которых делит номер другой, и которые к этому моменту ещё не соединены отрезком. Побеждает тот игрок, после хода которого впервые образуется треугольник с вершинами в вершинах -угольника, одна из которых имеет номер . Сначала никакая пара вершин не соединена отрезком. Первым ходит Петя. Кто из них победит при правильной игре? Отрезки могут пересекаться.
Ответ
Ответ. Выиграет Петя.
Решение. Укажем выигрышную стратегию для Пети. Первым ходом он должен соединить вершины с номерами и . Теперь тот, кто после этого первым совершит один из ходов , , , , , , , , проиграет, потому, что на его ход противник ответит ему ходом (или наоборот) и выиграет. Поэтому дальше Пете нужно отвечать на ходы Васи, отличные от восьми указанных, любыми ходами, отличными от восьми указанных. Каждый такой ход безопасен для обоих игроков потому, что не создаёт треугольника с вершиной номер и не создаёт новой угрозы, аналогичной ходу . Докажем, что таких ходов всего чётное количество, поэтому Пете удастся реализовать указанную стратегию.
Первый тип таких ходов — это ходы вида , , , их штуки, это чётное число.
Второй тип таких ходов — это ходы вида , , . При фиксированном это число равно количеству собственных делителей , то есть делителей, отличных от и самого . Это число является чётным, если не является квадратом натурального числа, и нечётным, если является квадратом натурального числа, так как все собственные делители , отличные от , можно объединить в пары , . Точных же квадратов, больших и меньших , существует шесть, это и , это тоже чётное число. Следовательно, сумма количеств собственных делителей у всех , не являющихся квадратами, чётна, как сумма чётных чисел, а сумма количеств собственных делителей у всех , являющихся квадратами чётна, как сумма чётного числа нечётных чисел. Значит, общее число ходов второго типа чётно, и выигрышная стратегия Пети реализуема.