СПбГУ 2022, 10-11 классы, задача 1
( баллов) На картинке нарисовано несколько кружочков, соединенных отрезками. Саша выбирает натуральное число и расставляет в кружочках различные натуральные числа так, чтобы для любых двух всех этих чисел выполнялось свойство: если числа и не соединены отрезком, то сумма должна быть взаимно проста с , а если соединены, то числа и должны иметь общий натуральный делитель, больший . При каком наименьшем существует такая расстановка?
Ответ: .
Решение. Сделаем два замечания.
-
нечетно. Действительно, пусть четно. Среди семи чисел всегда есть три числа одной четности, и по условию они должны быть попарно соединены. Но на картинке нет циклов длины .
-
Если — простой делитель , то среди четырех последовательно соединенных чисел существует пара соседних, сумма которых не кратна . Возьмем цепочку последовательно соединенных чисел. По условию
Тогда числа и тоже соединены, то есть на картинке получился цикл длины , которого там нет.
Из 1) и 3) вытекает, что число имеет по крайней мере два различных нечетных простых делителя. Пусть их ровно два (скажем, и ). Покажем, что они отличны от . Допустим, например, что . Не более двух чисел делятся на (если их три, то они образуют цикл). Остальные числа разобьем на две группы, дающие при делении на остатки и . Одна из этих групп пуста, иначе любое число из меньшей группы будет соединено по крайней мере с тремя числами из другой группы, что невозможно. Сумма чисел из одной группы на не делится. Поэтому существует трехзвенная цепочка, в которой сумма любой пары соединенных чисел не кратна и, значит, делится на . Но это противоречит 2).
Таким образом, если имеет ровно два различных нечетных простых делителя, то . Если же таких делителей больше двух, то . Расстановка для приведена на рисунке.
