# Is it true that we can get zero for all $(x,y,z)\in\mathbb{N}^3$?

There are three distinct positive integers $x$, $y$, and $z$.

We can choose two numbers $a,b\in\{x,y,z\}$, where $b\leq a$,

then replace $b$ by $2b$ and replace $a$ by $a-b$.

Is it true that there exists a method to repeat this process until we get a zero ?

For example, let $(x,y,z)=(3,5,10)$, then $(3,5,10)\rightarrow (6,2,10) \rightarrow (4,4,10) \rightarrow (\mathbf{0},8,10)$.

Let $(x,y,z)=(9,11,2)$, then $(9,11,2)\rightarrow (18,2,2) \rightarrow (18,\mathbf{0},4)$.

Is it true that we can get zero for all $(x,y,z)\in\mathbb{N}^3$ ?

Thanks.

thank you everyone. Now I found that this is problem from IMO 1994 and USAMT 23. Here is solution usamts.org/Solutions/Solutions_23_1.pdf

• This generally does not hold for 2-tuples, but I can't see what makes it so. We can easily see that for (x,y) in N^2, if one of these is double the other, then we can't reach a zero (assuming the x and y are not zeros). But what about other cases like (13,10)? I think that if we can precise the conditions which make this true for 2-tuples, we can solve the problem. – user207710 Jan 25 '15 at 19:51
• I found that if we are dealing with a 2-tuple, say (x,y), then this is solvable if and only if WLOG y is a multiple of x, say y = nx, and there is a non-zero k for which n = 2^(k + 1) - 1. – user207710 Jan 25 '15 at 23:05
• If $(x,y)$ can be transformed to reach zero, $x$ and $y$ have the same parity (alex' observation). Since $(x,y)$ behaves just like $(\frac{x}{\gcd(x,y)},\frac{y}{\gcd(x,y)})$, we can assume both $x$ and $y$ to be odd. Applying the transformation turns both of them even. Dividing by two and repeating the same reasoning again eventually terminates with pair $(1,1)$ (the only pair of equal integers with no common factor). Since we divided the initial two values first by their greatest common divisor and then (repeatedly) by $2$, their sum divided by the $\gcd$ must be a power of $2$. – Peter Košinár Feb 2 '15 at 0:18
• If $2$ generates the multiplicative group mod prime $p$, then we can solve this problem mod $p$. Since we can change $(a,b,c)$ to $(2^n a,b-2^n a + a,c)$ but if $2^n$ can be any $\alpha$ by hypothesis, we get to $(\alpha a,b-(\alpha - 1)a,c)$. Unless $b=2a$, it is possible for non-zero $\alpha$ to get a $0$ at $b$. So, unless $x=2y$ for every pair (which is impossible mod an odd prime), this gets us to a triple with $0$ in it. – Milo Brandt Feb 6 '15 at 1:35
• A possibly easier argument for pairs is to do it as follows. Let $n=a+b$, and work inside the ring of integers modulo $n$. Because $a\equiv -b\pmod n$ always, we see that a move replaces a set of the form $\{\overline{b},\overline{-b}\}\subset \Bbb{Z}_n$ with $\{\overline{2b},\overline{-2b}\}$. In other words, when viewed modulo $n$, all the moves are just multiplications by two. We terminate at zero, iff the (additive) order of $\overline{b}$ modulo $n$ is a power of two, which is equivalent to the condition by Ahmed Hussein and Peter Košinár. – Jyrki Lahtonen Feb 6 '15 at 17:30

In the absence of a proof, I'll give some more numerical evidence for the conjecture. The Python code below computes the "depth" of each triple $(a,b,c)$ with a given sum, where the depth is the minimum number of moves required to make two of the three numbers equal. (A triple where no two numbers can be made equal would have depth $-1$.) I've verified the conjecture for all $a+b+c\le2000$. I also looked at the triples that set new depth records... a partial table is below.

$$\begin{array}{c|c|l} {\text{depth}} & {\text{min }} a+b+c & {\text{triple(s)}} \\ \hline 5 & 27 & (5,9,13)^* \\ 6 & 45 & (4,15,26)^* \\ 7 & 81 & (8,27,46)^* \\ 8 & 105 & (27,35,43)^*,(8,35,62)^*,(8, 27, 70) \\ 9 & 195 & (8,57,130),(8,65,122)^*,(4,33,158),\ldots \\ 10 & 329 & (4,130,195) \\ 11 & 597 & (175,199,223)^* \\ 12 & 885 & (101,295,489)^* \\ 13 & 1425 & (206,475,744)^* \end{array}$$

At least one interesting fact stands out: almost all of these "most difficult" triples are arithmetic progressions of the form $(a-k,a,a+k)$ (these are indicated by asterisks). Also, the size of $a+b+c$ grows in a rough Fibonacci-like pattern. Looking at these examples, one might conjecture that the next record will occur around $885+1425=2310$.

Update: After running the code for a while longer, the next record comes later than expected, at

$$\begin{array}{c|c|l} {\text{depth}} & {\text{min }} a+b+c & {\text{triple(s)}} \\ \hline 14 & 2793 & (571, 931, 1291)^*. \end{array}$$ Also, the conjecture is now verified for $a+b+c\le 3000$.

def srt(i,j,k):
a = min(i,min(j,k))
c = max(i,max(j,k))
b = (i+j+k)-(a+c)
return (a,b,c)

def setdepth(i,j,k,val,d,queue):
key = srt(i,j,k)
if d.has_key(key) and d[key]>=0: return
d[key] = val
queue.append(key)

if a%2==0:
setdepth(a/2,b+a/2,c,val+1,d,queue)
setdepth(a/2,b,c+a/2,val+1,d,queue)

def depths(n):
d = {}
queue = []
for i in xrange(1,n+1):
for j in xrange(1,n+1):
k = n-(i+j)
if i+j<n and i!=j and i!=k and j!=k: d[srt(i,j,k)] = -1
if 2*i<n: setdepth(i,i,n-2*i,0,d,queue)
ix = 0
while ix<len(queue):
key = (a,b,c) = queue[ix]
val = d[key]

I wrote a Delphi program which checked that each triple $(x,y,z)$ such that $6\le x+y+z\le 100$ is reducible to a triple with a zero. You can download the program and its results here.