Puzzle time
-
wrote on 21 Jun 2020, 23:36 last edited by
In a circle are light bulbs numbered clockwise 1 through 100, all initially on. At time t, you examine bulb number t (if t > 100, it's the light bulb whose number is the last two digits of t). If that light bulb is on, you change the state of bulb t+1; i.e., you turn off the clockwise-next bulb if it's on, and on if it's off. If bulb t is off, you do nothing.
If you continue around and around the ring in this manner, will it ever happen that all 100 bulbs will again be on?
-
wrote on 27 Jun 2020, 11:32 last edited by
Big hint:
Is the process reversible?
-
wrote on 27 Jun 2020, 14:56 last edited by
By running simulations, I can "see" that for smaller # of bulbs, they do return to the state where all bulbs are on. I ran simulations up to 30 bulbs.
There is some hint of iterating the process (2 to the power of the # of bulbs) times to return to the state where all bulbs are on, but not consistently so. I haven't figure out the pattern yet.
If you don't mind, please do not post the answer yet ... I'd like to see if I can return to this puzzle later. Thanks.
-
wrote on 27 Jun 2020, 15:03 last edited by
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.
-
wrote on 27 Jun 2020, 15:26 last edited by
The answer is 12.
-
wrote on 27 Jun 2020, 16:28 last edited by Klaus
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.
-
wrote on 27 Jun 2020, 17:08 last edited by
Your first paragraph is correct. You’re also correct that straight 0s is stable.
-
wrote on 27 Jun 2020, 17:10 last edited by jon-nyc
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.
-
wrote on 27 Jun 2020, 17:16 last edited by
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.
-
wrote on 27 Jun 2020, 17:19 last edited by
Pinhole loops are not possible because they would require two different antecedent states leading to the same next state. And it seems a pinhole loop is the only way the state would never revert to the initial conditions.
-
wrote on 27 Jun 2020, 17:36 last edited by
Yes that is the answer. From reversibility it follows.
(assuming you meant 'all on' not 'all off')
-
wrote on 27 Jun 2020, 17:43 last edited by
Whichever one is less racist, that’s the one I meant.
-
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.
wrote on 27 Jun 2020, 17:45 last edited by@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?
-
wrote on 27 Jun 2020, 18:07 last edited by
I would add the reversibility isn’t a sufficient condition to answer the problem, you also need a finite number of possible states.
-
wrote on 27 Jun 2020, 18:09 last edited by jon-nyc
yes yes. there are fewer than 100*2^100 states.
-
wrote on 27 Jun 2020, 18:09 last edited by
Ax I was exaggerating but I used python on the Mac
-
wrote on 27 Jun 2020, 20:21 last edited by Klaus
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"?
-
wrote on 27 Jun 2020, 21:08 last edited by
I graphed out some early ones, they do not. THey're in the general shape of a normal curve (not saying they're normal).
-
wrote on 28 Jun 2020, 00:40 last edited by
Are these Christmas tree bulbs? If so, the answer is that they will never all be on again until you buy new ones.
-
I graphed out some early ones, they do not. THey're in the general shape of a normal curve (not saying they're normal).