Four Number Game II [Solution]

This was the puzzle:

You start with $n$ integers $a_1, a_2, \dots, a_n$ and in one step you perform the following transformation

$$(a_1, a_2, \dots , a_n) \to (|a_1-a_2|, |a_2 - a_3|, \dots, |a_{n-1} - a_n|, |a_n - a_1|)$$

($|x| =$ absolute value of $x$)

You keep performing this operation till all the numbers become zero.

Find all $n \gt 1$ (with proof), such that no matter which integers you start with, the numbers eventually become zero.

Solution

---

 The answer is the game terminates for every starting tuple of integers if and only if $n$ is a power of $2$.

The proof is based on the following observations (note, you might have to fill in a few details):

Lemma 1)

It is enough to consider the game modulo $2$, i.e, we play the game as

$$(a_1, a_2, \dots , a_n)  \to$$
$$(|a_1-a_2| \mod 2, |a_2 - a_3| \mod 2, \dots, |a_{n-1} - a_n| \mod 2, |a_n - a_1| \mod 2)$$

which is equivalent to the game, working in the field $\mathbb{F}_2$ (where each $a_i$ is $0$ or $1$ and $1+1 = 0$) as

$$(a_1, a_2, \dots , a_n) \to (a_1 + a_2, a_2 + a_3, \dots, a_{n-1} + a_n, a_n  + a_1)$$


Lemma 2)

Looking at the tuples as vectors over $\mathbb{F}_2$, if the game terminates for $u$ and $v$, then the game terminates for $u+v$.

Now the game is basically multiply a vector $v$ by a fixed matrix $A$, and the game terminates if $A^k v = 0$ for some $k$.

Lemma 3)

If the game terminates for $e = (1,0, \dots, 0)$, then the game terminates for all vectors in $\{0,1\}^n$. This is because we can cyclic shift $e$ to get that the game terminates for $(0, 1, \dots, 0)$ etc, and add as appropriate (by Lemma 2).

Lemma 4)

 If the game terminates for $e = (1, 0, \dots, 0)$, it does so in no more than $n$ steps!

This we can see by considering the starting state $v$, and the subsequent states $Av, A^2v, \dots, A^nv$.

Now suppose we have that $A^mv \ne 0$ for all $m \lt K$, and $A^K v = 0$.

The claim is that $v, Av, A^2v, \dots, A^{K-1}v$ are all linearly independent vectors.

If they were linearly dependent, then we have that

$$A^{s_1} v + A^{s_2}v + \dots = 0$$

with $s_1 \lt s_2 \dots \lt K$

Now just multiply the above with $A^{K-1-s_1}$ to get that $A^{K-1}v = 0$.

Since the $K$ vectors are linearly independent, we have that $K \le n$.

Main proposition)

The game played on $(1, 0, \dots, 0)$ gives us the rows of the Pascal's triangle on each step, and we are looking for all numbers to become even within $n$ steps.

We can now use Lucas' theorem to show that the only $n$ for which termination occurs is powers of $2$.

More reading: https://en.wikipedia.org/wiki/Ducci_sequence