Given integer $n \geq 3$. $1, 2, \ldots, n$ were written on the blackboard. In each move, one could choose two numbers $x, y$, erase them, and write down $x + y, |x-y|$ in the place of $x, y$. Find all integers $X$ such that one could turn all numbers into $X$ within a finite number of moves.
Problem
Source: IMOC 2023 C6
Tags: combinatorics
starchan
10.09.2023 11:44
cute problem
The answer is all powers of two at least $n$.
First let us show that if all numbers can be converted into an integer $X$ then $X \geq n$ and $X$ is a power of two. Consider the largest number on the blackboard at any point of time. Either it increases in value or stays constant. Since initially it was $n$ finally it must be $\geq n$. Thus $X \geq n$. Next, suppose that an odd prime $p$ divides $X$. Consider reversing the operations on the final tuple $(X, X, \dots, X)$. We go (in the inverse transform) from \[(a, b) \mapsto \left(\frac{a+b}{2}, \frac{|a-b|}{2}\right)\]In particular $p$ divides the new numbers as well, as long as it divides the numbers $a, b$. Since $p$ divides the numbers (all are $X$) in the beginning it follows that every number on the blackboard must've been a multiple of $p$ at all times, impossible since $1$ was on the board at some point. Thus if $X$ is attainable then $X$ is a power of $2$ and at least $n$.
Now, let $\ell$ be the smallest positive integer such that $2^{\ell} \geq n$. We've to show that all tuples $(2^m, 2^m, \dots, 2^m)$ are attainable whenever $m \geq \ell$. Remark that we may perform: \[(x, y) \mapsto (x+y, |x-y|) \mapsto (2x, 2y)\]In particular, $(0, x) \mapsto (0, 2x)$, that is, as long as there's a zero in the tuple any arbitrary number in the tuple can be doubled. We dub this technique with the insightful name doubling.
Suppose we were able to reach $(2^x, 2^x, \dots, 2^x)$. Then \[(2^x, 2^x, \dots, 2^x) \mapsto (0, 2^{x+1}, 2^x, 2^x, \dots, 2^x) \mapsto (0, 2^{x+1}, 2^{x+1}, \dots, 2^{x+1}) \mapsto (2^{x+1}, 2^{x+1}, \dots, 2^{x+1})\]Hence, it suffices to show only that $(2^{\ell}, 2^{\ell}, \dots, 2^{\ell})$ is attainable from $(1, 2, \dots, n)$.
To this end, we induct on $n \geq 3$. Additionally, we'll also maintain that during the conversion, at some point a zero is observed. The base case $n = 3$ is easily handled, as seen: \[(1, 2, 3) \mapsto (2, 2, 4) \mapsto (0, 4, 4) \mapsto (4, 4, 4)\]Write $n = 2^{\ell}-m$ where $0 \leq m < 2^{\ell-1}$. Note that $\ell \geq 2$. If $m = 0$, we simply induct on $n-1$ and add in the $2^{\ell}$ already present. Thus we may assume $m \geq 1$. Note that $m < n$, $n \equiv m \pmod 2$ and that $2^{\ell-1}$ is the midpoint of interval $[m, n]$. We use the operation on the numbers $(2^{\ell-1}-i, 2^{\ell-1}+i)$ for $1 \leq i \leq n-2^{\ell-1}$. The tuple transforms: \[(1, 2, \dots, m-1, m, m+1, \dots, n) \mapsto \left(1, 2, \dots, m-1, 2, 4, \dots, 2\left(\frac{n-m}{2}\right), 2^{\ell-1}, 2^{\ell}, 2^{\ell}, \dots, 2^{\ell}\right)\]Now we do some casework.
$m \geq 4$ and $n-m \geq 6$. In this case, we can use the inductive hypotheses and scaling on the $(1, 2, \dots, m-1)$ and $(2, 4, 6, \dots, n-m)$ tuples to obtain \[(2^{\ell-1}, 2^{\ell-1}, \dots, 2^{\ell-1}, 2^{\ell-1}, 2^{\ell}, \dots, 2^{\ell}) \mapsto (0, 2^{\ell}, 2^{\ell-1}, \dots, 2^{\ell-1}, 2^{\ell}, \dots, 2^{\ell})\]Using the doubling and reverting back the zero, we would succeed in this case.
$m \geq 4$ and $n-m \leq 4$. Using the inductive hypotheses we convert the subtuple $(1, 2, \dots, m-1) \mapsto (2^{\ell-1}, 2^{\ell-1}, \dots, 2^{\ell-1})$. Next, \[(2, \dots, n-m, 2^{\ell-1}, 2^{\ell-1}, \dots, 2^{\ell-1}, 2^{\ell}, \dots, 2^{\ell}) \mapsto (2, \dots, n-m, 0, 2^{\ell}, 2^{\ell-1}, \dots, 2^{\ell-1}, 2^{\ell}, \dots, 2^{\ell})\]Using the doubling and remarking that each even term in $[2, n-m]$ is either $2$ or $4$ we can convert everything to $2^{\ell}$ (since $2, 4$ are powers of $2$ themselves).
$m \leq 3$ and $n-m \geq 6$
Imagine using the inductive hypotheses to convert $(2, 4, \dots, n-m) \mapsto (2^{\ell}, 2^{\ell}, \dots, 2^{\ell})$. As in the inductive hypotheses we must witness a zero at some point. At that point, we use the doubling to change the numbers in $[1, m-1]$ (if any) to $2^{\ell}$. Again, remark that only $1, 2$ will be present here, both of which are powers of $2$.
$m \leq 3$ and $n-m \leq 4$
We first have $n \leq 7$ and some inspection reveals this only corresponds to $n = 5, 6$. But for $5$ we have the conversion: \[(1, 2, 3, 4, 5) \mapsto (1, 2, 2, 4, 8) \mapsto (1, 0, 4, 4, 8) \mapsto (0, 8, 8, 8, 8) \mapsto (8, 8, 8, 8, 8)\]and for $6$ the conversion: \[(1, 2, 3, 4, 5, 6) \mapsto (1, 4, 3, 4, 5, 8) \mapsto (1, 4, 2, 4, 8, 8) \mapsto (1, 0, 2, 8, 8, 8) \mapsto (0, 8, 8, 8, 8, 8) \mapsto (8, 8, 8, 8, 8, 8)\]proving this case.
Combining the above cases, we've proven the inductive hypotheses, and consequently the problem is solved.
a1267ab
10.09.2023 15:19
Codeforces 1637G
Assassino9931
10.09.2023 18:15
RMM 2021/4 and many more.