Международная олимпиада 2022, Осло, Норвегия, 2022 год
Комментарий/решение:
Решим более сильную задачу, в которой x из условия может быть просто целым числом.
Представим числа в виде вершин и будем проводить ребро между двумя числами, если их произведение имеет такой вид. Тогда в нашем графе есть цикл и нужно доказать, что нет другого цикла
Рассмотрим максимальное простое число из множества и его двух соседей - p>q, r, соответственно. Тогда 4pq=x2+c, 4pr=y2+c, где 2∤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=(x2+c)(y2+c)4p2=(xy−c)2+c(x+y)24p2=(xy−c2p)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
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.