Given a sequence of eight integers $x_{1},x_{2},...,x_{8}$ in a single operation one replaces these numbers with $|x_{1}-x_{2}|,|x_{2}-x_{3}|,...,|x_{8}-x_{1}|$. Find all the eight-term sequences of integers which reduce to a sequence with all the terms equal after finitely many single operations.
Problem
Source: 4-th Taiwanese Mathematical Olympiad 1995
Tags: combinatorics unsolved, combinatorics
youxia2
04.06.2014 06:21
It's Ducci Sequence http://en.wikipedia.org/wiki/Ducci_sequence
McTeague
04.02.2019 02:28
Since the wikipedia page on Ducci sequence doesn't seem to give an explicit solution, I will provide one. A few initial observations: All entries are always integers and after the first operation, all entries are nonnegative. From $(1)$, from the second 8-tuple onward, the maximum entry is non-increasing over successive operations. The $8$-tuples ends up with all the same entries at some point iff it eventually ends up as an $8$-tuple of all $0$s. If after some number of operations we have a sequence of $(a_1, a_2, \ldots, a_8)$ of the form $(kb_1, kb_2, \ldots, kb_8)$ for integers $k, b_1, b_2, \ldots, b_8,$ then the $8$-tuple can be reduced to $(b_1, b_2, \ldots, b_8)$ and this new $8$-tuple eventually ends up as all $0$s iff the old one does. When viewed $\pmod 2$, the operation is equivalent to applying $(x_1, x_2, \ldots, x_8) \pmod 2 \to (x_1+x_2, x_2+x_3, \ldots, x_8+x_1) \pmod 2$. From $(3)$ it suffices to show that the entries all eventually end up as $0$. Proceed by induction on the maximum entry $m$ in the $8$-tuple resulting from a single operation. This method is legal due to $(1)$ and $(2)$. As a base case, with $m = 0$ we are already done. Consider $m = k > 0$ and assume the claim follows for all nonnegative integers less than $k$. From $(5)$, we observe the following for successive operations $\pmod 2$: \begin{align*} (x_1, x_2, \ldots, x_8) &\to (x_1+x_2, x_2+x_3, \ldots, x_8+x_1)\\ &\to (x_1+x_3, x_2+x_4, \ldots, x_8+x_2)\\ &\to (x_1+x_2+x_3+x_4, x_2+x_3+x_4+x_5, \ldots, x_8+x_1+x_2+x_3)\\ &\to (x_1+x_5, x_2+x_6, \ldots, x_8+x_4)\\ &\to (x_1+x_2+x_5+x_6, x_2+x_3+x_6+x_7, \ldots, x_8+x_1+x_4+x_5)\\ &\to (x_1+x_3+x_5+x_7, x_2+x_4+x_6+x_8, \ldots, x_8+x_2+x_4+x_6)\\ &\to (x_1+x_2+\cdots+x_8, x_1+x_2+\cdots+x_8, \ldots, x_1+x_2+\cdots+x_8)\\ &\to (0, 0, \ldots, 0) \pmod 2 \end{align*} Thus after a finite number of steps, the $8$-tuple is in the form $(2a_1, 2a_2, \ldots, 2a_8)$ for integers $a_1, a_2, \ldots, a_8$ and from $(4)$, the $8$-tuple can be reduced so that all entries are divided by a factor of $2$. Since the maximum entry is non-increasing and we began with $m = k$, we now have $m \le \lfloor k / 2 \rfloor < k$ (for $k > 0$). The $8$-tuple now reaches the form $(0, 0, \ldots, 0)$ in a finite number of steps by the IH. $\blacksquare$
In the list of properties of the Ducci sequence given on its wikipedia page, it says that for $n$-tuples where $n$ is not a power of $2$, the sequence either reaches $(0, 0, \ldots, 0)$ or enters a cycle where all entries are either $0$ or $M$ for a fixed constant $M$. The fact that it at least enters a cycle is clear from $(1)$ and $(2)$ above since the number of $n$-tuples with entries all nonnegative integers at most some fixed maximum is finite, so repeats must eventually occur.
To see that the $n$-tuples must all eventually contain only $0$ and $M$ for a fixed $M$ (if not eventually reaching $(0, 0, \ldots, 0)$), note that this requires the non-increasing maximum entry to stop decreasing and remain stationary, in this case no more than $M$, and in fact, exactly $M$. Indeed, call the $i$-th tuple $x_i$ and its $j$-th entry $x_i^{(j)}$. If the the maximum persists as $M$ for $n$ $n$-tuples $x_i, x_{i+1}, \ldots, x_{i+n-1}$, we can prove that all entries of $x_i$ must be either $0$ or $M$: let $x_{i+n-1}^{(j)} = M$.
Then $\{x_{i+n-2}^{(j)}, x_{i+n-2}^{(j+1)}\} = \{0, M\}$ (with superscripts taken $\pmod n$), as any other pair of integers in $\{0, 1, \ldots, M\}$ could not have achieved this difference. From similar reasoning, each of $x_{i+n-3}^{(j)}, x_{i+n-3}^{(j+1)}, x_{i+n-3}^{(j+2)} \in \{0, M\}$ with at least one being $M$. Repeating this reasoning down to $x_i$, all of its entries must be in $\{0, M\}$ and it is straightforward that this then must always be the case for subsequent $n$-tuples in the iterations.
vietajumping
24.02.2021 05:07
@above What is the proof of observation 4?