Fifteen Little Lights

As is common on my blog, today's post topic is a tangent. It will eventually return to the only-just-recently introduced topic of early video game audio. I originally stumbled upon the topic in that context, but I will introduce it as an abstract mathematical question. I will also deliberately leave out references to relevant mathematical materials, in order to 'force' you to make the discoveries independently.

Pretend that you are walking down the street, and you come across a signpost. On this signpost, there is a row of fifteen lights: some of the lights are on, and some of them are off:

At the bottom of the post is a large, friendly-looking button, labelled 'Push Me'. Such a button is irresistable to you, (as it is to me), and so you push it, to find that the lights change. You push the button a few times, and a pattern starts to emerge: each time you push the button, the lights turn on and off depending on whether the light to their left was on or off. Essentially, they are shifting towards the right.

The behaviour of the leftmost light is not as easy to pin down. It does not always take on the value of the rightmost light, so the lights aren't shifting around in a 'loop', so to speak. You eventually characterize the behaviour as follows: the rightmost light is lit if, before pressing the button, the leftmost two lights are in different states. (If you are computer-science inclined, you might call this an exclusive OR).

Having mastered the very simple, observable behaviour of this strange post, you put on your mathematics hat, and begin to wonder about deeper results about the signpost:

• What patterns of lights could you reach, if you kept pushing the button?
• Given a starting pattern, would you ever get back to that pattern again if you pushed the button enough times?
• Is there a starting pattern that eventually leads to all the lights being off?

We will begin to explore these questions in the next post.