第1题

黑板上写有

2026

个大于

1

的整数，不一定互不相同。在一次操作中，孔子从黑板的不同位置选取两个整数

m>1

与

n>1

，并把这两个整数替换为

\tfrac{\operatorname{lcm}(m,n)}{\gcd(m,n)}

与

\gcd(m,n)

。只要还能进行，他就不断继续操作。(a) 求证:无论孔子如何选择，经过有限次操作后，黑板上恰有一个大于

1

的整数

M

。(b) 求证:

M

的值不依赖于孔子的选择。

第 4/4 步：第 (b) 部分:不变量唯一确定 M

上一步下一步

v_p(M)=\gcd(v_p(M),0,\ldots,0)=\gcd(v_p(a_1),\ldots,v_p(a_{2026}))\ \Longrightarrow\ M=\prod_p p^{\gcd(v_p(a_1),\ldots,v_p(a_{2026}))}

详细分析

设 $a_1,\ldots,a_{2026}$ 为黑板上的初始数。游戏结束时黑板上由 $M$ 与 $2025$ 个一组成，其 $p$ 进赋值为 $v_p(M)$ 与 $2025$ 个零;这些终止赋值的最大公约数为 $\gcd(v_p(M),0,\ldots,0)=v_p(M)$ 。由第3步的不变性，对每个素数 $p$ ，它都必须等于初始最大公约数 $\gcd(v_p(a_1),\ldots,v_p(a_{2026}))$ 。因为正整数由其在所有素数 $p$ 上的 $p$ 进赋值唯一确定，所以 $M$ 只依赖于初始数，而不依赖于孔子的选择。