Three beads are threaded on a circular wire and they are coloured
either red or blue. You repeat the following actions over and over
again. Between any two of the same colour put a red bead and
between any two of different colours put a blue, then remove the
original beads.

Andrei Lazanu, age 14, School No. 205, Bucharest, Romania correctly analysed all the results with all possible arrangements of $n= 2, 3, 4, 5$ and 6 red and blue beads on the wire.

Andrei found that starting with 2 beads and 4 beads all the beads become red giving a final steady state but there are more possibilities for the final state for other values of $n$.

In fact he identified more types of solutions: - all beads of the same colour lead to a steady state with all red beads - there are a cyclic combinations of beads dependent on the starting positions $(n = 3, 5, 6)$ - there are stable situations in the final state $( n=3, 5, 6)$.

With 2 beads RB changes to BB which changes to RR (the steady state) so, irrespective of the starting state, this always reduces to a steady state.

With 3 beads the only initial states are RRR BBB RBB and BRR

(1) With 3 beads the steady state is RRR

(2) BBB becomes RRR and then remains RRR for all time

(3) RBB becomes BRB then BBR then RBB again giving a periodic 3-cycle

(4) BRR becomes BRB goes into a periodic 3-cycle as in (3)

Generalising this note that for any number of beads if all the beads are red RRR...R his is a steady state. If all the beads are blue then at the first step they all become red and reach the steady state.

To encode this process we can write 0 for the red beads and 1 for the blue beads and denote the sequence of $n$ beads by the vector $(x_0, x_1,...x_n)$ where all the $x$s are 0 or 1. This vector is mapped to $(x_0+x_1, x_1+x_2, ... x_n+x_0)$ where addition is modulo 2. Note that 1 + 1 =0 and 0 + 0 = 0 which corresponds to replacing two of the same colour by a red. Also 1 + 0 = 1 and 0 +1 = 1 which corresponds to replacing two of different colours by a blue.

For 4 beads there are 6 positions which all reduce to the steady state with all red beads.

(1) 1111 $\rightarrow$ 0000 (6)

(2) 0111 $\rightarrow$ 1001 (3) $\rightarrow$ (4) $\rightarrow$ (1) $\rightarrow$ (6)

(3) 0011 $\rightarrow$ 0101 (4) $\rightarrow$ (1) $\rightarrow$ (6)

(4) 0101 $\rightarrow$ 1111 (1) $\rightarrow$ (6)

(5) 0001 $\rightarrow$ 0011 (3) $\rightarrow$ (4) $\rightarrow$ (1) $\rightarrow$ (6)

(6) 0000 $\rightarrow$ 0000 (6)

For 5 beads there are 8 positions two reducing to the steady state with all red beads and the other six cycling between 3 positions.

(1) 11111 $\rightarrow$ 00000 (8)

(2) 01111 $\rightarrow$ 10001 (5)(6)(2) which is a 3-cycle

(3) 00111 $\rightarrow$ 01001 (6) then into the 3-cycle (2)(5)(6)\

(4) 01011 $\rightarrow$ 11101 (2) then into the 3-cycle (5)(6)(2)

(5) 00011 $\rightarrow$ 00101 (6)(2)(5) again the 3-cycle

(6) 00101 $\rightarrow$ 01111 (2)(5)(6) again the 3-cycle

(7) 00001 $\rightarrow$ 00011 (5) then into the 3-cycle (6)(2)(5)

(8) 00000 $\rightarrow$ 00000 (8) which is the steady state

For 6 beads there are 13 positions three reducing to the steady state with all red beads, three reducing to a steady state with 2 red and 4 blue beads and the other seven eventually cycling between 2 positions.

(1) 111111 $\rightarrow$ 000000 (13)

(2) 011111 $\rightarrow$ 100001 (9)(10)(3) the 2-cycle

(3) 001111 $\rightarrow$ 010001 (10)(3) is a 2-cycle

(4) 010111 $\rightarrow$ 111001 (3)(10) the 2-cycle

(5) 011011 $\rightarrow$ 101101 (5) which is a steady state

(6) 000111 $\rightarrow$ 001001 (11)(5)which is a steady state

(7) 001011 $\rightarrow$ 011101 (4)(3)(10)the 2-cycle

(8) 010101 $\rightarrow$ 111111 (1)(13) the red steady state

(9) 000011 $\rightarrow$ 000101 (10)(3) the 2-cycle

(10)000101 $\rightarrow$ 001111 (3)(10) the 2-cycle

(11)001001 $\rightarrow$ 011011 (5) which is a steady state

(12)000001 $\rightarrow$ 000011 (9)(10)(3) the 2-cycle

(13)000000 $\rightarrow$ 000000 (13) which is the steady state with all red beads

Editor's note: These steps are equivalent to repeatedly multiplying by the n by n matrix $M$ a column $B$ of 1s and 0s representing the beads:

$$MB=\left( \begin{array}{cc} 1 &1 &0 &0 &\cdots &0 \\ 0 &1 &1 &0 &\cdots &0 \\ \cdots \cr 1 &0 &0 &0 &\cdots &1 \end{array} \right) \left( \begin{array}{cc} x_0 \\ x_1 \\ \\ x_n \end{array} \right)$$

If some power of this matrix is zero the process reaches a steady state with all red beads.

We can take $M=I+S$ where $I$ is the identity matrix and $S$ is the shift so that $M^n=(I+S)^n$. In matrix algebra we can expand this by the Binomial Theorem and all even coefficients will be zero (mod 2). In the case $n=2^k$ the Binomial coefficients, other than the first and last, are even so it reduces to $M^n=I+S^n$.

Andrei Lazanu, age 14, School No. 205, Bucharest, Romania correctly analysed all the results with all possible arrangements of $n= 2, 3, 4, 5$ and 6 red and blue beads on the wire.

Andrei found that starting with 2 beads and 4 beads all the beads become red giving a final steady state but there are more possibilities for the final state for other values of $n$.

In fact he identified more types of solutions: - all beads of the same colour lead to a steady state with all red beads - there are a cyclic combinations of beads dependent on the starting positions $(n = 3, 5, 6)$ - there are stable situations in the final state $( n=3, 5, 6)$.

With 2 beads RB changes to BB which changes to RR (the steady state) so, irrespective of the starting state, this always reduces to a steady state.

With 3 beads the only initial states are RRR BBB RBB and BRR

(1) With 3 beads the steady state is RRR

(2) BBB becomes RRR and then remains RRR for all time

(3) RBB becomes BRB then BBR then RBB again giving a periodic 3-cycle

(4) BRR becomes BRB goes into a periodic 3-cycle as in (3)

Generalising this note that for any number of beads if all the beads are red RRR...R his is a steady state. If all the beads are blue then at the first step they all become red and reach the steady state.

To encode this process we can write 0 for the red beads and 1 for the blue beads and denote the sequence of $n$ beads by the vector $(x_0, x_1,...x_n)$ where all the $x$s are 0 or 1. This vector is mapped to $(x_0+x_1, x_1+x_2, ... x_n+x_0)$ where addition is modulo 2. Note that 1 + 1 =0 and 0 + 0 = 0 which corresponds to replacing two of the same colour by a red. Also 1 + 0 = 1 and 0 +1 = 1 which corresponds to replacing two of different colours by a blue.

For 4 beads there are 6 positions which all reduce to the steady state with all red beads.

(1) 1111 $\rightarrow$ 0000 (6)

(2) 0111 $\rightarrow$ 1001 (3) $\rightarrow$ (4) $\rightarrow$ (1) $\rightarrow$ (6)

(3) 0011 $\rightarrow$ 0101 (4) $\rightarrow$ (1) $\rightarrow$ (6)

(4) 0101 $\rightarrow$ 1111 (1) $\rightarrow$ (6)

(5) 0001 $\rightarrow$ 0011 (3) $\rightarrow$ (4) $\rightarrow$ (1) $\rightarrow$ (6)

(6) 0000 $\rightarrow$ 0000 (6)

For 5 beads there are 8 positions two reducing to the steady state with all red beads and the other six cycling between 3 positions.

(1) 11111 $\rightarrow$ 00000 (8)

(2) 01111 $\rightarrow$ 10001 (5)(6)(2) which is a 3-cycle

(3) 00111 $\rightarrow$ 01001 (6) then into the 3-cycle (2)(5)(6)\

(4) 01011 $\rightarrow$ 11101 (2) then into the 3-cycle (5)(6)(2)

(5) 00011 $\rightarrow$ 00101 (6)(2)(5) again the 3-cycle

(6) 00101 $\rightarrow$ 01111 (2)(5)(6) again the 3-cycle

(7) 00001 $\rightarrow$ 00011 (5) then into the 3-cycle (6)(2)(5)

(8) 00000 $\rightarrow$ 00000 (8) which is the steady state

For 6 beads there are 13 positions three reducing to the steady state with all red beads, three reducing to a steady state with 2 red and 4 blue beads and the other seven eventually cycling between 2 positions.

(1) 111111 $\rightarrow$ 000000 (13)

(2) 011111 $\rightarrow$ 100001 (9)(10)(3) the 2-cycle

(3) 001111 $\rightarrow$ 010001 (10)(3) is a 2-cycle

(4) 010111 $\rightarrow$ 111001 (3)(10) the 2-cycle

(5) 011011 $\rightarrow$ 101101 (5) which is a steady state

(6) 000111 $\rightarrow$ 001001 (11)(5)which is a steady state

(7) 001011 $\rightarrow$ 011101 (4)(3)(10)the 2-cycle

(8) 010101 $\rightarrow$ 111111 (1)(13) the red steady state

(9) 000011 $\rightarrow$ 000101 (10)(3) the 2-cycle

(10)000101 $\rightarrow$ 001111 (3)(10) the 2-cycle

(11)001001 $\rightarrow$ 011011 (5) which is a steady state

(12)000001 $\rightarrow$ 000011 (9)(10)(3) the 2-cycle

(13)000000 $\rightarrow$ 000000 (13) which is the steady state with all red beads

Editor's note: These steps are equivalent to repeatedly multiplying by the n by n matrix $M$ a column $B$ of 1s and 0s representing the beads:

$$MB=\left( \begin{array}{cc} 1 &1 &0 &0 &\cdots &0 \\ 0 &1 &1 &0 &\cdots &0 \\ \cdots \cr 1 &0 &0 &0 &\cdots &1 \end{array} \right) \left( \begin{array}{cc} x_0 \\ x_1 \\ \\ x_n \end{array} \right)$$

If some power of this matrix is zero the process reaches a steady state with all red beads.

We can take $M=I+S$ where $I$ is the identity matrix and $S$ is the shift so that $M^n=(I+S)^n$. In matrix algebra we can expand this by the Binomial Theorem and all even coefficients will be zero (mod 2). In the case $n=2^k$ the Binomial coefficients, other than the first and last, are even so it reduces to $M^n=I+S^n$.