Fall 2016, problem 32

Written on a blackboard are $n$ nonnegative integers whose greatest common divisor is $1$. A move consists of erasing two numbers $x$ and $y$, where $x\ge y$, on the blackboard and replacing them with the numbers $x-y$ and $2y$. Determine for which original $n$-tuples of numbers on the blackboard it is possible to reach a point, after some number of moves, where $n-1$ of the numbers on the blackboard are zeroes.

Comments

Anonymouse

4 years ago

A partial solution is that it is necessary that the sum of the numbers be a power of two. Consider the game in reverse, where moves consist of taking 2x and y and replacing them with x and x+y. If our list of numbers has any common divisors other than 2 before a move, it will still have those divisors afterwards, so if we start with only one nonzero number and eventually get to a list with no common divisors, then the nonzero number was a piwer of 2. Since the total sum of the elements in our list is constant, the result follows.

The necessary condition is in fact also sufficient. Let us firstly point out some remarks.

We will always assume that the sum is a power of 2.
In particular the number of odd terms must be even.
If, after some moves, all terms are even, we can work with the "halved" board. In fact, if a sequence of moves solves the problem corresponding to the halved board, the same sequence applied to the original board solves the true problem.
We will work by induction on $M$, the maximum of the values appearing on the board. The base case ($M=1$) is quite trivial: if $M=1$, because of remark 2, the non vanishing elements are $2p$ elements all with value 1; replacing any couple $(1,1)$ with a couple $(0,2)$ we end up with only $2(p-1)$ non vanishing elements all with value 2. After applying remark 3 we are back with the original problem with $p$ replaced by $p-1$. Step by step we finish with a single couple $(0,1)$ that becomes $(2,0)$.

In order to prove the inductive step, let us call "strategy" the family of moves defined by:

if all element are even, we half the board;else:
we list the odd elements in decreasing order, $O_1\ge O_2\ge\dots,\ge O_{2p}$ (see remark 2). Then we replace $(O_1,O_2)$ by $(O_1-O_2,2O_2)$, $(O_3,O_4)$ by $(O_3-O_4,2O_4)$ and so on. All the newly generated numbers are even, as well as the untouched entries; so that we can apply remark 3.

CLAIM: starting from a board with maximum $M$ where there are $NV$ non-vanishing elements, after applying the strategy we end up with a board whit a maximum $M'\le M$; and, if $M'=M$, the new number $NV'$ of non vanishing elements is strictly less than $NV$.

Of course the claim is sufficient to prove the induction step. when $M' \le M$ we are done; if instead $M'=M$ we continue to apply our strategy until $M' \le M$ or $NV'=2$, In this last case the element will have the same parity (remark 2) thus applying one more time the strategy we end up with a smaller value for $M$ or just one number as required.

Finally, let us prove the claim. The maximum cannot incease because $O_{2j+1}-O_{2j+1} \le O_{2j + 1}$ and $2O_{2j + 2}$, after halving, is $O_{2j + 2}$; and the even terms obiously cannot increase. Furthermore: if the maximun $M$ is odd, it must coincide with the value noted $O_1$; we can assume $O_1>O_2$ otherwise the generated element $O_1-O_2$ vanishes; thus the maximum anong the newly generated elements, after halving, is $O_2$ that is less than $O_1=M$; and the even elements have a lesser maximum. If, on the contrary, $M$ is even, the odd elements are less than $M$ as well as the halved newly generated ones; and the halved even elements.

Claudio 4 years ago