Processing math: 100%

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


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

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

  10
2 года 6 месяца назад #

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

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

Рассмотрим максимальное простое число из множества и его двух соседей - p>q, r, соответственно. Тогда 4pq=x2+c, 4pr=y2+c, где 2x, y, а c=4k1, тогда x,y<2p, также 4p(qr)=(xy)(x+y), откуда одна из скобок делится на p, а значит и на 2p. Это может быть только вторая скобка, причем x+y<22p, значит x+y=2p, из этого уже следует, что у p нет других соседей, так как иначе суммы пар соответствующих чисел были бы все равны 2p, а значит и сами числа равны, а значит равны и изначальные простые. 4qr=(x2+c)(y2+c)4p2=(xyc)2+c(x+y)24p2=(xyc2p)2+c, то есть между q и r тоже есть ребро. Тогда, если предположить существование двух циклов, то можно удалить вершину с наибольшим числом и найти два цикла в оставшемся множестве. Продолжая этот процесс, мы придем в случай с тремя простыми, где есть не более одного цикла.

  2
1 года 2 месяца назад #

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

Пусть 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

  0
1 года 2 месяца назад #

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