Bulb Puzzle
Source: P. Winkler
In a circle are light bulbs numbered 0 through n-1 all initially on. At time t, you examine the bulb number t mod n, and if its on, you change the state of bulb t+1 mod n. If bulb t is off, you do nothing.
Prove that if you continue around and around the ring in this manner, eventually all the bulbs will again be on.
Update (Nov 5 2009) : Thanx vivek, the small problem updated. Bulbs numbered 0 to n-1 instead to 1 to n. Thanx. Solution in comments!!
In a circle are light bulbs numbered 0 through n-1 all initially on. At time t, you examine the bulb number t mod n, and if its on, you change the state of bulb t+1 mod n. If bulb t is off, you do nothing.
Prove that if you continue around and around the ring in this manner, eventually all the bulbs will again be on.
Update (Nov 5 2009) : Thanx vivek, the small problem updated. Bulbs numbered 0 to n-1 instead to 1 to n. Thanx. Solution in comments!!
for each k >= 0, after kn time, let the arrangement of bulbs was given by Tk.
ReplyDeleteNow let all such Tk lie in a domain D. Also there is a transition function f(T(k-1)) = Tk.
So, for each k, after kn time, you will go in a linked list of such transition of arrangements. e.g.
T0->T1->T2...
If I prove that f is a reversible function, then each Tk value can be reached from exactly one T(k-1). So that there are no "hoops" in this linked list and it is a circular linked list... and hence eventually all bulbs will be "on" again.
To prove that it is reversible. Consider arrangement at kn > 0 time. Let it be {a1, a2, ..., an} where ai = 0 means bulb is off and 1 means it is on. Now, at time t-1, let the arrangement be {a1', a2', ...an'}. But, a1 = an' ^ a1' and an = an'.....(at time kn). Hence we can determine all ai'. Similarly going back in time, we can determine {b1, b2, ..., bn} which was arrangment at (k-1)n time. Hence it is deterministic. So, there can be one operand for a given output. Hence, no hoop. Hence, only circular list, which proves the problem.
solution is not completely clear.I think it would be more clear if he would have said that all bulb off state would never be reached and also number of possible state is finite
ReplyDeleteThe non zero condition is really not required. It follows from absence of hoops.
ReplyDeleteBut awesome! I was completely stumped. Thought about it through the VMWare PPT. :(
All bulb OFF is a self loop in this case. Even if there are several other such loops... why do we need to worry about them?
ReplyDeleteWe know that it has finite states. Function is reversible. So, the graph of points of states is just set of circles... and no hoop. Thus, the proof.
the graph with points as state of bulbs is 1) finite 2) has one-one edges. Thus, it is just set of directed circles... no hoops. And hence the solution.
ReplyDeletesince we will never have n as tmodn hence the first bulb is never switched off...therefore as you go round and round you will have all the bulbs on and all the bulbs off in alternative cycles
ReplyDeletewhat is n is odd?? did you think abt that case?
ReplyDeleteChange the question slightly,otherwise you never check state of nth bulb and so state of bulb 1 remains always on.
ReplyDeleteThen, it is just like array of flip flops working as frequency divider and state of 2nd bulb is toggled every cycle, state of 3rd bulb is toggled every two cycles, and so on.
So, in every 2^(n-1) cycles you'll get all to be on at least once.
@Anonymous,
ReplyDeleteFundoo maxx Solution
Thanx a lot..
Could you bless us by telling us your holy name? :D
@vivek
Interesting solution :)
Thanx...