There are $n$ natural numbers written on the board. Every move, we could erase $a,b$ and change it to $\gcd(a,b)$ and $\text{lcm}(a,b) - \gcd(a,b)$. Prove that in finite number of moves, all numbers in the board could be made to be equal.
Problem
Source: Indonesia National Math Olympiad 2021 Problem 6 (INAMO 2021/6)
Tags: number theory, algorithm
09.11.2021 10:59
09.11.2021 11:17
Consider $x_1, x_2, \cdots, x_n$ to be the numbers on the board. Now consider the product of all such numbers. Using the following procedure, I claim that the product of all $n$ numbers is monotonically decreasing. First, the procedure: Take any $a = x_i$ and $b = x_j$. If $a = b$, find another pair. Otherwise, replace $a, b$ with $\gcd(a, b)$ and $lcm(a, b) - \gcd(a, b)$. Let the product of all other numbers (which don't have indices $i$ and $j$) be $P$. Then before the operation, the product of all such numbers is $Pab$, but after, it's $P(ab - \gcd(a,b)^2) < Pab$. Clearly the monovariant will always be positive, since $lcm(a, b) - \gcd(a, b) \geq (p-1) \gcd(a, b) \geq \gcd(a, b)$ where $p$ is a prime, and we only do an operation if two numbers are different. If it requires infinitely many steps, then the monovariant will be negative, which isn't possible by our procedure. So we'll stop the procedure when we cannot find any two numbers which are different, which is equivalent to saying all the numbers on the board are the same.
09.11.2021 13:23
We firstly observe that,$lcm(gcd(a,b),lcm(a,b)-gcd(a,b))=lcm(a,b)-gcd(a,b)$. Thus define $S=\Sigma lcm(a,b)$ over all pairs of $(a,b)$ written on the board. The move changes $lcm(a,b) \rightarrow lcm(a,b)-gcd(a,b)$,which means that $S$ is a monovariant,if move is applied on unequal $(a,b)$which clealry can't go negative and hence the process terminates.
09.11.2021 22:52
Prolly can be done better but meh. If $n=1$, then done, therefore assume $n\geq 2$. Take any two, say $a,b$. We split into cases: If $a\perp b$, then firstly make an operation on $(a,b)$ and obtain $1$ and some other number. Then make everything to $1$ as $\gcd{(x,1)}=1$ and $\text{lcm}(x,1) - \gcd(x,1)=x-1$ decreases $x$ by $1$. Consider the case, where are no numbers with $\gcd{(a,b)}=1$, initially. Then if there exists $c$ such that $\gcd(a,c)\perp \gcd(b,c)$, then we may apply the move on $(a,c)$ and then $(\gcd(a,c),b)$, which yields $1$ on the board, we return to the Case 1. Hence, we now assume that there is no such $c$, i.e. $\gcd(\{a_i\}_n)\neq 1$. Take such $a,b$ with $\gcd(a,b)=\gcd(\{a_i\}_n)$, do an operation on $(a,b)$, we obtain $d=\gcd(a,b)$. Now take any $x$ and note that $\gcd(d,x)=d$ and $\text{lcm}(x,d) - \gcd(x,d)=x-d$ decreases $x$ by $d$, repeat until $x$ replaces with $d$.
10.11.2021 03:44
Nice problem. The operation implies that we can replace any set of numbers with their gcd. The base case for $n=1$ is trivial. Then for $n,$ we wish to show $n+1,$ but then we have $n$ copies of a number $a$ and one copy of a number $b,$ and these can easily all be transformed to $\gcd(a,b),$ so we are done by induction.
21.10.2023 17:57
Let the $\gcd$ of all numbers be $s$. Then we know that any remaining number on the blackboard at any time is a multiple of $s$. Now we know that $k,s$ can be changed to $k-s,s$. Repeatedly doing so will change it to $s,s$. So $a,b$ can be changed to $\text{lcm}(a,b)-\gcd(a,b), \gcd(a,b)$, then into $\gcd(a,b), \gcd(a,b)$ in a finite of moves. We call these sequence of move a "hit". Now we hit the first two number. After doing so, hit both the number with the third one. After turning the first $t$ terms into the same number, hit all of them with the $k+1$th term. Repeat untill all terms have been hit.