18
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – user207710 Jan 25 '15 at 19:51
  • 3
    $\begingroup$ 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. $\endgroup$ – user207710 Jan 25 '15 at 23:05
  • 4
    $\begingroup$ 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$. $\endgroup$ – Peter Košinár Feb 2 '15 at 0:18
  • 2
    $\begingroup$ 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. $\endgroup$ – Milo Brandt Feb 6 '15 at 1:35
  • 3
    $\begingroup$ 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. $\endgroup$ – Jyrki Lahtonen Feb 6 '15 at 17:30
3
+50
$\begingroup$

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)

def addpreds(a,b,c,val,d,queue):
  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]
    addpreds(a,b,c,val,d,queue)
    addpreds(b,c,a,val,d,queue)
    addpreds(c,a,b,val,d,queue)
    ix += 1
  return d
$\endgroup$
  • 3
    $\begingroup$ 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 $\endgroup$ – kong Feb 8 '15 at 15:40
  • $\begingroup$ Quite hard to find, due to different formulation. And the goal is defined different: You win the game when any two of the three stacks have the same number of cards, although the next move you can achieve a zero, which is a goal defined here. Detailed location: problem 5/1/23 at page 10 of the PDF file. $\endgroup$ – CiaPan Feb 16 '15 at 9:40
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.