Four Cards, Gnome, and Goblin

Another interesting puzzle, Four Cards from Gurmeet Manku's Puzzle collection

Four cards are placed on a square table, one card at each corner. A blind gnome and an evil goblin take turns to play the following game. The blind gnome gets to choose a subset of the four cards and flip them simultaneously. If all four cards are face up, he wins the game. Otherwise, the evil goblin get to rotate the table by an amount of his choice. Show that for any initial configuration of cards chosen by the evil goblin, the blind gnome can win the game in a finite number of steps with a deterministic strategy.

To get a better start with the problem, let me simplify it a little. In the modified problem, the gnome wins if all cards face the same. Example, either all cards face up, or all cards face down. This is a simpler problem.

Now lets take the simplified version. Consider the 4 cards on the table. Removing all the symmetrical configurations, there are just three distinct configurations of cards on the table, apart from the winning configuration. For notational convenience, I will use D for a cards facing down, U for a card facing up.

Case 1: Just one face differs from others.
   |D D|
   |D C|

Case 2: two cards up and two down on the same side.
   |D C|
   |D C|

Case 3: Two cards up and two down diagonally.
   |D C|
   |C D|

The gnome has to know about which kinds of flips matter. He cant judge about which cards to flip, so he only has the option of differentiating flips by count and orientation. Again, there are just 3 kinds of flips that matter. Flipping one of them, flipping 2 diagonally, or flipping 2 sideways.

Now map the transformations possible by these flips on the 3 types of configuration.

1 <-diag-> 1
1 <-side-> 1
1 <-one->  {2, 3, win}

2 <-diag-> 2
2 <-side-> {3, win}
2 <-one->  1

3 <-diag-> win
3 <-side-> 2
3 <-one->  1

Lets map the transformations for a the winning game. We would have to keep track of set possible cases that will occur in each transformation. Observe that case 1 is most distant from wining, case 2 the second most, and case 3 the closest. What we would like to achieve is a way to reduce the possible number of configuration, as we work with transformations. So if there is a case 3, finish off with it and so on. If a win happens in between, game ends automatically. So we only have to consider in the cases otherwise. Here's the solution

{1,2,3} <-diag-> {1,2} <-side-> {1,3} <-diag-> {1} <-one-> {2,3} <-diag-> {2} <-side-> {3} <-diag-> {sure win}

To the main problem. If the only winning position is all faces up, the game essentially remains the same except the number of configurations and transformations. Now the number of combinations that matter is 5. The types of transformations remain the same, except for the special case of flipping all the cards. Its only used in one case. For rest of the configurations, flipping all doesn't change anything. Here's a list cases and the transformations which are useful. I am showing win case if its the only case.

Case 1:
   |U U|   1 <-diag-> {1,2} ; 1 <-side-> {1,2} ; 1 <-one-> {3,4,5}
   |U D|

Case 2:
   |D D|   2 <-diag-> {1,2} ; 2 <-side-> {1,2} ; 1 <-one-> {3,4,5}
   |D U|

Case 3:
   |U U|   3 <-diag-> {3} ; 3 <-side-> {4,5} ; 3 <-one-> {1,2}
   |D D|

Case 4:
   |U D|   4 <-diag-> {5} ; 4 <-side-> {3} ; 4 <-one-> {1,2}
   |D U|

Case 5:
   |D D|   5 <-diag-> {4} ; 5 <-side-> {3} ; 5 <-one-> {2} ; 5 <-flipall-> {sure win}
   |D D|

Now the solution for the original problem. What we would try to do it get all the cases to case 5, and then flip-all. Flip all is represented by fa.

{1,2,3,4,5}
<-fa->   {1,2,3,4}
<-diag-> {1,2,3,5}
<-fa->   {1,2,3}
<-side-> {1,2,4,5}
<-fa->   {1,2,4}
<-diag-> {1,2,5}
<-fa->   {1,2}
<-one->  {3,4,5}
<-fa->   {3,4}
<-diag-> {3,5}
<-fa->   {3}
<-side-> {4,5}
<-fa->   {4}
<-diag-> {5}
<-fa->   {sure win}

Essentially, what we did is to take the following action at each step.

• if: 5 one of possible states then flip-all
• else if: 4 among the possible states flip diagonal
• else if: 3, flip side
• else if: 2 or 1, flip one

So gnome can win the game in 15 steps or less.