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.<br />
  <br />
  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. <br />
  <br />
  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$. <br />
  <br />
  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)$. <br />
  <br />
  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. <br />
  <br />
  With 3 beads the only initial states are RRR BBB RBB and
  BRR<br />
  <br />
  (1) With 3 beads the steady state is RRR <br />
  (2) BBB becomes RRR and then remains RRR for all time <br />
  (3) RBB becomes BRB then BBR then RBB again giving a periodic
  3-cycle <br />
  (4) BRR becomes BRB goes into a periodic 3-cycle as in (3) <br />
  <br />
  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. <br />
  <br />
  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. <br />
  <br />
  For 4 beads there are 6 positions which all reduce to the steady
  state with all red beads. <br />
  <br />
  (1) 1111 $\rightarrow$ 0000 (6) <br />
  (2) 0111 $\rightarrow$ 1001 (3) $\rightarrow$ (4) $\rightarrow$
  (1) $\rightarrow$ (6)<br />
  (3) 0011 $\rightarrow$ 0101 (4) $\rightarrow$ (1) $\rightarrow$
  (6)<br />
  (4) 0101 $\rightarrow$ 1111 (1) $\rightarrow$ (6)<br />
  (5) 0001 $\rightarrow$ 0011 (3) $\rightarrow$ (4) $\rightarrow$
  (1) $\rightarrow$ (6)<br />
  (6) 0000 $\rightarrow$ 0000 (6) <br />
  <br />
  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. <br />
  <br />
  (1) 11111 $\rightarrow$ 00000 (8) <br />
  (2) 01111 $\rightarrow$ 10001 (5)(6)(2) which is a 3-cycle <br />
  (3) 00111 $\rightarrow$ 01001 (6) then into the 3-cycle
  (2)(5)(6)\<br />
  (4) 01011 $\rightarrow$ 11101 (2) then into the 3-cycle (5)(6)(2)
  <br />
  (5) 00011 $\rightarrow$ 00101 (6)(2)(5) again the 3-cycle <br />
  (6) 00101 $\rightarrow$ 01111 (2)(5)(6) again the 3-cycle <br />
  (7) 00001 $\rightarrow$ 00011 (5) then into the 3-cycle (6)(2)(5)
  <br />
  (8) 00000 $\rightarrow$ 00000 (8) which is the steady state
  <br />
  <br />
  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. <br />
  <br />
  (1) 111111 $\rightarrow$ 000000 (13) <br />
  (2) 011111 $\rightarrow$ 100001 (9)(10)(3) the 2-cycle <br />
  (3) 001111 $\rightarrow$ 010001 (10)(3) is a 2-cycle <br />
  (4) 010111 $\rightarrow$ 111001 (3)(10) the 2-cycle <br />
  (5) 011011 $\rightarrow$ 101101 (5) which is a steady state
  <br />
  (6) 000111 $\rightarrow$ 001001 (11)(5)which is a steady state
  <br />
  (7) 001011 $\rightarrow$ 011101 (4)(3)(10)the 2-cycle <br />
  (8) 010101 $\rightarrow$ 111111 (1)(13) the red steady state
  <br />
  (9) 000011 $\rightarrow$ 000101 (10)(3) the 2-cycle <br />
  (10)000101 $\rightarrow$ 001111 (3)(10) the 2-cycle <br />
  (11)001001 $\rightarrow$ 011011 (5) which is a steady state
  <br />
  (12)000001 $\rightarrow$ 000011 (9)(10)(3) the 2-cycle <br />
  (13)000000 $\rightarrow$ 000000 (13) which is the steady state
  with all red beads <br />
  <br />
  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: <br />
  <br />
  $$MB=\left( \begin{array}{cc} 1 &amp;1 &amp;0 &amp;0 &amp;\cdots
  &amp;0 \\ 0 &amp;1 &amp;1 &amp;0 &amp;\cdots &amp;0 \\ \cdots \cr
  1 &amp;0 &amp;0 &amp;0 &amp;\cdots &amp;1 \end{array} \right)
  \left( \begin{array}{cc} x_0 \\ x_1 \\ \\ x_n \end{array}
  \right)$$ <br />
  <br />
  If some power of this matrix is zero the process reaches a steady
  state with all red beads. <br />
  <br />
  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$.<br />