Source: P. Winkler
In a circle are light bulbs numbered 0 through n1 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 n1 instead to 1 to n. Thanx. Solution in comments!!
Quant, Math & Computer Science Puzzles for Interview Preparation & Brain Teasing
A collection of ~225 Puzzles with Solutions (classified by difficulty and topic)
Subscribe to:
Post Comments (Atom)
Fraction Brainteaser
Source: Sent to me by Gaurav Sinha Problem: Siddhant writes a Maths test and correctly answers 5 out of 6 Arithmetic questions and 20...

This is not a puzzle. So, for those of you who follow this puzzle blog, please bear with me for just one post. Interesting Math in this art...

Let's say A keep tossing a fair coin, until he get 2 consecutive heads, define X to be the number of tosses for this process; B keep tos...

Source: Sent to me by Gaurav Sinha Problem: Siddhant writes a Maths test and correctly answers 5 out of 6 Arithmetic questions and 20...
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(k1)) = 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(k1). 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 t1, 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 (k1)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 oneone 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^(n1) 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...