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.
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.
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?