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₀, x₁,...x_n) where all the xs are 0 or 1. This vector is mapped to (x₀+x₁, x₁+x₂, ... x_n+x₀) 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 ® 0000 (6)
(2) 0111 ® 1001 (3) ® (4) ® (1) ® (6)
(3) 0011 ® 0101 (4) ® (1) ® (6)
(4) 0101 ® 1111 (1) ® (6)
(5) 0001 ® 0011 (3) ® (4) ® (1) ® (6)
(6) 0000 ® 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 ® 00000 (8)
(2) 01111 ® 10001 (5)(6)(2) which is a 3-cycle
(3) 00111 ® 01001 (6) then into the 3-cycle (2)(5)(6)
(4) 01011 ® 11101 (2) then into the 3-cycle (5)(6)(2)
(5) 00011 ® 00101 (6)(2)(5) again the 3-cycle
(6) 00101 ® 01111 (2)(5)(6) again the 3-cycle
(7) 00001 ® 00011 (5) then into the 3-cycle (6)(2)(5)
(8) 00000 ® 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 ® 000000 (13)
(2) 011111 ® 100001 (9)(10)(3) the 2-cycle
(3) 001111 ® 010001 (10)(3) is a 2-cycle
(4) 010111 ® 111001 (3)(10) the 2-cycle
(5) 011011 ® 101101 (5) which is a steady state
(6) 000111 ® 001001 (11)(5)which is a steady state
(7) 001011 ® 011101 (4)(3)(10)the 2-cycle
(8) 010101 ® 111111 (1)(13) the red steady state
(9) 000011 ® 000101 (10)(3) the 2-cycle
(10)000101 ® 001111 (3)(10) the 2-cycle
(11)001001 ® 011011 (5) which is a steady state
(12)000001 ® 000011 (9)(10)(3) the 2-cycle
(13)000000 ® 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= æ ç ç ç ç è 1 1 0 0 ¼ 0 0 1 1 0 ¼ 0 ¼ 1 0 0 0 ¼ 1 ö ÷ ÷ ÷ ÷ ø æ ç ç ç ç è x0 x1 xn ö ÷ ÷ ÷ ÷ ø

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ⁿ=(I+S)ⁿ. 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ⁿ=I+Sⁿ.