Problem 1

There are

2026

integers greater than

1

written on a blackboard, not necessarily different. In a move, Confucius chooses two integers

m>1

and

n>1

from different places on the blackboard and replaces these two integers with

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

and

\gcd(m,n)

. He continues to make moves while it is possible to do so. (a) Prove that, regardless of the choices of Confucius, after finitely many moves, exactly one integer

M

on the blackboard is greater than

1

. (b) Prove that the value of

M

does not depend on the choices of Confucius.

Step 2 of 4: Part (a): termination with a single M > 1

Previous step Next step

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

Detailed analysis

Once a number becomes $1$ , it can never be chosen again (moves require $m,n>1$ ). By step 1, each move either strictly decreases the positive-integer product of all board numbers, or keeps that product fixed while increasing the count of $1$ s by $1$ (which can happen at most $2025$ times in a row). Hence the game must terminate after finitely many moves. At each move on $m,n>1$ , at least one of $g$ and $mn/g^2$ is greater than $1$ (if $g=1$ then $mn/g^2=mn>1$ ; if $g>1$ then $g$ itself is $>1$ ), so the board never becomes all $1$ s; on the other hand, as long as at least two numbers exceed $1$ , another move is possible. Therefore termination leaves exactly one integer $M>1$ and $2025$ ones.