Consider an integer \(n \ge 2\) and write the numbers \(1, 2, \ldots, n\) down on a board. A move consists in erasing any two numbers \(a\) and \(b\), then writing down the numbers \(a+b\) and \(\vert a-b \vert\) on the board, and then removing repetitions (e.g., if the board contained the numbers \(2, 5, 7, 8\), then one could choose the numbers \(a = 5\) and \(b = 7\), obtaining the board with numbers \(2, 8, 12\)). For all integers \(n \ge 2\), determine whether it is possible to be left with exactly two numbers on the board after a finite number of moves. Proposed by China
Problem
Source: RMM 2021/4
Tags: RMM 2021, combinatorics, board, RMM
14.10.2021 05:10
We claim that the answer is yes for every $n$. We use induction. The base cases $n=2,3,4,5,6,7,8,9,10$ are left to the reader as an exercise (10 is just a sufficiently large number). Suppose the statement is true for all numbers $\le m-1$. We show it is also true for $m$. Case 1: $m=4k$. Apply the move on $(1,4k-1),(3,4k-3),...,(2k-1,2k+1)$. The numbers become $2,4,6,8,10,...,4k$, all the even numbers between $2$ and $4k$. Using the algorithm for the $n=2k$ case, we can reduce this to two numbers. Case 2: $m=4k-1$. Apply the move on $(1,4k-1),(3,4k-3),...,(2k-1,2k+1)$. Similarly, the numbers become $2,4,6,8,...,4k$ and we are done by the inductive hypothesis. Case 3: $m=4k+1$. Apply the move on $(4,2k+1)$ to get the numbers $1,2,3,5,...,2k,2k+2,...4k+1$. Now apply the move on $(1,4k+1),(3,4k-1),(5,4k-3),...,(2k-1,2k+3)$. The numbers left are $2,4,6,...,4k+2$ and we are done by the induction hypothesis. (All the even numbers were not acted on, and 4 was added back with $(2k-1,2k+3)$. Case 4: $m=4k+2$. Apply the move on $(4,2k+1)$ to get the numbers $1,2,3,5,...,2k,2k+2,...4k+2$. Now apply the move on $(1,4k+1),(3,4k-1),(5,4k-3),...,(2k-1,2k+3)$. The numbers left are $2,4,6,...,4k+2$ and we are done.
14.10.2021 06:18
Let us show that any set of three elements can be reduced to two. Here's my proof of this fact: First, assume that in addition to the regular move we are also allowed to divide all three elements by the same integer power of 2. If two numbers on the board are $a$ and $b$, by applying the regular move to them twice we turn them into $2a$ and $2b$. This implies we can divide any even number from the board by two no matter what the other two numbers are. Then we proceed as follows: (1) divide each number by the maximum possible power of $2$ using the combination of moves described above; (2) if we end up with two equal odd numbers, we are done, otherwise, take any two of them, apply the regular move to them and divide both the sum and the difference by 2. Repeat (1) and (2) over and over. Both division by 2 and replacing $a$ and $b$ with $\frac{a+b}{2}$ and $\frac{|a-b|}{2}$ strictly decrease the total sum of the three elements, hence, sooner or later we will actually end up with two equal odd numbers. Now, if we run the same process except the part with divisions by powers of 2, we still end up with two numbers on the board because the regular move is invariant with respect to scaling. Finally, if we have any set of $n \ge 3$ elements, we can use the process above to reduce it to a set of $n-1$ or fewer elements (by applying it to any three numbers; note that some other numbers might be erased in the process). By applying this process repeatedly we can arrive at a set of $2$ elements as it is clearly impossible to get fewer than that.
14.10.2021 09:50
Cute. yes it is possible for every value of $n$. In fact, I will show that given any three numbers, we can reduce it to two, which will finish. I will do this by induction on the sum of the three numbers. The base cases are easy. First, note that by doing $a,b \rightarrow a+b, a-b \rightarrow 2a, 2b$, we can double any two numbers. Also note that we can scale the numbers so if they have a common gcd $> 1$, we can just divide through by it. So, we can also do $a,b,c \rightarrow 2a,2b,c \rightarrow 4a,2b,2c \rightarrow 2a,b,c$ so we can also just double any number. Now for the induction, not all are even otherwise induct, if there are $< 3$ odds, then just double them and then divide through the whole thing to get a smaller sum. So we may WLOG assume the numbers are all odd. But now we do $a,b,c \rightarrow a+b,a-b,c \rightarrow a+b, a-b, 2c \rightarrow \frac{a+b}{2}, \frac{a-b}{2}, c$, which has strictly smaller sum so again we're done by induction. The problem obviously now follows since we just pick three numbers and reduce them to two and repeat until we're left with only two.
14.10.2021 10:00
The whole heart of the problem is the following claim: Claim: For any triple of integers $(a,b,c),$ after some operations, we can eventually get to two numbers. For simplicity, let us call a triple good if we can eventually get to two numbers, and otherwise, call it bad. Proof: Assume that there exists at least one bad triple. Then, let $(m,n,p)$ be one of the bad triples with minimal sum. Before we begin to prove the claim, we will take a look at two rather easy observations, but which, in fact, are the motivation behind the whole solution: Observation 1: For any $a,b,c$ and $\lambda,$ the triple $(\lambda a,\lambda a,\lambda c)$ is good if and only if $(a,b,c)$ is good. This is trivial to observe, since we add and/or subtract our numbers, and hence the factor of $\lambda$ is conserved and hence, we can get rid of it. Observation 2: If a triple $(a,b,c)$ with even $c$ is bad, then $(a,b,c/2)$ is bad. Simply operate on $a,b$ (assume that $a>b$) to get $(a-b,a+b,c)$ and then on $a-b$ and $a+b$ again to get $(2a,2b,c).$ Since $(a,b,c)$ is bad, then so is $(2a,2b,c).$ Now, since $c$ is even, by observation 1, $(a,b,c/2)$ must be bad too. Coming back to $(m,n,p),$ by pigeonhole, let $m\equiv n\pmod{2}$ and let $n>m.$ Then, operate on $n$ and $m$ to get $(n-m,n+m,p).$ Since $(m,n,p)$ is bad, $(n-m,n+m,p)$ is also bad, so using observation 2, we can deduce that $\big((n-m)/2,(n+m)/2,p\big)$ is bad. But the latter triple has a sum of $n+p<n+m+p$ which contradicts the minimality of $(m,n,p).$ Hence, our claim is proven. $\square$ Now, coming back to the problem itself, let us induct on $n$. Clearly, for $n=2$ we already have $2$ numbers so everything is ok. Assume the problem holds for $n$. Then, simply do the operations to get $1,2,...,n$ to two numbers in the case $n+1$ and, in the end, we might get two numbers ($n+1$ might be a duplicate at some operation and might be erased) which is good, or we might get three numbers, from which we can still get to two numbers, by our claim. Hence, for any $n,$ we can reach two numbers. $\square$
14.10.2021 16:32
The goal is possible for every value of $n$. The proof goes by induction on $n \ge 2$. The base cases $n=2,3,4,5,6$ can be checked by hand. For the inductive step, assuming $n \ge 7$: If $n=4k+3$ or $n=4k+4$, then operate on pairs $(1,4k+3)$, $(3,4k+1)$, \dots, $(2k+1,2k+3)$. The numbers remaining are $\{2,4,6,\dots,4k+4\}$. One may then halve all the numbers and proceed by induction as $2k+2 < n$. If $n=4k+1$ or $n=4k+2$, first operate on the pair $(4,2k+1)$, then operate on pairs $(1,4k+1)$, $(3,4k-1)$, \dots, $(2k-1,2k+3)$. The numbers remaining are $\{2,4,6,\dots,4k+2\}$. One may then halve all the numbers and proceed by induction as $2k+5 < n$.
16.10.2021 04:11
v_Enhance wrote: If $n=4k+1$ or $n=4k+2$, first operate on the pair $(2,2k+1)$, then operate on pairs $(1,4k+1)$, $(3,4k-1)$, \dots, $(2k-1,2k+3)$. The numbers remaining are $\{2,4,6,\dots,4k+2\}$. One may then halve all the numbers and proceed by induction as $2k+1 < n$. [/list] Sorry to clarify, but aren't the numbers remaining $4,6,...,4k+2$? (This is the reason for me using $(4,2k+1)$ in my solution instead of $2$ but maybe I was mistaken).
16.10.2021 06:22
Nope, you're right. My mistake.
16.10.2021 11:23
v_Enhance wrote: [*]If $n=4k+1$ or $n=4k+2$, first operate on the pair $(4,2k+1)$, then operate on pairs $(1,4k+1)$, $(3,4k-1)$, \dots, $(2k-1,2k+3)$. The numbers remaining are $\{2,4,6,\dots,4k+2\}$. One may then halve all the numbers and proceed by induction as $2k+1 < n$. [/list] The cases $n=5,6$ need to be checked separately since $2k+5>n$ in this case.
22.10.2021 21:40
The answer is yes for all \(n\). Say a triple is irreducible if it may be reduced to two. I contend no triple of distinct positive integers is irreducible, which will suffice. First, observe that in an irreducible triple \((a,b,c)\), if \(a\) is even, then \((a,|b-c|,b+c)\) is irreducible, so \((a,2b,2c)\) is irreducible, and thus \((\frac12a,b,c)\) is irreducible. Now consider the irreducible triple \((a,b,c)\) that minimizes \(a+b+c\). If without loss of generality \(a\) and \(b\) have the same parity, then \((|a-b|,a+b,c)\) is irreducible, so \((\frac12|a-b|,\frac12(a+b),c)\) is irreducible. But \[\tfrac12|a-b|+\tfrac12(a+b)+c=\max\{a,b\}+c<a+b+c,\]contradiction.
20.12.2021 07:12
The answer is yes. We claim that any triple of integers can be reduced down to two, which solves the problem. Assume FTSOC that $(a,b,c)$ is a triple that can't be reduced to two and minimizes the quantity $a+b+c$. Notice that scaling the triple by any constant preserves if it is irreducible. WLOG let $b,c$ have the same parity; if they are both odd, then $\left(\frac{a}{2},\frac{b+c}{2},\frac{|b-c|}{2}\right)$ is irreducible with a smaller sum, and if they are both even, then $\left(a,b,\frac{c}{2}\right)$ is irreducible with a smaller sum.
13.02.2024 22:49
We strong induct on $n \ge 2$, with the base case $n=2$ trivial. Suppose that the $n+1$ case is given. Then operate on the numbers $1$ through $n$ only, and if the $n+1$ exists after the operation, then the result will be a triple of integers. (If $n+1$ does not exist at the end, then the induction is complete.) We define the function $f$ on triples of integers $(a, b, c)$ so that $f(a, b, c)$ is $1$ if $(a, b, c)$ can be reduced to two numbers and $0$ otherwise. Our goal is to prove that $f$ is always $1$. First, note that if $a$ is even, then \[ f(a, b, c) = f(a, |b-c|, b+c) = f(a, 2b, 2c) = f(a/2, b, c). \]Repeating this sequence of steps iteratively, we have that $f(a, b, c)=f(a/2^{\nu_2(a)}, b, c)$. In particular, we can assume that $a$, $b$, and $c$ are all odd, and if we ever attain an even number, then we can delete all of its factors of $2$. Assume for contradiction that $f(a, b, c)=0$. We minimize the sum $a+b+c$ over all such tuples. WLOG $a<b$. Since $a$ and $b$ have equal parity, we can operate on them, which changes the sum to \[ \frac{|a-b|}{2} + \frac{a+b}{2} + c = a+c < a+b+c, \]a contradiction to minimality. Thus $f(a, b, c)=1$ for all triples $(a, b, c)$, completing the inductive step.
11.12.2024 19:55
The answer is all $n$. We claim that, as long as there are at least three numbers remaining, we can always get rid of a number. We will give an algorithm that will reduce the number of numbers on the board. Assume we don't "accidentally" repeat a number, since in that case the algorithm will succeed anyways. First, we will define the following moves: Move 1 (doubling two numbers): Replace $a$ and $b$ with $2a$ and $2b$. To do this, simply preform two moves consecutively on $a$ and $b$. Move 2 (ratio simplification): As long as there are at least three numbers on the board, we can take two numbers $a\neq b$ on the board and perform a series of moves that simplfies their ratio (meaning $\frac{a}{b}=\frac{m}{n}$ with $\gcd(m,n)=1$, then we decrease $m+n$). If $v_2(a)\neq v_2(b)$, say WLOG $v_2(a)<a_2(b)$, then we can simplify the ratio by using Move 1 to double $a$ (together with some number that isn't $b$). Otherwise, if $v_2(a)=v_2(b)$, we claim that performing a move on $a$ and $b$ also simplfies their ratio. Let $a=2^k\cdot g m$ and $b=2^k\cdot gn$ such that $g,m,n$ are all odd and $\gcd(m,n)=1$. Then, $$\frac{a-b}{a+b}=\frac{m-n}{m+n}.$$However, because $m-n$ and $m+n$ are both even, we can at least factor out a $2$, so the new sum of numerator and denominator is at most $m$. However, the original was $\frac{m}{n}$ which had a sum of $m+n$, so we simplified the ratio. Thus we continue simplifying the ratio until we finally have $a=b$, in which case we will have decreased the number of numbers on the whiteboard. We are done.