Ring around the Rosie

The story so far: we have a lightpost, with fifteen lights, and the input light is the exclusive or of the fifteenth and ninth light. What is the cycle length?

In order to find the answer, we will first observe that we can map our lightpost, and the successive states, not as fifteen disjoint lights, but as a sliding window overtop of a single pattern of lights:

Under this mapping, each pattern of lights contributes a single light to the larger sequence, and conversely, each set of fifteen contiguous lights forms a single, unique pattern.

Having made this observation, we can represent the rule that produces a new pattern from an existing one as follows. If we assign each light in the sequence a number starting from some arbitrary starting light, and we represent L_x as the state of light N, then we have that L_x = L_x-9 ⊕ L_x-15. Here, ⊕ represents the 'exclusive or' operation.

We can go further, and apply this definition recursively. That is, L_x-9 = L_x-18 ⊕ L_x-24, so L_x = L_x-15 ⊕ L_x-18 ⊕ L_x-24. We also have L_x-15 = L_x-24 ⊕ L_x-30, and so learn that L_x = L_x-18 ⊕ L_x-24 ⊕ L_x-24 ⊕ L_x-30.

This is where things start to get interesting. The exclusive or operation has two identities that will be key to our proof: for a variable X, it is the case that X ⊕ X = False, and X ⊕ False = X. In our derivation above, L_x-24 appears twice. We can apply these two identities to conclude that L_x = L_x-18 ⊕ L_x-30.

Let's see what happens if we turn the crank of this algebraic jack-in-the-box:

L_x = L_x-9 ⊕ L_x-15
L_x = L_x-15 ⊕ L_x-18 ⊕ L_x-24
L_x = L_x-18 ⊕ L_x-24 ⊕ L_x-24 ⊕ L_x-30
L_x = L_x-18 ⊕ L_x-30
L_x = L_x-27 ⊕ L_x-30 ⊕ L_x-33
L_x = L_x-30 ⊕ L_x-33 ⊕ L_x-36 ⊕ L_x-42
L_x = L_x-33 ⊕ L_x-36 ⊕ L_x-39 ⊕ L_x-42 ⊕ L_x-45
L_x = L_x-36 ⊕ L_x-39 ⊕ L_x-42 ⊕ L_x-42 ⊕ L_x-45 ⊕ L_x-48
L_x = L_x-36 ⊕ L_x-39 ⊕ L_x-45 ⊕ L_x-48
L_x = L_x-39 ⊕ L_x-45 ⊕ L_x-45 ⊕ L_x-48 ⊕ L_x-51
L_x = L_x-39 ⊕ L_x-48 ⊕ L_x-51
L_x = L_x-48 ⊕ L_x-48 ⊕ L_x-51 ⊕ L_x-54
L_x = L_x-51 ⊕ L_x-54
L_x = L_x-54 ⊕ L_x-60 ⊕ L_x-66
L_x = L_x-60 ⊕ L_x-63 ⊕ L_x-66 ⊕ L_x-69
L_x = L_x-63 ⊕ L_x-66 ⊕ L_x-69 ⊕ L_x-69 ⊕ L_x-75
L_x = L_x-63 ⊕ L_x-66 ⊕ L_x-75
L_x = L_x-66 ⊕ L_x-72 ⊕ L_x-75 ⊕ L_x-78
L_x = L_x-72 ⊕ L_x-75 ⊕ L_x-75 ⊕ L_x-78 ⊕ L_x-81
L_x = L_x-72 ⊕ L_x-78 ⊕ L_x-81
L_x = L_x-78 ⊕ L_x-81 ⊕ L_x-81 ⊕ L_x-87
L_x = L_x-78 ⊕ L_x-87
L_x = L_x-87 ⊕ L_x-87 ⊕ L_x-93
L_x = L_x-93

The jack has popped! This demonstrates that for each cycle in our lightpost, each light is the same as the light 93 indices prior. From this we conclude that the length of each cycle in the lightpost is 93. There is only one problem with this result: it is impossible, and therefore wrong. Your questions for next time:

• Why it is impossibe for every cycle of this lightpost to be 93 sequences in length?
• Why does this impossibility not pose a problem for the proof that we have just derived?