Yoak: Face Up
This is a classic puzzle from Martin Gardner that also appears in Peter Winkler’s Mathematical Puzzles: A Connoisseur’s Collection. (At least I think so. My copy is buried in a box somewhere.)
First, a warm-up puzzle:
You’re blindfolded and I will place two cards on the table in front of you, each either face up or face down at my option. We’ll then play a game taking turns. On your turn, you may turn over either one or both cards. On my turn, I may either swap the positions of the cards without changing which might be face up or not at my option. You are unable to detect whether or not I’ve made a swap. You win as soon as both cards are face up. Your task is to identify a set (deterministic) strategy that you can use such that regardless of how I place and switch cards you are sure to win.
[spoiler]
The strategy that you can employ to be sure to win this version is to flip both cards on your first turn, and then flip one card on your next turn. Then finally you flip both cards on your final turn.
There are three states the cards can start in: both up, both down and one of each. If they are both up, you win without taking a turn. If they are both down, your first turn causes you to win. If one is up and one is down, you maintain this state (though you reverse the cards) in your first turn. On your second turn, you either turn up the down card (and win) or turn down the up card. In this latter case, your third step of flipping both cards makes you a winner.
[/spoiler]
Now, consider a tougher version of the problem. You now have four cards, each on the corner of a square table. The setup is the same as before. You’re blindfolded and I place the cards faces up or down in a way that I think will stump you. You flip 1,2,3 or all cards on your turn, and then I either leave the table alone or rotate it 90, 180 or 270 degrees. You can’t tell if the table has turned. You then do some more flipping, etc.
(Note that I can’t arbitrarily re-order cards — only rotate the table. Their relative position remains constant. I didn’t labor this point in the first puzzle as with two cards it isn’t a distinction. You can imagine that the rules are identical and the table can only be rotated 180 degrees.)
Can you identify a pattern of steps you can take that will ensure victory regardless of my placements and turning?
The Math Factor in iTunes
RSS feed
Comments RSS
mathbun.com
Blaine said,
May 28, 2009 at 6:47 pm
Although it is played with cards, this puzzle has essentially the same solution as one I posted recently on my website:
http://puzzles.blainesville.com/2009/05/friday-fun-rapidly-rotating-electronic.html
[spoiler]My puzzle assumed that you couldn’t start with all cards(switches) facing the same way. My solution required no more than 7 steps. With the additional possibility of all cards up or down, you would need one extra step where you flip any cards you like. So the total steps would be 8 in this case.
Summary:
Step 1: Flip any cards you like (1, 2 or 3)
Step 2: Flip two opposite cards.
Step 3: Flip two adjacent cards.
Step 4: Flip two opposite cards.
Step 5: Flip one card (or equivalently, three cards)
Step 6: Flip two opposite cards.
Step 7: Flip two adjacent cards.
Step 8: Flip two opposite cards.[/spoiler]
jyoak said,
May 28, 2009 at 9:55 pm
Blaine, I haven’t attempted to verify your solution yet, but you seem to write that your steps 2 through 8 are what is required if the cards can’t all start face-down and that step 1 eliminates this problem. That isn’t so. The step 1 that would be required would be turning over all of the cards in step one.
That said, I’m still doubtful that these problems work out to be the same. Your problem on your site calls for the switches to be either all on or all off. All face down isn’t a solution set here.
I’ll look in more detail in a couple of days. Unfortunately I’m packing right now for a trip and I will probably have little time over the next four days or so.
Stephen Morris said,
May 31, 2009 at 2:53 pm
A nice tricky problem. I think I have a solution.
I’m afraid I can’t make the spoiler tag work properly. I’ve tried several times including copying from another comment.
So don’t read this if you don’t want to know my solution.
[spoiler] Suppose the starting states of the four cards is a, b, c, d. I always show the cards in the starting orientation regardless of how the table is rotated.
1) Starting position
a b
c d
2) Flip all cards. We now have covered all scenarios where zero of four cards are flipped.
-a -b
-c -d
3) Flip two cards down a diagonal. As we don’t know the orientation of the table we don’t know which diagonal will be flipped.
a –b OR -a b
-c d c -d
4) Flip all cards. This gives the same state as if we had flipped the other diagonal in step 3. We have now covered all states where a diagonal is flipped.
-a b OR a -b
c -d -c d
5) Flip two cards along a side. Again we don’t know which side is flipped, nor which of the two states we are in at step 4. However we do know that we will have a state with one side flipped relative to the starting position at step 1)
a b
-c -d
Steps 6-8 repeat steps 2-3. This gives all four states with this property (one side flipped). To see this you need to see that each of these states can be got from any other by flipping a diagonal or flipping all the cards.
I only show one possibility. The order will depend on the table rotations.
6) Flip all cards, as step 2.
-a -b
c d
7) Flip a diagonal, as step 3. In this case a and d are flipped.
a -b
c -d
8) Flip all cards, as step 4.
-a b
-c d
Now we have covered all eight possibilities with an even number of cards flipped relative to the starting position.
There are a further eight possibilities with an odd number of cards flipped. To get these we flip one card and then repeat the previous steps.
Flipping one card will put into some state with an odd number of cards flipped. As the further steps lead to an even number of cards being flipped and are distinct this will give us all eight possibilities with an odd number flipped.
I show one possibility.
9) Flip one card. In this case a is flipped.
a b
-c d
10) Flip all cards, as step 2.
-a -b
c -d
11) Flip two cards down a diagonal, as step 3. In this case a and d are flipped.
a –b
c d
12) Flip all cards, as step 4.
-a b
-c -d
13) Flip two cards along a side, as step 5. In this case we flip a and c.
a b
c -d
14) Flip all cards, as step 6.
-a -b
-c d
15) Flip a diagonal, as step 7. In this case we flip a and d.
a -b
-c -d
16) Flip all cards, as step 8.
-a b
c d
So there we are. All sixteen possibilities accounted for. At some point they must all be face up! [/spoiler]
Stephen Morris said,
June 1, 2009 at 5:58 pm
Blaine’s solution is the same as mine if you take into account the one difference between his puzzle and this one.
Blaine said,
June 8, 2009 at 9:10 pm
Yes, I did miss the wording of all face up… I took that to mean all the same direction (face up *or* face down). There’s still a complication because the puzzle states that you can flip 1, 2 or 3 cards… flipping all 4 isn’t included.
Let me think a bit more.
jyoak said,
June 9, 2009 at 9:33 am
“You flip 1,2,3 or all cards on your turn…”
I’m not sure if you can do it without being able to turn all the cards.