POLYA024:  Long descent to zero (proposed by Li Zhou, 1/7/02).

Starting with positive integers a, b, c, and d, define f(a,b,c,d)=(|a-b|, |b-c|, |c-d|, |d-a|). It is well known [1, Chapter 1] that the iterations of f will always terminate at (0,0,0,0). For any m, can we always find (a,b,c,d) such that the iteration reaches (0,0,0,0) in more than m steps?

Discussion. [SCL, 1/8/02]: There is also a reference to this problem, I think in one of Honsberger's books. I'll look it up when I go into the office.
 Some obvious steps: (1) If there are no zeroes, the next iteration has maximum less than the current maximum
  (2) If there are four zeroes, you're done.
  (3) If there are three zeroes, you get     (a,0,0,0) -> (a,0,0,a) -> (a,0,a,0) -> (a,a,a,a) -> (0,0,0,0)
  (4) If there are two opposite zeroes (here, wlog, a>=c):   (a,0,c,0) --> (a,c,c,a) -> (a-c,0,a-c,0) -> (a-c,a-c,a-c,a-c) -> (0,0,0,0)
  (5) If there are two adjacent zeroes (here, wlog, a>=b):  (a,b,0,0) -> (a-b,b,b,a-b)  -> (e,0,e,0) -> (e,e,e,e) -> (0,0,0,0)    with  e=|a-2b|.
  (6) The case for only one zero, seems more involved.
  Still, what I remember doesn't give a proof that it takes only a few steps.
  ***************
  Here is an upper bound estimate of the number of steps:
  After at most four steps, all four of the numbers are even. (Just look at the problem modulo 2.)
  After at most four more steps, all four of the numbers are multiples of 4.
  After at most four more steps, all four of the numbers are multiples of 8.
  Since the maximum of numbers never increases, after at most 4*log(t) steps, the procedure terminates, where the log is to the base 2, and t=max{a,b,c,d}.
  ****************
  Now,  one can look for examples that take a lot of steps.
  For example, for four consecutive Fibonnaci numbers, I get seven steps, but I got a few better looking randonly.
[97, 60, 39, 11], [2, 35, 60, 94], [44, 1, 80, 62], [17, 29, 65, 3], [72, 61, 98, 81] take seven steps.
[35, 29, 88, 58], [59, 76, 99, 58], [32, 71, 6, 8] take 8 steps.
 [16, 77, 65, 50] takes 9 steps.
[50, 100, 93, 77], [23, 15, 11, 37], [30, 54, 97, 16], [95, 22, 62, 86], [56, 13, 19, 33], [55, 5, 96, 83] take 10 steps.
[16, 63, 87, 100] takes 11 steps.
[3, 74, 62, 41] takes 12 steps.
[50, 9, 84, 72] takes 13 steps.
[872, 648, 234, 996] takes 14 steps.
[732, 822, 265, 568], [279, 491, 881, 164] take 16 steps.

(Don't assume anything from my number of solutions at each size. After finding some of 10 steps, I then told it not to tell me about step-sizes I already knew.)
Anyway, I begin to suspect that one can get longer sequences. It might be possible to grow a sequence from (a,b,c,d) if there is some choice of signs so that a +/- b +/- c +/- d = 0, but even that might not be a guarantee.

[LZ, 1/8/02]: You are right, Stephen, there are arbitrarily long such sequences. The problem is not mine. Both parts appeared in the AMATYC Review a couple of years ago, proposed by Bill Leonard (Cal. State U., Fullerton, CA). But the published solution later didn't answer this second part of the question. My friend Nianqing Wang (Epic System, Madison, WI) came up with a nice way of getting arbitrarily long sequences, which I forwarded to the AMATYC Review. But to my amazement, the Solution Editor there failed to appreciate the question and completely ignored this solution.
You're also right about the conditions on a,b,c,d. Wang assumed a>b>c>d and a condition on a,b,c,d which satisfies yours. He then extended this one step back, while maintaining these conditions. We will then have a nice recursive growth formula.

[NW, 3/22/02]: Suppose that a>b>c>d, a=b+c+d, and it takes (a,b,c,d) n steps to descend to (0,0,0,0). Then (3b+2c+d,b+2c+d,b+d,b-d) will descend to (0,0,0,0) in n+1steps, and it satisfies 3b+2c+d>b+2c+d>b+d>b-d and the sum of the last three numbers is the first number again.
 
 

Bibliography. [1] Arthur Engel, Problem solving strategies, Springer.

Return to [Polya Home Page] [Members] [Problem Center] [Inventory] [Reserve Area]