MathLabs

第1题

黑板上写有 20262026 个大于 11 的整数,不一定互不相同。在一次操作中,孔子从黑板的不同位置选取两个整数 m>1m>1 与 n>1n>1,并把这两个整数替换为 lcm⁡(m,n)gcd⁡(m,n)\tfrac{\operatorname{lcm}(m,n)}{\gcd(m,n)} 与 gcd⁡(m,n)\gcd(m,n)。只要还能进行,他就不断继续操作。(a) 求证:无论孔子如何选择,经过有限次操作后,黑板上恰有一个大于 11 的整数 MM。(b) 求证:MM 的值不依赖于孔子的选择。
第 2/4 步:第 (a) 部分:终止时只剩唯一一个 M > 1
(product of board, 2026−#ones) strictly decreases lexicographically(\text{product of board},\ 2026-\#\text{ones})\ \text{strictly decreases lexicographically}
详细分析

一旦某个数变成 11,它就再也不会被选中(操作要求 m,n>1m,n>1)。由第1步,每次操作要么严格减小黑板上所有数的正整数乘积,要么在保持该乘积不变的同时使 11 的个数增加 11(这连续发生至多 20252025 次)。因此游戏必在有限步后终止。在对 m,n>1m,n>1 的每次操作中,gg 与 mn/g2mn/g^2 至少有一个大于 11(若 g=1g=1 则 mn/g2=mn>1mn/g^2=mn>1;若 g>1g>1 则 gg 本身就 >1>1),故黑板绝不会全变成 11;另一方面,只要还有至少两个数大于 11,就能继续操作。因此终止时恰有一个整数 M>1M>1 和 20252025 个一。