第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

の値が孔子の選択によらないことを証明せよ。

ステップ 2/4: パート (a):ただ1つの M > 1 を残して終了する

前のステップ次のステップ

(\text{product of board},\ 2026-\#\text{ones})\ \text{strictly decreases lexicographically}

詳しい解説

いったん $1$ になった数は二度と選ばれない(操作には $m,n>1$ が必要)。ステップ1より、各操作は黒板上の全数の正整数積を狭義に減少させるか、その積を保ったまま $1$ の個数を $1$ 増やす(これは連続して高々 $2025$ 回しか起こらない)かのいずれかである。したがってゲームは有限回の操作で必ず終了する。 $m,n>1$ に対する各操作で、 $g$ と $mn/g^2$ の少なくとも一方は $1$ より大きい( $g=1$ なら $mn/g^2=mn>1$ ; $g>1$ なら $g$ 自身が $>1$ )ので、黒板がすべて $1$ になることは決してない;他方、 $1$ を超える数が少なくとも2つある限り次の操作が可能である。よって終了時にはちょうど1つの整数 $M>1$ と $2025$ 個の1が残る。