Flickering Lights
Here’s an interesting 1D cellular automata. n lamps are arranged into a circle and each can be either on or off. Every second each of the lights can potentially change its state by the following rules:
- If a lamp has the same state as both of the lamps either side of it then it stays the same.
If either of a lamp's neighbours are in the opposite state to it, then it changes its state.
Show that unless all of the lamps are in the same initial state, then there is at least 1 pair of neighbouring lamps that will act as a blinker: alternating forever.
We’ll cycle back to that problem after exploring what happens with smaller numbers of lamps to get a feel for the set up. n=3 seems a nice small number to attempt. 000 and 111 just go to themselves and that will be true no matter how large the cycle is. 001 (which is identical to 010 and 100, but it is also the same in structure as 110 (and thus 101 and 011)) goes to 110, which then goes back to 001. By removing all of these structures that are functionally identical we limit the work for ourselves.
For n=4 the distinct starting states are 0000, 0001, 0011 and 0101. 0000 self loops. 0001 goes to 1010 which then flip flops to 0101 and back forever. Finally 0011 forms a period 2 pair with 1100. There are blinkers all over the place, but sometimes it requires a step before everything settles into this regularity.
As n gets bigger this period until everything settles is maximised by having a large area of one number with only a single other number. So 00000100000 becomes 00001010000, 00010101000, 00101010100, 01010101010 by which point we now loop with 10101010101 forever.
In answering the original problem, since we are given that not all the lights are in the same state, there must be at least one 1 and one 0 which are next to each other. Since they are both next to each other, they are both next to a lamp which is in the opposite state and so they are both going to change in the next time state. When they change the same logic applies and they will flip backwards and forwards forever. This rules out possibilities of fixed stable states or things with periods higher than 2.
