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,\hspace{1em}3,\hspace{1em}4,\hspace{1em}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,\hspace{1em}5,\hspace{1em}6)$ - there are stable situations in the final state $(n=3,\hspace{1em}5,\hspace{1em}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,\hspace{1em}{x}_1,\hspace{1em}...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 $\to$ 0000 (6)
(2) 0111 $\to$ 1001 (3) $\to$ (4) $\to$ (1) $\to$ (6)
(3) 0011 $\to$ 0101 (4) $\to$ (1) $\to$ (6)
(4) 0101 $\to$ 1111 (1) $\to$ (6)
(5) 0001 $\to$ 0011 (3) $\to$ (4) $\to$ (1) $\to$ (6)
(6) 0000 $\to$ 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 $\to$ 00000 (8)
(2) 01111 $\to$ 10001 (5)(6)(2) which is a 3-cycle
(3) 00111 $\to$ 01001 (6) then into the 3-cycle (2)(5)(6)
(4) 01011 $\to$ 11101 (2) then into the 3-cycle (5)(6)(2)
(5) 00011 $\to$ 00101 (6)(2)(5) again the 3-cycle
(6) 00101 $\to$ 01111 (2)(5)(6) again the 3-cycle
(7) 00001 $\to$ 00011 (5) then into the 3-cycle (6)(2)(5)
(8) 00000 $\to$ 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 $\to$ 000000 (13)
(2) 011111 $\to$ 100001 (9)(10)(3) the 2-cycle
(3) 001111 $\to$ 010001 (10)(3) is a 2-cycle
(4) 010111 $\to$ 111001 (3)(10) the 2-cycle
(5) 011011 $\to$ 101101 (5) which is a steady state
(6) 000111 $\to$ 001001 (11)(5)which is a steady state
(7) 001011 $\to$ 011101 (4)(3)(10)the 2-cycle
(8) 010101 $\to$ 111111 (1)(13) the red steady state
(9) 000011 $\to$ 000101 (10)(3) the 2-cycl
(10)000101 $\to$ 001111 (3)(10) the 2-cycle
(11)001001 $\to$ 011011 (5) which is a steady state
(12)000001 $\to$ 000011 (9)(10)(3) the 2-cycle
(13)000000 $\to$ 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 of 1s and 0s representing the beads:

${\displaystyle \mathrm{MB}=\left(\begin{array}{cccccc}\hfill 1\hfill & \hfill 1\hfill & 0& 0& ...& 0\\ \hfill 0\hfill & \hfill 1\hfill & 1& 0& ...& 0\\ \hfill ...\hfill & \hfill \hfill & \\ \hfill 1\hfill & \hfill 0\hfill & 0& 0& ...& 1\end{array}\right)\left(\begin{array}{c}\hfill x\hfill \\ \hfill y\hfill \\ \hfill \hfill \\ \hfill \mathrm{xN}\hfill \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$.