tag:blogger.com,1999:blog-4115025577315673827.post6839150178218857234..comments2020-05-25T13:34:36.365+05:30Comments on CSE Blog - quant, math, computer science puzzles: Invert the CupsPratik Poddarhttp://www.blogger.com/profile/11577606981573330954noreply@blogger.comBlogger9125tag:blogger.com,1999:blog-4115025577315673827.post-31142425396077275122014-08-07T22:33:06.472+05:302014-08-07T22:33:06.472+05:30Can't it be done by induction?
You can trivi...Can't it be done by induction? <br /><br />You can trivially do it for n = 2. Now suppose that you can do it for n = 2k for some integer k. <br />Take n = 2k + 2. You take the first 2k cups and invert them (by hypothesis) and while doing so in each step do whatever it occurs to the last two. i.e. both of them will have same state. If both of them are down already, its good otherwise leave the last one and invert the rest. This will lead you to have second last one down rest upright. You again invert those which are upright. This will give you all cups facing down.<br />So this tells us that you can do it for n = even.<br /><br />Now we know that we can't do it for n = 1. As (n - 1) = 0 and you are not able to invert anything.<br />Now suppose that you are able to do it for some odd n = 2k + 1 (k is some integer). i.e. Now all are facing down. Now you can invert all of them except the last one. Now again invert all except the second last one. This will lead to have first 2k -1 cups facing down and last 2 upright. So, this tells us if you are able to do it for any odd number then you can do it for odd number just before that number.<br />This will tell you that you can do it for 1. But, you know you can't do it for n = 1. Hence, contradiction. <br /> Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-64612824597154031592010-02-26T12:59:21.300+05:302010-02-26T12:59:21.300+05:30Proof that n moves would be needed.
Define a func...Proof that n moves would be needed.<br /><br />Define a function f after time t as<br /><br />No. of upright - No. of inverted after time t if t is even<br /><br />No. of inverted - No. of upright if t is odd<br /><br />So, f(0) = n<br />After each time, the change in value of f is either +2 or -2 (as n-1 cups are inverted. So, they so not contribute to any change)<br /><br />Since, we will always take odd number of moves (trivial proof by parity argument)<br /><br />Finally, f value is -n<br /><br />So, change is 2n<br /><br />So, at least n steps are needed.<br /><br />Hence, proved :)Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-48229391938559073832010-02-25T11:35:37.434+05:302010-02-25T11:35:37.434+05:30I think the minimum number of steps is n (the algo...I think the minimum number of steps is n (the algorithm given by sid ankush and others gives those n moves). It should be easy to prove it too. Probably an argument saying u cant change it effectively by more than 1.Aytidaa Madrashttps://www.blogger.com/profile/04386601441575337262noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-57537101599311405952010-02-08T19:47:40.315+05:302010-02-08T19:47:40.315+05:30A natural question to ask is find the minimum numb...A natural question to ask is find the minimum number of steps required to complete the task. <br />Lets try to answer that.NGhttps://www.blogger.com/profile/00137167173637522039noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-71925018248773467732010-02-08T09:06:47.649+05:302010-02-08T09:06:47.649+05:30Thanx Ankush, Dinesh, Nikhil and Sid :)
@Ankush.....Thanx Ankush, Dinesh, Nikhil and Sid :)<br /><br />@Ankush.. Correct algorithm. Nice explanation<br /><br />@Dinesh (scadza): Argument using "parity" would have been simpler.<br /><br />@Nikhil, Sid: Good explanation for n=odd case<br /><br />@Sid: Thanx for a different algorithm. No one I talked to came up with this algorithm. :) All of us did it in Ankush's way.Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-51980561359518935082010-02-07T23:30:39.513+05:302010-02-07T23:30:39.513+05:30Case 1: n even: take all combinations of n-1 cups ...Case 1: n even: take all combinations of n-1 cups and invert them. As each cup lies in exactly (n-1) combinations and as n-1 is odd => each cup is flipped odd no of times => each cup is inverted.<br />Case 2: n odd: assign binary value to each "down" cup as 1 and each "up" as 0. So initially sum is 1 mod 2. As n-1 is even => any n-1 flips will not change the sum mod 2. As sum of all "up" is 0, hence this is not possiblesidhttps://www.blogger.com/profile/04179126136399818676noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-6351165938942701072010-02-07T23:29:55.208+05:302010-02-07T23:29:55.208+05:30And if n is odd , it is not possilble :
As at eve...And if n is odd , it is not possilble :<br /><br />As at every step we upset n-1 (even) bits- So parity of sum would remain invariant. Initially sum is even So it should be even always. <br />However if all become 1 , we have odd sum.NGhttps://www.blogger.com/profile/00137167173637522039noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-54960410714680712222010-02-07T23:26:41.683+05:302010-02-07T23:26:41.683+05:30Let the cups be numbered from 1 to N
Initially al...Let the cups be numbered from 1 to N<br /><br />Initially all cups were upright <br />{U,U,...,U} N times <br /><br />Define the inversion of cups from one state to another (i.e. from upright to inverted or from inverted to upright ) as an Operation OP<br /><br />IF all cups are inverted in the end, then it means each of the cup went the operation OP odd number of times.<br /><br />Suppose N = even and in this case total K operations were required to flip all of them to inverted then it follows <br />Kx(N-1) = odd number + odd number + odd number + .... + odd number (even number of times since N is even)<br />LHS is even and hence chosing K as even could solve the above equation<br /><br />Suppose N=odd then<br />K x (N-1) = odd number + odd number + ....+ odd number (odd number of times since N is odd)<br />RHS is odd while LHS is even (as [N-1] is even)<br />This a contradiction. Thus in this case solution can't exist<br /><br />And Ankush solution gives the procedure in N=even case.scadzahttps://www.blogger.com/profile/04733361617492050871noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-12495113035986445482010-02-07T17:35:46.564+05:302010-02-07T17:35:46.564+05:30Even Case :
m=2n bits
Initially all are zero.
Con...Even Case : <br />m=2n bits<br />Initially all are zero.<br />Consider the situation where we have r <br />zeros and (2n-r) ones. Invert all the bits except for a '1' bit. Now number of zeros = (2n-r-1) and number of ones equal (r+1). Let the ordered pair represent (No of Ones,Number of Zeros).We can follow the sequence : (0,2n),(2n-1,1),(2,2n-2),....,(2n,0)Ankushhttps://www.blogger.com/profile/09691343611737045503noreply@blogger.com