第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

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

ステップ 1/4: 置き換えを書き直し、積を追跡する

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

\frac{\operatorname{lcm}(m,n)}{\gcd(m,n)}=\frac{mn}{\gcd(m,n)^2},\qquad \text{new pair product}=\frac{mn}{\gcd(m,n)}

詳しい解説

$\operatorname{lcm}(m,n)\cdot\gcd(m,n)=mn$ を用いると、置き換え後の2数は $g:=\gcd(m,n)$ と $mn/g^2$ であり、その積は $mn/g$ となる。 $g>1$ のときは常にこの新しい積 $mn/g$ は元の2数の積 $mn$ より真に小さいので、黒板上の $2026$ 個すべての数の積は狭義に減少する; $g=1$ のときは置き換えが $(1,mn)$ となり、全体の積は変わらないが新しい $1$ が1つ増える( $m,n>1$ はどちらも $1$ ではなく、 $mn>1$ であるため)。