On a board the numbers $(n-1, n, n+1)$ are written where $n$ is positive integer. On a move choose 2 numbers $a$ and $b$, delete them and write $2a-b$ and $2b-a$. After a succession of moves, on the board there are 2 zeros. Find all possible values for $n$. Proposed by Andrei Eckstein
Problem
Source: Romanian "Stars of Mathematics" Junior 2019 P3
Tags: combinatorics proposed, combinatorics
alexiaslexia
31.12.2020 06:46
$\boxed{\text{Answer = }3^k.}$ In this problem, I claim that size and order of the numbers really do matter, and for that, I will represent the triple generated after the $k^{th}$ move as $(a_k,b_k,c_k)$ with $a_k \leq b_k \leq c_k$ --- where the initial triple $(a_0,b_0,c_0)$ is equal to $(n-1,n,n+1)$. Call the move between $a_k$ and $b_k$ to be a $\textit{left}$ move, $b_k$ and $c_k$ to be a $\textit{right}$ move, finally, the move between $a_k$ and $c_k$ to be an $\textit{endpoint}$ move. As a result, a move which transfers a triple $(a_k,b_k,c_k)$ to $(a_{k+1},b_{k+1},c_{k+1})$ can be classified as one of the three above categories. We will start with two claims. $\color{green} \rule{25cm}{2pt}$ $\color{green} \textbf{\text{Claim 1: A broader parity.}}$ Let $D|b_k-a_k$ and $D|c_k-b_k$. Then, \[ (a_k,b_k,c_k) \equiv (a_{k+1},b_{k+1},c_{k+1}) \pmod D \]$\color{green} \textbf{\text{Proof 1.}}$ Just note that if $a \equiv b \equiv c \pmod D$, then $2a-b = a+(a-b) \equiv a \pmod D$. Then, any combination of moves will not change (their) modulo $D$ class. $\color{green} \textbf{\text{Claim 2: Possible End-result.}}$ For any nonnegative triple $(a_0,b_0,c_0)$ which may not necessarily be in the form $(n-1,n,n+1)$, if $(a_k,b_k,c_k) = (0,0,N)$ for some $k$, then $3|N$. $\color{green} \textbf{\text{Proof 2.}}$ Consider the last move which transforms $(a_{k-1},b_{k-1},c_{k-1})$ into $(a_k,b_k,c_k)$. We can sneakily eliminate the possibility of a left move or an endpoint move, as it would imply that \[ (a_{k-1},b_{k-1},c_{k-1}) = (0,0,N) \ \text{or} \ (a_{k-1},b_{k-1},c_{k-1}) = (\text{positive},0,\text{positive}) \]On the other hand, a right move would imply that \[(a_{k-1},b_{k-1},c_{k-1}) = \bigg(0,\dfrac{N}{3},\dfrac{2N}{3}\bigg) \]ensuring that $N = 3 \cdot N'$ for some $N'$. $\blacksquare$ $\color{red} \rule{25cm}{2pt}$ $\color{red} \textbf{\text{Finishing.}}$ Let, before doing anything else, $E$ endpoint moves have commenced. Then, $(a_E,b_E,c_E) = (n-3^E,n,n+3^E)$. We divide into two cases here. Case 1. $a_E \leq 0.$ After this point onwards (when $k \geq E$), $\min(a_k,b_k) = a_k \leq 0$, with any further left or endpoint move further pushing $a_{k \geq E}$ to be more negative. As the only feasible case left is when $a_E = 0$, with all further moves being right moves, we can infer that $n = 3^E$, where it would take us a mere right move to transform \[ (a_E,b_E,c_E) = (n-3^E,n,n+3^E) = (0,3^E,2\cdot 3^E) \ \text{to} \ (a_{E+1},b_{E+1},c_{E+1}) = (0,0,3^{E+1}) \] Case 2. $a_E > 0.$ By $\color{green} \textbf{\text{Claim 1}}$ with $D = 3^E$, the values of triples' terms after the $E^{th}$ move will remain constant. If they are unequal to $0$, they will never reach $0$ mod $3^E$, let alone being truly zero. Therefore, $D$ must also divide $n$. Now we let $n = 3^E \cdot k$ to obtain \[ (a_E,b_E,c_E) = (3^E \cdot (k-1),3^E \cdot k, 3^E \cdot (k+1)) \]Seeing the abundance of $3^E$ factors here, we can divide $a_E,b_E,c_E$ by their gcd and instead operate in \[ (a_k',b_k',c_k') = \bigg(\dfrac{a_k}{3^E},\dfrac{b_k}{3^E},\dfrac{c_k}{3^E} \bigg) \]As the next move cannot again be an endpoint move, it must be either a left or right move. $\color{red} \rule{25cm}{2pt}$ If it is a left move, the triple $(k-1,k,k+1)$ becomes $(k-2,k+1,k+1)$. Seeing that $3$ divides $b_k-a_k$ and $c_k-b_k$ again, we can let $k = 3l+2$ and divide by $3$ to yield the triple $(l,l+1,l+1)$. By $\color{green} \textbf{\text{Claim 2}}$, setting a new $(a_0,b_0,c_0)$ equal to this triple, then it follows that this triple cannot have $(0,0,N)$ as its descendant. The same goes with the other case, where a right move is performed, but with the setting $(a_0,b_0,c_0) = (l,l,l+1)$ instead. $\blacksquare$ $\blacksquare$ $\blacksquare$
This is the type of problem where a seasoned veteran may take a long time to process, where a beginner with a more down-to-earth mindset may have the advantange. The more advanced theories or invariants you may come up with, the more you would get lost here. Fortunately, the description of this problem's source prevented me to venture towards more sophisticated methods --- hence, this is the best place to showcase my own most-shared advice:
\[ \begin{tabular}{p{12cm}}
Never treat an easy problem as if you were doing a hard problem, and never treat a hard problem as if you were doing an easy one.
\end{tabular} \\ \]\[\begin{tabular}{p{12cm}}
$\rule{4cm}{0.5pt} \hspace{1cm} \bigstar \hspace{1cm} \rule{4cm}{0.5pt}$ \\
\end{tabular} \\ \]Experimenting to victory, here's a quick recap of my discoveries:
\[ \begin{tabular}{c|c|c|c|c|c}
$n=1$&$n=2$&$n=3$&$n=4$&$n=5$&$n=6$ \\ \hline
$012$&$123$&$234$&$345$&$456$&$567$ \\
$003$&$114$&$036$&$147$&$258$&$369$ \\
&$1,-2,7$&$009$&$-2,7,7$&$2,2,11$&$099\text{?}$ \\
\end{tabular} \]And that it seemed that the endpoint moves are the best moves to boot. However, seeing the prevalence of the number $3$ in this problem, I wondered why $n=6$ doesn't guarantee the existence of a $(0,0,N)$ triple. Sure, an endpoint move would reduce it to the case $n = 2$, but otherwise?
Since the simplest moves are the endpoint ones, I observed the moves' behaviors for arbitrary $n$ as follows:
\begin{align*} (n-1,n,n+1) &\Rightarrow (n-3,n,n+3) \Rightarrow (n-6,n+3,n+3) \Rightarrow (n-15,n+12,n+3) \\ &\Rightarrow (n-15,n+21,n-6) \Rightarrow (n-24,n+21,n+3) \end{align*}This difference analysis alone (I called it this way, as we're not technically seeing what numbers can arise from the moves, but only their relation with each other: $n-24$ has a $27$ difference from the second lowest term $n+3$, and the second lowest term has difference $18$ from the highest term. Altogether, these set of differences can be expressed as $(n-24,n+3,n+21)$.) has important conclusions to pull, as
the later differences must all be a multiple of $3$, even by $9$;
the lowest number must decrease every turn (meaning the game would definitely end in finitely many turns);
Say, when $n = 24$, some tricks must be pulled on the remaining terms $n+3$ and $n+21$ (i.e. $27$ and $48$) so that they will eventually form another zero after that point.
\[\begin{tabular}{p{12cm}}
$\rule{4cm}{0.5pt} \hspace{1cm} \bigstar \hspace{1cm} \rule{4cm}{0.5pt}$ \\
\end{tabular} \\ \]Then, the two Claims can be succinctly formulated. The remaining problem still lingers: after a (finite) number of endpoint moves, how will we manage to eliminate the pesky pests ($n \ne 3^E$, where $E$ is equal to the number of endpoint moves performed initially) out of the picture? Still, an application of the Claims bothered me when I did this problem: when the triple is in the following form:
\[ (a_E,b_E,c_E) = (3^E \cdot (k-1),3^E \cdot k, 3^E \cdot (k+1)) \]the audacious Conjecture that $n = 3^E$ is the only solution implies that for any triple $(k-1,k,k+1)$, any application of a right or left move would immediately terminate the triple's viability. This meant that any $(k-2,k+1,k+1)$ or $(k-1,k-1,k+2)$ must be unviable --- and here, again, I noticed the strange difference set being $(3,0)$ and $(0,3)$. What could this difference guarantee, then?
\[\begin{tabular}{p{12cm}}
$\rule{4cm}{0.5pt} \hspace{1cm} \bigstar \bigstar \hspace{1cm} \rule{4cm}{0.5pt}$ \\
\end{tabular} \\ \]Here, I spent the longest time speculating on what the mysterious invariant could've been. First, I considered $(a_k,b_k,c_k) = (x,x+d_1,x+d_1+d_2)$ and analyzed the differences $(d_1,d_2,d_1+d_2)$ mod 3, but this premise hinged on the fact that differences are easily categorized --- in which the numbers $(a_k,b_k,c_k)$ can swap positions arbitrarily when it is transformed into $(a_{k+1},b_{k+1},c_{k+1})$.
Next idea was directly trying to substitute $k$ into $(k-2,k+1,k+1)$ which yielded $(5,8,8)$ when $k = 7$ --- and here I realized that $k$ must be in the form $3k+2$ to ensure that the terms are all $0$ mod $3$. Next, I tried to consider the aftermath of the triple $(l,l+1,l+1)$, of which its only possibility is to become $(l-1,l+1,l+2)$. Seeing that $l = 4$ looked nice because $l-1 \equiv l+2 \pmod 3$, I quickly catched on that any process the triple went through:
\begin{align*} (3,5,6) &\Rightarrow (1,7,6) \Rightarrow (1,5,8) \\ &\Rightarrow (1,2,11) \Rightarrow (0,3,11) \end{align*}must result in a triple with 2 odd numbers, which is taboo if we were to create two zeroes (which are even). I then tried with $l = 7$, which created two multiple of threes and two even numbers, but the best I could do is to pull out $(-8,0,31)$ from the triple $(6,8,9)$.
A final desperate attempt was working backwards: the objective of the problem statement (now) is to transform $(k,k+2,k+3)$ into $(0,0,3k+5)$. Again, I tried to consider invariants: when $k=7$, the starting point is of $``\text{class}" (1,0,1)$, and I wanted it to end in $(0,0,2)$ --- which doesn't seem to contradict anything. However, I got reaaallly close when I transformed $(7,9,10)$ into $(0,9,17)$ --- if only a $(0,9,18)$ is attainable! Then, it clipped my mind: what if a $(0,0,3k+5)$ cannot be attained from any position: and that it has no preimage of any kind?
Turns out that a sum invariant is all I needed, specifically, a $(0,0,N)$ must require $N$ to be a multiple of $3$ to be a descendant of some other triple.
\[\begin{tabular}{p{12cm}}
$\rule{4cm}{0.5pt} \hspace{1cm} \blacksquare \hspace{1cm} \rule{4cm}{0.5pt}$ \\
\end{tabular} \\ \]Final Comments: Nothing grandiose to say here. In summary, since it seems that this is too simply structured to warrant a detailed overview, I would say that the first section is a soft tech which highlights the importance of a systematic bash, the second section is an old hard tech which permits the solver to divide the terms of a sum/difference-based operation by its GCD (and also the constant-modulo invariant is important), and the final section is how to look backwards for an observation. In total, this is a fair medium 20M problem.