Let $n \ge 2$ be an integer and let $a_1, a_2, \cdots a_n$ be fixed positive integers (not necessarily all distinct) in such a way that $\gcd(a_1, a_2 \cdots a_n)=1$. In a board the numbers $a_1, a_2 \cdots a_n$ are all written along with a positive integer $x$. A move consists of choosing two numbers $a>b$ from the $n+1$ numbers in the board and replace them with $a-b,2b$. Find all possible values of $x$, with respect of the values of $a_1, a_2 \cdots a_n$, for which it is possible to achieve a finite sequence of moves (possibly none) such that eventually all numbers written in the board are equal.
Problem
Source: Iberoamerican MO 2024 Day 2 P5
Tags: combinatorics, number theory
Supertinito
23.09.2024 14:41
This great problem was proposed by Lorenzo Sarria from Colombia. He recently graduated from high school and this is his first problem in an international Olympiad. But I believe that he is going to be one of the great problem authors.
br_cr7
24.09.2024 19:12
Answer
All $x$ such that $a_1+a_2+\dots+a_n+x=2^k(n+1)$ for some positive integer $k$
Solution
It is clear that for such $x$ we must have $n+1\mid a_1+a_2+\dots+a_n+x=S$ since the sum S is invariant through the process. Therefore, $S=k(n+1)$ and we are going to prove that all k that works are powers of 2.
Part 1 - $k$ must be of the form $2^j$
Suppose, for the sake of contradiction, that there exists a prime $p\neq 2$ such that $p\mid k$. Thus, as at the end we have all terms in the blackboard equal $k$, $p$ would divide them all. However, if $p$ divides all numbers after a move $(a, b) \longrightarrow (a-b, 2b)$ then $p\mid 2b$ and $p\mid a-b \Rightarrow p\mid b$ and $p\mid a$, so $p$ divided each number before that move. As $p$ divides all terms at the end of the process, $p$ would divide all terms at the beginning, a contradiction since $(a_1, a_2, \dots, a_n)=1$.
Part 2 - $k=2^j$ works
Note that it works for $j=0$ since all $a_i$ are positive integers and must be 1. We proceed by induction on $j$. We aim to make all numbers even, so we can scale each number by $\dfrac{1}{2}$ having $a_i'=\dfrac{a_i}{2}$ and $S'=\dfrac{S}{2}=2^{j-1}(n+1)$ and conclude the induction.
Note that for $j\ge 1$ the number of odd terms is even, since the sum is even. Thus, we can pair these odd numbers, if they are different, and make a move in each pair as $a-b$ and $2b$ are both even if $a$ and $b$ are odd. Therefore, we only need to consider the case where all the odd numbers are equal (so we can't pair them now). Let $a_1=a_2=\dots=a_i=2r+1$ and the others to be even (note that $i$ must be even since $S$ is even). Then, we take an even number $a_j\neq 4k+2$ from the blackboard (such term exists, otherwise $2k+1$ would be a common factor of all numbers and it is a contradiction from our previous argument on Part 1). Make a move in $(a_i, a_j) \longrightarrow (\lvert a_i-a_j\rvert, 2min(a_i, a_j))$ so $\lvert a_i-a_j\rvert\neq a_i$ and is odd since $a_j\neq 4k+2$ and is even. Thus, we perform another move in $(a_{i-1}, \lvert a_i-a_j\rvert)$ letting them both even. Note that we decreased the amount of odd numbers in 2. Repeating this proceedure, we make all terms even and conclude the induction.
The conclusion follows.