第1問

黒板に

1

より大きい

2026

個の整数が書かれており、それらは異なるとは限らない。1回の操作で、孔子は黒板の異なる場所から2つの整数

m>1

と

n>1

を選び、これら2つの整数を

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

と

\gcd(m,n)

に置き換える。彼は可能な限り操作を続ける。(a) 孔子の選択にかかわらず、有限回の操作の後、黒板上で

1

より大きい整数

M

がちょうど1つだけになることを証明せよ。(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$ 個の1からなり、その $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$ は最初の数のみに依存し、孔子の選択にはよらない。