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

Тақта 2026 бөлікке бөлінген. Әр бөлікте 1-ден үлкен бір бүтін сан жазылған (тақтадағы сандардың бірдей болуы міндетті емес). Уақыт өте келе Пафнутий келесі әрекетті орындайды. Ол ішінде 1-ден үлкен сандар жазылған екі түрлі бөлікті таңдайды. Бірінші бөліктегі санды $m$, ал екіншісіндегі санды $n$ деп белгілейік. Пафнутий осы екі санды $$ \text{ЕҮОБ}(m,n) \quad \text{және} \quad \frac{\text{ЕКОЕ}(m,n)}{\text{ЕҮОБ}(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}))$$