Задание 19 ЕГЭ, математика (профиль): Числа и их свойства

а) Нужно расставить числа 9–18 по кругу так, чтобы у всех соседних пар НОД был 1. Подходит порядок 9, 16, 15, 14, 13, 12, 11, 18, 17, 10 — если проверить каждую пару соседей, все они окажутся взаимно простыми. Значит, такая расстановка существует.

б) По кругу стоит 10 чисел, значит и пар соседей ровно 10, то есть НОД считается 10 раз. Если все 10 значений НОД попарно различны, то среди них есть 10 разных натуральных чисел, а значит хотя бы одно из них не меньше 10. Но для чисел от 9 до 18 максимально возможный НОД достигается на паре (9, 18): $\gcd(9,18)=9$. Больше 9 НОД быть не может, поэтому получить 10 различных значений невозможно.

в) Среди чисел 9–18 есть три простых числа: 11, 13, 17. У простого числа $p$ и любого другого числа $n$ из этого набора $\gcd(p,n)=1$, так как $p$ не делится ни на что кроме 1 и себя, а все остальные числа набора меньше $p^2$ и не кратны $p$ (кроме случая, когда сами равны $p$). Значит, для каждого из этих трёх чисел оба соседа дают НОД, равный 1.

Каждое число имеет двух соседей, всего у трёх простых чисел — 6 «соседств», но так как эти три числа не могут все находиться подряд без повторов рассмотрим: по кругу они расположены среди 10 чисел, поэтому хотя бы два из этих трёх простых чисел имеют соседа, не входящего в тройку {11,13,17}. Это даёт не менее четырёх пар с НОД=1 (по принципу учёта соседств, так как каждая такая пара считается один раз, но минимум 4 из 10 пар дают значение 1).

Таким образом, среди 10 значений НОД как минимум четыре совпадают и равны 1, поэтому различных значений не может быть больше $10-4+1=7$.

Пример расстановки 9, 18, 12, 16, 14, 13, 11, 17, 10, 15 даёт ровно 7 различных значений НОД, значит эта оценка достижима.