Last time, we 'proved' that the 15-9 lightpost has cycles of length 93, but I ended the post claiming that result is impossible. Why?
In the first post in this series, we observed that the lightpost is deterministic: from a given starting pattern, we can unambiguously determine the next pattern, and the next, and the next, and on and on, until we eventually return to the original pattern, which we always eventually do, because they come in cycles. This determinism property means that no two unique cycles share a common light pattern: if they did, then we could deterministically derive the rest of the pattern, and we would find that they had to the be same cycle, violating our original assumption that they were unique.
We can now explain why our cycles cannot be length 93. The lightpost has fifteen lights, for a total of 32768 different patterns. One of these patterns, the one with all ligths off, stands in its own lonely cycle of length 1, leaving 32767 other patterns unaccounted for. Each of the remaining patterns must appear in exactly one cycle. If all of the remaining cycles were length 93, then 32767 must be divisible by 93. It is not.
We must therefore have non-93 length cycles. Where is the error in our last proof, then? There isn't one. How can we reconcile these two facts?
The error turns out to be in our conclusion from the algebra: that each cycle was length 93. What we actually demonstrated was something subtly different: that each cycle repeats after 93 steps.
The difference is best explained by a story. Imagine that there is a racetrack, and it just so happens that the length of my stride is such that it takes me exactly 100 steps to run around this track. Now, imagine that there is also a freakishly tall, 12-foot man, standing next to me. His legs are twice as long, making his stride length twice as long, so he only takes 50 steps to run around the track. Here, however, is the key: after 100 steps, he is ALSO back at the starting line. The only difference between me and him is that he has gone through two cycles, whereas I have only gone through one.
All that we have proven, then, is that the cycles in the 15-9 lightpost repeat after 93 steps. The number 93 can be decomposed into prime factors 3 * 31. Therefore, the cycles of this lightpost can be 93, 31, 3, or 1 patterns long. (The '1' case is important, because we already know that the pattern with all lights off is part of a cycle with only one pattern).
We also know that the sum of the lengths of all of the cycles must be 32768. We can therefore state that 32768 = N1 + 3 * N3 + 31 * N31 + 93 * N93, for some constants N1, N3, N31 and N93 giving the number of cycles Nx with length x.
It is not too difficult to show that N1 = 1. There are only two possible light patterns that could repeat themselves: representing a light being 'on' with a 1, and a light being 'off' with a 0, these two patterns are '000000000000000' and '111111111111111'. Of these, only the former actually repeats itself; the latter turns into '011111111111111' after the button is pressed.
It is also not too difficult to show that N3 = 0. There are only eight possible light patterns that could repeat themselves after three steps: if we declare three state variables a, b and c, then these light patterns are of the form 'abcabcabcabcabc'. Note that the case where a = b = c = 0 has already been covered above, so we will restrict our attention to the seven remaining cases where at least one of a, b, and c is equal to 1. If we start with a pattern of this form, after we push the button three times, the pattern will be transformed into '000abcabcabcabc'. This is only equal to the original pattern if a = b = c = 0, which we just said we weren't going to consider.
Knowing these two facts, we can conclude that 32767 = 31 * N31 + 93 * N93, or, equivalently, that 1057 = N31 + 3 * N93. Math buffs will immediately recognize this as a Diophantine equation, first studied by the Greek mathematician Diophantus around the middle of the the 3rd century. They can tell you that the equation has possible solutions; specifically, 353 diifferent possible solutions. They can even parameterize them for you: for an integer parameter T in the range [0, 352], N31 = 1057 - 3 * T, and N93 = 3 * T.
This is all well and good, but we aren't looking for the solutions to a Diophantine equation, we are looking to characterize the cycle lengths of our lightpost. Only one of the 353 possible solutions is the correct one. The math buffs shrug their shoulders and move on, leaving us to ponder alone. Diophantus had nothing to say on the subject of lightposts, as he preceded the lightbulb by sixteen centuries.
Your question for next time: which of the 353 possible solutions for N31 and N93 is correct? A few hints follow:
- What do the numbers 31 and 32767 have in common?
No comments:
Post a Comment