You may also like

problem icon

Whole Number Dynamics I

The first of five articles concentrating on whole number dynamics, ideas of general dynamical systems are introduced and seen in concrete cases.

problem icon

Whole Number Dynamics II

This article extends the discussions in "Whole number dynamics I". Continuing the proof that, for all starting points, the Happy Number sequence goes into a loop or homes in on a fixed point.

problem icon

Whole Number Dynamics III

In this third of five articles we prove that whatever whole number we start with for the Happy Number sequence we will always end up with some set of numbers being repeated over and over again.

More Beads

Stage: 5 Challenge Level: Challenge Level:2 Challenge Level:2
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$.