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
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
No comments:
Post a Comment