Международная олимпиада 2022, Осло, Норвегия, 2022 год

Пусть $k$ — целое положительное число, а $S$ — конечное множество, состоящее из нечетных простых чисел. Докажите, что существует не более одного способа (с точностью до поворотов и отражений) расположить все элементы множества $S$ по кругу так, чтобы произведение любых двух соседних чисел имело вид $x^2+x+k$, где $x$ — целое положительное число.

Комментарий/решение

Решим более сильную задачу, в которой $x$ из условия может быть просто целым числом.

Представим числа в виде вершин и будем проводить ребро между двумя числами, если их произведение имеет такой вид. Тогда в нашем графе есть цикл и нужно доказать, что нет другого цикла

Рассмотрим максимальное простое число из множества и его двух соседей - $p > q$, $r$, соответственно. Тогда $4pq=x^2+c$, $4pr=y^2+c$, где $2 \nmid x$, $y$, а $c=4k-1$, тогда $x,y < 2p$, также $4p(q-r)=(x-y)(x+y)$, откуда одна из скобок делится на $p$, а значит и на $2p$. Это может быть только вторая скобка, причем $x+y<2*2p$, значит $x+y=2p$, из этого уже следует, что у $p$ нет других соседей, так как иначе суммы пар соответствующих чисел были бы все равны $2p$, а значит и сами числа равны, а значит равны и изначальные простые. $4qr=\frac{(x^2+c)(y^2+c)}{4p^2}=\frac{(xy-c)^2+c(x+y)^2}{4p^2}=(\frac{xy-c}{2p})^2+c$, то есть между $q$ и $r$ тоже есть ребро. Тогда, если предположить существование двух циклов, то можно удалить вершину с наибольшим числом и найти два цикла в оставшемся множестве. Продолжая этот процесс, мы придем в случай с тремя простыми, где есть не более одного цикла.

Постановка задачи

Пусть k — целое положительное число и пусть S — конечное множество нечетных простых чисел. Доказывать

что существует не более одного способа (с точностью до вращения и отражения) разместить элементы

S по окружности так, что произведение любых двух соседей имеет вид

Икс

2 + x + k для некоторого натурального числа x.

Мы заменяем «натуральное целое число x» на «целое неотрицательное число x» и произносим числа

форма х

2 + x + k — хорошо. Мы также могли бы заменить «неотрицательное целое число x» на «целое число x».

ввиду очевидного отображения x 7→ 1 − x.

Утверждение: если p — нечетное простое число, то существует не более двух нечетных простых чисел q и r меньше, чем

p, для которого pq = x

2 + x + k и пр = y

2 + y + k — хорошо.

Более того, если вышеописанное имеет место и x, y ≥ 0, то x + y + 1 = p и xy ≡ k

(мод р).

Доказательство. Уравнение Т

2 + T + k ≡ 0 (mod p) имеет не более двух решений по модулю p, т.е.

не более двух решений в интервале [0, p − 1]. Поскольку 0 ≤ x, y < p из p > max(q, r)

и k > 0, следует первая половина.

Для второй половины Виета также дает x + y ≡ −1 (mod p) и xy ≡ k (mod p), и

мы знаем 0 < x + y < 2p.

Утверждение: если существуют два таких простых числа, как указано выше, то qr тоже хорошо (!).

Доказательство. Пусть pq = x

2 + x + k и пр = y

2 + y + k для x, y ≥ 0, как и раньше. Зафиксируем α ∈ C такой, что

что α

2 + α + k = 0; тогда для любого n ∈ Z имеем

н

2 + n + k = Норма(n − α).

Следовательно

pq · pr = Норма

(х - α)(у - α)

= Норма

(xy − k) − (x + y + 1)α

Но Norm(p) = p

2

, поэтому объединение со второй половиной предыдущего утверждения дает

qr = Норма(

1

п

(xy − k) − α)

по мере необходимости.

Из этих двух утверждений следует утверждение непосредственно индукцией по |S|, поскольку теперь можно удалить

самый крупный элемент С.

Замечание. Чтобы показать, что условие не пустое, автор дал кольцо из 385 простых чисел.

для к = 41; см. https://aops.com/community/p26068963.

6

Не решайте по давнски