Cut the knot: learn to enjoy mathematics
A math books store at a unique math study site. Learn to enjoy mathematics.
Google
Web CTK
Terms of use
Privacy Policy

More Mathematics
CTK Exchange

Games to Relax
Guest book
Recommend this site

Sites for teachers
Sites for parents

Manifesto: what CTK is about Buying a book is a commitment to learning Things you can find on CTK Email to Cut The Knot Recommend this page

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.

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.

<hr> <h3> This applet requires Sun's Java VM 2 which your browser may perceive as a popup. Which it is not. If you want to see the applet work, visit Sun's website at http://www.java.com/en/download/index.jsp, download and install Java VM and enjoy the applet. </h3> <hr>

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. To obtain 4 equal numbers, the numbers on the previous step had to be either all odd or all even. Where they were odd, on the previous step, the sequence had to consist of two pairs of numbers of different parities. 6 cases are possible:

  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 to end up with a sequence consisting entirely of zeros unless, of course, one starts with such a sequence or a sequence with all terms equal. In all other cases, iterations always lead to a loop (a cycle) of nonzero sequences. The applet, perhaps, will help you discover what kind of loops are possible and what sequences may comprise those loops for various N.

Remark

  1. Ducci's problem has been investigated for N = 4 and the starting numbers arbitrary reals. Curiously, real iterations always converge in a finite number of steps, except for one case, where they converge to a unique fixed point of the R4 transformation defined by Ducci's iterations. In this setting, the problem is known as "Difference boxes" and even as "Diffy boxes."

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

  3. 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.

  4. The sequence of iteration produced by the algorithm is often called a Ducci sequence.

  5. 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.

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. G. Chang and T. W. Sederberg, Over And Over Again, MAA, 1997, pp. 32-44
  3. J. Cofman, What To Solve?, Clarendon Press, Oxford, 1996, Fourth printing
  4. R. Honsberger, Ingenuity in Mathematics, MAA, 1970
  5. P. Winkler, Mathematical Puzzles: A Connoisseur's Collection, A K Peters, 2004, p. 17 (Subtracting around the corner)

Copyright © 1996-2008 Alexander Bogomolny



Search:
Keywords: