Puzzle time
-
I draw the line at writing code or writing anything down for these puzzles. I couldn’t make much headway with this one though I had tried the reversal and a reductio of the lightbulbs. Either there is an infinite loop which returns to all off or they eventually turn to all on.
-
So you start with t = 0 (i.e. turn bulb 1 off), then t=1 (do nothing with bulb 2), then t=2 (turn bulb 3 of) and so forth. After the first round, all odd numbered bulbs are off and all even numbered ones are on.
Correct so far?
I haven't thought a lot about it yet, but the only fixed point seems to be that all bulbs are off. Hmm... My first guess is that it will return to that same state around time t=2^100.
-
My first guess was that it would return because lower numbers do. But you need to do better than guess.
Like Ax I wrote code to play a bit but after 36 bulbs ran for a full day I gave up on the brute force method.
Only non-witches get due process.
- Cotton Mather, Salem Massachusetts, 1692
-
Is it not inevitable that it returns to all off? I don’t think there can exist a loop which does not eventually return to every antecedent state. And if there is no loop then you have to assume that the infinity of future states must contain all off. Which makes a loop. Maybe the insight is that all such state machines are necessarily looping.
-
My first guess was that it would return because lower numbers do. But you need to do better than guess.
Like Ax I wrote code to play a bit but after 36 bulbs ran for a full day I gave up on the brute force method.
@jon-nyc said in Puzzle time:
Like Ax I wrote code to play a bit but after 36 bulbs ran for a full day I gave up on the brute force method.
Just out of curiosity, I ran a simulation for 36 bulbs on a MacBook Air (1.6 GHz Intel Core i5). It took 10 minutes and 36 seconds to reach the "all on" state at the 22,839,252,821st iteration. I implemented my simulator using Go.
What did you use to implement and run your simulation?
-
Nice puzzle!
Let's analyze this some more.
Every state is in a cycle that has a length n. We just established that the set of states is the disjoint union of all cycles.
Let's consider a histogram of cycle lengths. For instance, "000....000" is in a cycle of length one, hence we add one to the bin for cycles of length 1.
What kind of shape will the histogram have? And the extra Nassim Taleb Black Swan question is: does it have a "fat tail"?
-
I graphed out some early ones, they do not. THey're in the general shape of a normal curve (not saying they're normal).
-
No we’re not. I graphed out the sum of lightbulbs that were on in each state change (every toggle changes the sum by +-1) so it moves around in a jerky continuous fashion). That formed a narrow bell curve.
When I say early ones, I did it to the completion of the cycle, or even multiple cycles for smaller n. I did also graph them for n=100 but just for the first few million ticks.
