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:
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.
|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]):
- All four numbers are even.
- Three numbers are even and one is odd.
- Two numbers next to one another are even, the other two are odd.
- Two numbers opposite one another are even, the other two are odd.
- One number is even, three are odd.
- 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
This is indeed the case. First of all, observe that, as it follows from the second proof for
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
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.
Ducci's problem has been further investigated for
N = 4and 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.
Chang and Sederberg consider iterations that start with two numbers: 0 and 1.
Winkler solves the cases of
N = 4and N = 5and mentions a story of a POW in WWII who entertained himself by trying iterations with different sequences of 4 integers.
The sequence of iterations produced by the algorithm is often called a Ducci sequence.
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 - athe iterations will necessarily diverge.
- A. Behn, C. Kribs-Zaleta, V. Ponomarenko, The Convergence of Difference Boxes, Am Math Monthly, v 112, n 5 (May 2005), pp. 426-439
- M. Lotan, A Problem in Difference Sets, Am Math Monthly, v 56, n 8 (Oct 1949), pp. 535-541
- G. Chang and T. W. Sederberg, Over And Over Again, MAA, 1997, pp. 32-44
- J. Cofman, What To Solve?, Clarendon Press, Oxford, 1996, Fourth printing
- M. Gardner, Riddles of the Sphinx, MAA, 1987, #29, p. 105, p.134, p.151, p.160
- R. Honsberger, Ingenuity in Mathematics, MAA, 1970
- D. O. Shklarsky, N. N. Chentzov, and I. M. Yaglom, The USSR olympiad problem book, Dover, 1993 (Reprint of W. H. Freeman, 1962.)
- P. Winkler, Mathematical Puzzles: A Connoisseur's Collection, A K Peters, 2004, p. 17 (Subtracting around the corner)