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 (x0, x1, ... xn) where all the xs are 0 or 1. This vector is mapped to (x0+x1, x1+x2, ... xn+x0) 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-cycl
(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 of 1s and 0s representing the
beads:
|