Blind flipping
Four tumblers are placed at the corners of a square table. A blind gnome and an evil goblin take turns to play a game. The blind gnome gets to choose a subset of the four tumblers and flip them simultaneously. Effectively, he may choose “one tumbler”, “two diagonally opposites”, “two adjacent”, “three tumblers” or “four tumblers” lying in front of him. After flipping, if all four tumblers are upright, he wins the game! Otherwise, the game continues: the evil goblin rotates the table by an amount of his choice. Can the blind gnome win the game with a deterministic strategy?
Source: One of the questions in the placement paper of a quant company at another IIT
Update (11/12/09): Solution by Me, Jaadu and Ramdas in comments!!
Source: One of the questions in the placement paper of a quant company at another IIT
Update (11/12/09): Solution by Me, Jaadu and Ramdas in comments!!
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
ReplyDeleteThis strategy surely leads to winnig strategy
yo yo!!
ReplyDeletecan you prove that the sequence you wrote will indeed produce all the sequences, no matter how the table is rotated?
In fact, one tumbler option is redundant, me thinks..
ReplyDeleteYes, there is a winning strategy..
ReplyDeleteJust as a hint:
State 1. If I have all 4 tumblers closed, there is a winning strategy from here on.
State 2: If I have diagonal elements off, I can definitely reach state 1 from here.
State 3: 2 elements closed: I can definitely reach either state 1 or state 2 from here.
State 4: 1 element closed: I can reach either state 3 or state 1 from here.
All possible states covered.
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.
ReplyDeleteAs 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 existdd
Since many people have been asking me to explain Jaadu's and Pratyush argument, I am writing a long post now...
ReplyDeleteYes indeed:
flip all
flip diagonal
flip all
flip adjacent
flip all
flip diagonal
flip all
flip any 3
flip all
flip diagonal
flip all
flip adjacent
flip all
flip diagonal
flip all
would work..
Lets see how..
The number of states are 32 (Each tumbler up and down and whose chance it is, mine or the other person)
The number of operations on each step by me is 15 (all, 2 diagonal, 4 adjacent, 4 in groups of 3, 4 single flips)
We are ignoring the operation single flip. So, effectively its 11
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.
Let us say we start with 0000
flip all (1111)
flip diagonal
Case 1: 1010, Case 2: 0101
Case 1:
flip all 0101
flip adjacent 1001 or 0011 or 0110 or 1100
flip all 0110 or 1100 or 1001 or 0011
flip diagonal
flip all
and the same in case 2
The above 6 steps ensure that you have seen all the possible 0s1s with even parity.
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.
So, flipping three and then the same operations as above would ensure the 8 strings with odd parity.
flip any 3
flip all
flip diagonal
flip all
flip adjacent
flip all
flip diagonal
flip all
So, we are done :)
We see all the possible bit strings.
:)
I hope that was clear.
@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.
@jaadu.. Thanx for the godmax solution. Love you max..
@asad
ReplyDeleteThat'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.
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 :)
ReplyDeleteAnyways do take a stab at the 3 tumbler situation
I think PP gave a "proof" that it works, but how do we "come up" with such a solution?
ReplyDeleteI'll call DA (flip diagonal, then flip all), SA (side,all), CA (corner, all) as the 3 possible moves. All arguments are modulo rotation.
Notice that this is what let's us win: a table that looks like
1 0
0 1
has a _guaranteed_ solution (DA)
(at first thought, there is no such case for the triangle).
ALSO, this leaves the
0 0
1 1
and the
0 0
0 1
cases untouched. HENCE, we can safely do DA first.
Now, for the
0 0
1 1
case, we see that SA either solves it, or converts it to the first case, where DA was the solution.
So SA-DA solves this one.
AND, SA-DA leaves
0 0
0 1
untouched. HENCE we can safely apply it.
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.
So CA-DA-SA-DA will surely solve it.
Hence the total solution can be written as DA, SA-DA, CA-DA-SA-DA
nice.. thanx.. :)
ReplyDeleteSuppose there is a name written on each corner and an external referee. To the referee there are 15 states for table
ReplyDeleteviz 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.
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?
Answer should be at least 15. I show here its exactly 15.
Lets consider possible moves for blindfold:
S1. Flip All
S2. Flip Diagonal (2 types)
S3. Flip Adjacent (4 types)
S4. 1-flip (4 types)
S5. 3-flip (4 types)
Lets apply some of the moves on state 0 and analyze the following diagram:
_____________________
|__________________ |
|_______________ | |
|_________ | | |
| | | | |
0 1 2 3 4 5 6 7
| | | | | | | |
15 14 13 12 11 10 9 8
PS : all lines in the picture are reversible
S1 takes 0-15, 1-14, ....., 7-8 (lines between rows)
S2 takes 0- 5 (shown in the picture), 0-10
S3 takes 0-3, 0-6 (both shown in the picture), 0-12, 0-9
S5 takes 0-7(shown) and 0-14, 0-13, 0-11
The left out numbers on the first row can be reached from 0 by S4.
S1 is only deterministic move of the lot, rest are probabilistic.
Now if we combine the moves to the following operation:
C1 : (S1 - S2 - S1)
C1 has two deterministic moves and one probabilistic move.
This operation partitions states into four disjoint classes:
P1 : (0, 5, 10, 15)
P2: (1, 4, 11, 14)
P3: (2, 7, 8, 13)
P4: (3, 6, 9, 12)
Partition meaning if we start from any member of any Pi, and follow C1, we traverse rest of the elements of that partition.
For example: for P1 starting from 0, apply C1 to get either 0-15-10-5 or 0-15-5-10
Now challenge reduces to switching partitions. I consider following two operations for this:
C2 : (S3)
C3: (S5)
See C2 always takes P1 to P4 and P2 to P3 (eg C2 takes 0/5 to 3/6, 10/15 to 9/12)
and C3 always takes P1/P4 to P2/P3
PS: C2 is deterministic operation and C3 is probabilistic operation
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):
So one possible move is: (starting from 0)
C1-C2-C1 (This traverses P1 and P4 both)
-C3 (Switches from P4-P2/P3)
-C1-C2-C1 (This traverses both P2 and P3)
Counting total moves, it is 15.