Международная олимпиада 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}))$$

Пусть на доске записаны изначально числа $a_1,a_2,...,a_{2026}$.

Пункт (a): Пусть $P$ это произведение всех чисел на данный момент. После каждой операции $P$ делиться на $\gcd(m, n)$. Так как $P$ не увеличивается в один момент она станет константой. То есть на доске все числа будут попарно взаимно простые. Пусть на доске числа $1,1,..., x_1,x_2,...,x_k$. Тогда операции будут проводится между $x_i$, и количество чисел не $1$ будет уменьшаться на $1$, и в конце на доске будут числа $1,1,\dots,1,x_1x_2\cdots x_k$.

Пункт (b): Рассмотрим какой-то простой делитель $p$ изначального $P$. Пусть $n=\gcd(v_p(a_1), v_p(a_2),\dots,v_p(a_{2026}))$. После любой операции между числами $m$ и $n$, где $v_p(m)=x>v_p(n)=y$, $(x,y)$ заменяется на $(x-y,y)$. Пока на доске все степени вхождения по $p$, для всех чисел кроме одного не станет $0$. То есть если после конечного количества таких операции с числами $v_p(a_1),v_p(a_2), ...,v_p(a_{2026})$ осталось одно число, то это число $n$, так как наши операции это алгоритм Евклида проделанная на $2026$ числах.

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