Lightpost Characteristics

I hope you have given some thought to the questions posed in the previous post. If not, give that a read and a think before coming back.

What can we say about the patterns of lights that show up on the signpost? Let us start simple. There are 15 lights, and each can be either on or off. This means that there are at most 2¹⁵ = 32768 possible patterns. The fact that this is a finite number means that we can conclude that repeatedly pusing the button will eventually cause us to repeat a pattern that has previously appeared.

What sort of linked structure do these patterns present? For example, if there were only eight states, there are several different possible linking structures. Here is an example of three:

We can exclude a link structure that has 'spokes', like the first example. We do this by observing that each pattern has a unique 'successor' pattern. What abot predecessor? It turns out that each pattern also has a unique 'predecessor' pattern: you get this by shifting all the lights left, instead of right, and setting the rightmost light to be the exclusive or of the leftmost and rightmost light in the previous pattern:

The uniqueness of the predecessor and successor means that the patterns of lights must form simple loops, with no other, more complex shapes. This is because, on a link graph like the ones above, there must be exactly one arrow going into and exactly one arrow going out of each node.

How many loops are there? How many different patterns are in each loop? (We call this number of patterns the 'cycle length' of a loop). There is an easy loop to characterize. If all of the lights are initially off, then the predecessor and successor patterns are both equal to the initial pattern. Therefore there is one loop, with cycle length one.

We will thus restrict our attention to patterns with at least one light on. How many loops do they form, and what is the cycle length of each? Interestingly, there is only one other loop, containing every other pattern. That is right: starting from any pattern, you can keep pressing the button, and eventually reach any other pattern you desire (except, of course, for all the lights being off). This property will turn out to be very useful for the purposes of making an audio signal, but for now, I will simply state the result without proof.

At this point, you get bored of the lightpost, and continue walking to wherever it is you were originally headed. Before you can get there, however, you find another lightpost, also with fifteen lights. You push the button a few times, and discover that this one behaves slightly differently than the one before: instead of taking the exclusive or of the rightmost two lights, it takes the exclusive or of the rightmost light (let's call it light 15) and light 9:

The question for next time: how many cycles are in this second ligthpost, and what is the length of each? (Spoiler alert: the answer isn't the same as that of the first lightpost).