tag:blogger.com,1999:blog-4115025577315673827.post1634566692170534964..comments2020-05-20T14:21:54.596+05:30Comments on CSE Blog - quant, math, computer science puzzles: Bulb PuzzlePratik Poddarhttp://www.blogger.com/profile/11577606981573330954noreply@blogger.comBlogger9125tag:blogger.com,1999:blog-4115025577315673827.post-66922662081925928892009-11-05T23:16:42.713+05:302009-11-05T23:16:42.713+05:30@Anonymous,
Fundoo maxx Solution
Thanx a lot..
Cou...@Anonymous,<br />Fundoo maxx Solution<br />Thanx a lot..<br />Could you bless us by telling us your holy name? :D<br /><br />@vivek<br />Interesting solution :)<br />Thanx...Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-8853445859333955992009-11-01T15:27:49.494+05:302009-11-01T15:27:49.494+05:30Change the question slightly,otherwise you never c...Change the question slightly,otherwise you never check state of nth bulb and so state of bulb 1 remains always on.<br />Then, 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.<br />So, in every 2^(n-1) cycles you'll get all to be on at least once.Vivek Jhahttps://www.blogger.com/profile/00394691204629747462noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-47056732998482135312009-10-26T19:55:27.634+05:302009-10-26T19:55:27.634+05:30what is n is odd?? did you think abt that case?what is n is odd?? did you think abt that case?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-76868008292247763002009-10-22T19:23:09.485+05:302009-10-22T19:23:09.485+05:30since we will never have n as tmodn hence the firs...since 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 cyclesAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-67919399986967574152009-10-20T14:15:11.574+05:302009-10-20T14:15:11.574+05:30the graph with points as state of bulbs is 1) fini...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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-19147823428559425562009-10-20T14:12:55.550+05:302009-10-20T14:12:55.550+05:30All bulb OFF is a self loop in this case. Even if ...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?<br /><br />We 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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-70736231400086855362009-10-13T22:28:35.173+05:302009-10-13T22:28:35.173+05:30The non zero condition is really not required. It ...The non zero condition is really not required. It follows from absence of hoops.<br />But awesome! I was completely stumped. Thought about it through the VMWare PPT. :(A Rustlehttps://www.blogger.com/profile/02337350008237724548noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-6524122871773882432009-10-13T21:08:01.987+05:302009-10-13T21:08:01.987+05:30solution is not completely clear.I think it would ...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 finiteUnknownhttps://www.blogger.com/profile/17923995765018410791noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-54059154675252222032009-10-13T19:41:09.397+05:302009-10-13T19:41:09.397+05:30for each k >= 0, after kn time, let the arrange...for each k >= 0, after kn time, let the arrangement of bulbs was given by Tk.<br />Now let all such Tk lie in a domain D. Also there is a transition function f(T(k-1)) = Tk.<br />So, for each k, after kn time, you will go in a linked list of such transition of arrangements. e.g.<br />T0->T1->T2...<br /><br />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.<br /><br /><br />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.Anonymousnoreply@blogger.com