tag:blogger.com,1999:blog-4115025577315673827.post3683279563631848676..comments2020-05-20T14:21:54.596+05:30Comments on CSE Blog - quant, math, computer science puzzles: Blind flippingPratik Poddarhttp://www.blogger.com/profile/11577606981573330954noreply@blogger.comBlogger11125tag:blogger.com,1999:blog-4115025577315673827.post-89200603681591574872014-09-20T20:53:59.890+05:302014-09-20T20:53:59.890+05:30Suppose there is a name written on each corner and...Suppose there is a name written on each corner and an external referee. To the referee there are 15 states for table<br />viz 0000, 0001, 0010, ... , 1111. But instead of representing states in their binary form, we are gonna use the decimal version, so our states are 0, 1, 2, ..., 15.<br /><br />Challenge is to reach state 0 or 15 from any given state. Now if we XOR both the starting state and desired state(which 0 or 15) with the starting state, challenge reduces to reaching any state starting from 0 within some limited number of moves. What is the lowest value for that limit?<br /><br />Answer should be at least 15. I show here its exactly 15.<br /><br />Lets consider possible moves for blindfold:<br />S1. Flip All<br />S2. Flip Diagonal (2 types)<br />S3. Flip Adjacent (4 types)<br />S4. 1-flip (4 types)<br />S5. 3-flip (4 types) <br /><br />Lets apply some of the moves on state 0 and analyze the following diagram:<br /><br /> _____________________<br /> |__________________ |<br /> |_______________ | |<br /> |_________ | | |<br /> | | | | | <br /> 0 1 2 3 4 5 6 7<br /> | | | | | | | |<br /> 15 14 13 12 11 10 9 8<br /><br />PS : all lines in the picture are reversible<br /><br />S1 takes 0-15, 1-14, ....., 7-8 (lines between rows)<br />S2 takes 0- 5 (shown in the picture), 0-10<br />S3 takes 0-3, 0-6 (both shown in the picture), 0-12, 0-9<br />S5 takes 0-7(shown) and 0-14, 0-13, 0-11<br /><br />The left out numbers on the first row can be reached from 0 by S4.<br />S1 is only deterministic move of the lot, rest are probabilistic.<br /><br />Now if we combine the moves to the following operation:<br /> C1 : (S1 - S2 - S1) <br />C1 has two deterministic moves and one probabilistic move.<br /><br />This operation partitions states into four disjoint classes:<br />P1 : (0, 5, 10, 15)<br />P2: (1, 4, 11, 14)<br />P3: (2, 7, 8, 13)<br />P4: (3, 6, 9, 12)<br /><br />Partition meaning if we start from any member of any Pi, and follow C1, we traverse rest of the elements of that partition.<br /><br />For example: for P1 starting from 0, apply C1 to get either 0-15-10-5 or 0-15-5-10<br /><br />Now challenge reduces to switching partitions. I consider following two operations for this:<br /> C2 : (S3)<br /> C3: (S5)<br /><br />See C2 always takes P1 to P4 and P2 to P3 (eg C2 takes 0/5 to 3/6, 10/15 to 9/12) <br />and C3 always takes P1/P4 to P2/P3<br /><br />PS: C2 is deterministic operation and C3 is probabilistic operation<br /><br />Thus idea is to land on each partition and traverse it (and as before I use the deterministic move more than probabilistic move like in C1): <br /><br />So one possible move is: (starting from 0)<br /> C1-C2-C1 (This traverses P1 and P4 both)<br /> -C3 (Switches from P4-P2/P3)<br /> -C1-C2-C1 (This traverses both P2 and P3)<br /><br />Counting total moves, it is 15.<br />Anonymoushttps://www.blogger.com/profile/07462007299438769456noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-20566898122788763442009-12-10T15:30:06.795+05:302009-12-10T15:30:06.795+05:30nice.. thanx.. :)nice.. thanx.. :)Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-58776077289137029352009-12-10T14:51:06.098+05:302009-12-10T14:51:06.098+05:30I think PP gave a "proof" that it works,...I think PP gave a "proof" that it works, but how do we "come up" with such a solution?<br /><br />I'll call DA (flip diagonal, then flip all), SA (side,all), CA (corner, all) as the 3 possible moves. All arguments are modulo rotation.<br /><br />Notice that this is what let's us win: a table that looks like <br />1 0<br />0 1<br />has a _guaranteed_ solution (DA)<br /><br />(at first thought, there is no such case for the triangle).<br /><br />ALSO, this leaves the <br />0 0<br />1 1 <br />and the<br />0 0<br />0 1<br />cases untouched. HENCE, we can safely do DA first.<br /><br />Now, for the<br />0 0 <br />1 1<br />case, we see that SA either solves it, or converts it to the first case, where DA was the solution.<br />So SA-DA solves this one.<br /><br />AND, SA-DA leaves<br />0 0<br />0 1<br />untouched. HENCE we can safely apply it.<br /><br />Now we see that CA converts it to either the first case or the second case. So, a DA would solve it if it left the 1st case. But if it left the second case, then DA would have left it unchanged and so a subsequent SA-DA will solve it.<br />So CA-DA-SA-DA will surely solve it.<br /><br />Hence the total solution can be written as DA, SA-DA, CA-DA-SA-DAAytidaa Madrashttps://www.blogger.com/profile/04386601441575337262noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-86114175134492372722009-11-28T18:52:09.722+05:302009-11-28T18:52:09.722+05:30Okay I got it. What led me to believe that there m...Okay I got it. What led me to believe that there may not exist a solution is that 3 tumblers on a triangle table do not have a solution (I couldn't find one!). I was going through the induction/ recursive way but now I see it may not always work :)<br />Anyways do take a stab at the 3 tumbler situationEarthlinghttps://www.blogger.com/profile/07133281473683565210noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-48566798792430293562009-11-25T14:14:17.047+05:302009-11-25T14:14:17.047+05:30@asad
That's what I proved.. Whichever way the...@asad<br />That's what I proved.. Whichever way the evil goblin rotates the table, I will always go to a new state and so, all the states would be covered. Note that it does not matter what goblin does, because, I make sure that in all the cases, my sequence of instructions result in a complete exhaustive search for all the cases. Hence it is correct. We are giving a "deterministic" algorithm that yes in 15 steps, I will go to a different state each time.Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-30437724436151220752009-11-25T13:42:40.441+05:302009-11-25T13:42:40.441+05:30Since many people have been asking me to explain J...Since many people have been asking me to explain Jaadu's and Pratyush argument, I am writing a long post now...<br /><br />Yes indeed:<br />flip all<br />flip diagonal<br />flip all<br />flip adjacent<br />flip all<br />flip diagonal<br />flip all<br />flip any 3<br />flip all<br />flip diagonal<br />flip all<br />flip adjacent<br />flip all<br />flip diagonal<br />flip all<br /><br />would work..<br /><br />Lets see how..<br />The number of states are 32 (Each tumbler up and down and whose chance it is, mine or the other person)<br /><br />The number of operations on each step by me is 15 (all, 2 diagonal, 4 adjacent, 4 in groups of 3, 4 single flips)<br /><br />We are ignoring the operation single flip. So, effectively its 11<br /><br />We can show that by following the steps as mentioned above we can get all the possible states irrespective of what the other guy does.<br /><br />Let us say we start with 0000<br />flip all (1111)<br /><br />flip diagonal <br />Case 1: 1010, Case 2: 0101<br /><br /><br />Case 1: <br />flip all 0101<br />flip adjacent 1001 or 0011 or 0110 or 1100 <br />flip all 0110 or 1100 or 1001 or 0011<br />flip diagonal <br />flip all<br /><br />and the same in case 2<br />The above 6 steps ensure that you have seen all the possible 0s1s with even parity.<br /><br />So, flip any 3 now to change the parity and then repeat the above steps to make sure that you have seen all the cases. Since are operations are independent of what the other payer does, we are doing good whatever he does.<br /><br />So, flipping three and then the same operations as above would ensure the 8 strings with odd parity.<br /><br />flip any 3<br />flip all<br />flip diagonal<br />flip all<br />flip adjacent<br />flip all<br />flip diagonal<br />flip all<br /><br />So, we are done :)<br />We see all the possible bit strings.<br />:)<br />I hope that was clear.<br /><br />@pratyush.. Yes one tumbler option is redundant.. but your second comment is wrong in the sense that the person is blind and merely saying that there exists a path does not help. A sequence such that it does not matter where u start, you will cover all the states is important. <br /><br />@jaadu.. Thanx for the godmax solution. Love you max..Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-2175150233159956682009-11-25T13:04:03.243+05:302009-11-25T13:04:03.243+05:30If there does exist a deterministic strategy then ...If there does exist a deterministic strategy then I think we can assume the goblin to be a cheat - meaning that it will interpret an ambiguous order like one flip, two flip in whichever way it deems best.<br /><br />As for a deterministic solution I don't think any such solution exists but if the goblin is not a cheat (the blind gnome always directs which of the glasses to flip) then an asymptotically probable solution may existddEarthlinghttps://www.blogger.com/profile/07133281473683565210noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-41962953160132386472009-11-24T17:34:00.803+05:302009-11-24T17:34:00.803+05:30In fact, one tumbler option is redundant, me think...In fact, one tumbler option is redundant, me thinks..Pratyush Rathorehttps://www.blogger.com/profile/14085124243567744668noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-85175347188630193292009-11-24T17:34:00.804+05:302009-11-24T17:34:00.804+05:30Yes, there is a winning strategy..
Just as a hint:...Yes, there is a winning strategy..<br />Just as a hint:<br />State 1. If I have all 4 tumblers closed, there is a winning strategy from here on.<br />State 2: If I have diagonal elements off, I can definitely reach state 1 from here.<br />State 3: 2 elements closed: I can definitely reach either state 1 or state 2 from here.<br />State 4: 1 element closed: I can reach either state 3 or state 1 from here.<br /><br />All possible states covered.Pratyush Rathorehttps://www.blogger.com/profile/14085124243567744668noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-4913650229474012582009-11-24T12:30:37.831+05:302009-11-24T12:30:37.831+05:30yo yo!!
can you prove that the sequence you wrote ...yo yo!!<br />can you prove that the sequence you wrote will indeed produce all the sequences, no matter how the table is rotated?Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-27333001885565617462009-11-24T01:49:36.431+05:302009-11-24T01:49:36.431+05:30There are four kinds of flip that are possible:fli...There are four kinds of flip that are possible:flip all four,flip any 3,flip any two adjacent and flip any two diagonal.lets us call them flip4,flip3,flip2adj,flip2diag.Then following sequence is winning:flip4,flip2diag,flip4,flip2adj,flip4,flip2diag,flip4,flip3,flip4,diag2,flip4,flip2adj,flip4,flip2diag,flip4<br />This strategy surely leads to winnig strategyUnknownhttps://www.blogger.com/profile/17923995765018410791noreply@blogger.com