Integer Iterations on a Circle

Here is a problem:

Place 4 integers on a circle. Proceed in iterations. At every step, compute all differences of pairs of consecutive numbers. Place the absolute values of these differences between the corresponding numbers and remove the numbers themselves. Show that after performing the step several times all the numbers will become 0.

Here's a sample of two successive iterations:

Interger iterations on circle. Professor E. Ducci's observation

R. Honsberger refers to the problem as Professor E. Ducci's observation. The problem also appears in [Cofman] with a different solution (The latter has been probably taken from an old Russian collection by D. O. Shklyarsky, N. N. Chentsov, and I. M. Yaglom.) Note that, if indeed the state is reached where all the numbers became 0, it is obvious that on the previous step all the numbers had to be equal. The problem, therefore, can be reformulated as a request to show that the iterations always lead to a quadruple of equal numbers.

I shall later outline the two solutions and then pose a little more general problem whose solution is easily obtained by a means already available on these pages. But first there is an applet to experiment with. The number N of integers on the circle may be anywhere between 3 and 20. The applet may initialize the starting sequence to 0 or place some random numbers that I limit to the interval [0, 20]. In both cases, at any stage, you can modify the integers by clicking either immediately to the right (to increase the number) or to the left (to decrease the numbers) of its vertical center line. To perform the calculations press the "One Step" button.

Please try switching to IE 11 (Windows) or Safari (Mac), for no other browser nowadays runs Java applets. If asked whether to allow the applet to load, click Yes - the applet is signed with a security certificate from a trusted company. But, regardless, there is an explanation below.

Integer Iterations on A Circle II

What if applet does not run?

For N = 4, Honsberger shows that in four or fewer steps the largest number in a sequence must get smaller. Since we always deal with nonnegative numbers, the largest number will eventually become 0 and, with it, all other terms of the sequence will also vanish. If no terms are 0, the largest number will become smaller right away. But, if 0 is present, the largest number may pass on to the next step. To conclude the proof, Honsberger considers several cases of various distributions of 0 terms and verifies that, in all cases, 0s disappear in at most three steps.

Cofman also considers the case of N = 4 exclusively. She starts with 4 equal numbers and goes backwards. If the 4 equal numbers are even, the numbers on the previous step had to be either all odd or all even. If the 4 equal number are odd, the sequence on the previous step had to consist of two pairs of numbers of different parities. 6 cases are possible (these are also considered in [Shklarsky, Chentzov, Yaglom]):

  1. All four numbers are even.
  2. Three numbers are even and one is odd.
  3. Two numbers next to one another are even, the other two are odd.
  4. Two numbers opposite one another are even, the other two are odd.
  5. One number is even, three are odd.
  6. All four numbers are odd.

The transition diagram shows that the state 1 with all numbers even may be reached from other states in at most 4 steps. In other words, starting with an arbitrary quadruple of integers the process, in finite number of steps, leads to a quadruple consisting entirely of even numbers. We can apply the distributive law and consider only factors of those number obtained after division by two. This sequence too after a few iterations will consist of even numbers. Without the factoring, the numbers would be divisible by 4. Continuing this process, we see that for any power 2n of 2, all terms of the sequence will be divisible by 2n. Since, on no step the largest number of the sequence increases, to be divisible by any power of 2 the numbers must all be zero.

Is there anything special about the number 4? Do we always arrive at a sequence of all zeros starting with a sequence of arbitrary length N? For N = 2, the answer is obviously, yes. For N = 3, the no answer is as much obvious. Experimenting with the applet you will easily observe that, for N = 5, the sequences settle into a loop whose length is 3 or 6 depending on your point of view. You may or may not count as the same two sequences obtained from one another by sliding the numbers along the circle. For N = 6, there are two loops: of length 2 and 3 (with the same caveat as above.) Is anything provable here? For N = 8, one seems to always end up with 0. It appears plausible that the same is true whenever N is a power of 2.

This is indeed the case. First of all, observe that, as it follows from the second proof for N = 4, we may confine the allowed operations to addition modulo 2. (Since, modulo 2, 1 + 1 = 0.) Recollect how we used the superposition principle when looking into dot patterns and the relation between Pascal's and Sierpinski's triangles. Because of the superposition principle suffice it to consider starting sequences with a single nonzero term whose value is of no consequence either. So, when we start with a single 1 in the midst of zero terms, the situation (at least for a while) is analogous to the evolution of dot patterns that start with a single nonzero dot. From Lucas' theorem, except for the two extreme ones (which both are 1), all terms in the row 2n of Pascal's triangle are even. (This also follows from the induction argument applied to the dot patterns.) The total number of terms in the row 2n is 2n + 1. If we wrap this row on a circle with 2n positions, the two extreme terms will also add up to 0 modulo 2. Which proves our assertion for all powers of 2.

Since Lucas' theorem gives a necessary and sufficient condition for the elements on Pascal's triangle to be 0 modulo 2, we may claim that for no N other than the powers of two it is at all possible, starting with a single 1 and the rest of terms 0, to end up with a sequence consisting entirely of zeros. However, it is possible to start with several nonzero elements that would eventually lead to a zero sequence. The sequence 101010 gives such an example for N = 6. (The example easily extends for all even N. The example is due to Andrew Conner who found an error in the earlier version of the page. He has also suggested two other sequences whose iterations lead to the required sequence of zeros: 121210 and 123210.) In other cases iterations lead to a loop (a cycle) of nonzero sequences. The applet will, perhaps, help you discover what kind of loops are possible and what sequences may comprise those loops for various N.

Remark

  1. Moshe Lotan was apparently the first to consider the problem with real numbers. He found that, for N = 4, the iterations always converge, except when starting with numbers 1, q, q², q³ (and simple modifications of that sequence), where q is the only real solution of the equation x³ - x² - x - 1 = 0. (Being of odd degree the equation certainly has a real solution whose uniqueness follows from Descartes' Rule of Signs.) Lotan also proved that the convergence is not possible for N odd unless one starts with all numbers equal. His treatment has been popularized by M. Gardner.

  2. Ducci's problem has been further investigated for N = 4 and the starting numbers arbitrary reals. (By this time, the problem is known as "Difference boxes" and even as "Diffy boxes.") The author describe the decomposition of a parameters plane into regions of starting quadruples that converge in a given number of iterations.

  3. Chang and Sederberg consider iterations that start with two numbers: 0 and 1.

  4. Winkler solves the cases of N = 4 and N = 5 and mentions a story of a POW in WWII who entertained himself by trying iterations with different sequences of 4 integers.

  5. The sequence of iterations produced by the algorithm is often called a Ducci sequence.

  6. Ducci sequences formed for real numbers have been the subject of Greg Brockman's research submitted to the Intel Science Talent Search Competition where Greg received 6th place.

  7. The presence of the absolute value is essential. If the four numbers a, b, c, d are simply replaced with the differences a - b, b - c, c - d, and d - a the iterations will necessarily diverge.

References

  1. A. Behn, C. Kribs-Zaleta, V. Ponomarenko, The Convergence of Difference Boxes, Am Math Monthly, v 112, n 5 (May 2005), pp. 426-439
  2. M. Lotan, A Problem in Difference Sets, Am Math Monthly, v 56, n 8 (Oct 1949), pp. 535-541
  3. G. Chang and T. W. Sederberg, Over And Over Again, MAA, 1997, pp. 32-44
  4. J. Cofman, What To Solve?, Clarendon Press, Oxford, 1996, Fourth printing
  5. M. Gardner, Riddles of the Sphinx, MAA, 1987, #29, p. 105, p.134, p.151, p.160
  6. R. Honsberger, Ingenuity in Mathematics, MAA, 1970
  7. D. O. Shklarsky, N. N. Chentzov, and I. M. Yaglom, The USSR olympiad problem book, Dover, 1993 (Reprint of W. H. Freeman, 1962.)
  8. P. Winkler, Mathematical Puzzles: A Connoisseur's Collection, A K Peters, 2004, p. 17 (Subtracting around the corner)

|Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny

72083937