Международная олимпиада 2026, Шанхай, 2026 год

Доска разделена на 2026 частей. В каждой части написано по одному целому числу, большему 1 (числа на доске не обязательно различны). Время от времени Пафнутий выполняет следующие действия. Он выбирает две различные части доски, числа в которых больше 1. Обозначим число в первой из частей через $m$, а во второй — через $n$. Пафнутий заменяет эти два числа на числа $$ \text{НОД}(m, n) \quad \text { и } \quad \frac{\text{HOK}(m, n)}{\text{HOД}(m, n)}.$$ Он продолжает эти действия, пока возможно.
   (a) Докажите, что независимо от действий Пафнутия рано или поздно только в одной из частей будет написано число, большее 1. Обозначим это число через $M$.
   (b) Докажите, что значение $M$ не зависит от действий Пафнутия.

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

Я решил только А не знаю как решать Б

Пусть на доске в некоторый момент записаны числа $x_1, x_2, \dots, x_{2026}$. Обозначим через $S$ количество чисел на доске, которые строго больше $1$. Применим операцию к двум числам $m, n > 1$, заменяя их на $g = \text{НОД}(m, n)$ и $L' = \frac{\text{НОК}(m, n)}{\text{НОД}(m, n)}$. Рассмотрим два возможных случая для выбранной пары $(m, n)$:

1. Если $\text{НОД}(m, n) = 1$: Тогда $g = 1$, а новое число $L' = m \cdot n > 1$. Одно из чисел превратилось в $1$, следовательно, количество чисел на доске, больших $1$, строго уменьшилось на $1$ (величина $S$ уменьшилась на $1$).

2. Если $\text{НОД}(m, n) > 1$: Тогда оба новых числа $g$ и $L'$ строго больше $1$, поэтому $S$ не меняется. Однако произведение всех чисел на доске изменяется, так как вместо произведения $m \cdot n$ мы получаем $g \cdot L' = \text{НОК}(m, n) = \frac{m \cdot n}{\text{НОД}(m, n)} < m \cdot n$. Поскольку произведение всех чисел на доске является натуральным числом и строго уменьшается при каждой такой операции, этот случай может произойти лишь конечное число раз.

Так как операции второго типа не могут продолжаться бесконечно, а операции первого типа уменьшают конечное число $S$, весь процесс гарантированно завершится за конечное число шагов. Когда процесс завершился, на доске не может оставаться двух чисел, больших $1$ (иначе операцию можно было бы продолжить). Покажем, что не может оказаться так, что все числа стали равны $1$. Действительно, если хотя бы одно из исходных чисел делилось на некоторый простой делитель $p$, то по крайней мере одно из чисел на доске всегда будет делиться на $p$ на каждом шаге (поскольку если $p$ делит $m$ или $n$, то $p$ делит $\text{НОК}(m, n)$, а значит, делит либо $g$, либо $L'$). Следовательно, в конце на доске останется ровно одно число $M > 1$.

b)

Пусть на доске были записаны числа a и b, которые превратились в c и d, то для произвольного простого р, будет выполняться:

$$V_{p}(c)=min(V_{p}(b), V_{p}(a))$$

$$V_{p}(d)=|V_{p}(a)-V_{p}(b)|$$

По алгоритму Евклида

$$\gcd(V_p(a),V_p(b))=\gcd(V_p(c),V_p(d)) \Rightarrow \gcd(V_{p}(a_1),V_{p}(a_2),\ldots,V_{p}(a_{2026}))=\gcd(M,0,0,\ldots,0). \Rightarrow V_{p}(M)=gcd((V_{p}(a_1),V_{p}(a_2),\ldots,V_{p}(a_{2026}))$$