There is a classical memory game called concentration that you can play with a deck of cards. Let N be a positive integer, and suppose that you have a deck of 2N cards labeled 1,1,2,2, \ldots, N,N. (Cards with the same value are indistinguishable.)
You start by shuffling the deck of cards and laying them face-down on a table in front of you. At each turn, you pick two face-down cards and flip them face-up.
- If they do not match, you flip them back over.
- If the cards match, then those cards remain face-up for the rest of the game.
The game ends when all the cards are face-up.
Throughout the entire game, we will assume you have a perfect memory.
Normal concentration isn’t that fun if you play it with a perfect memory. Find a strategy that is guaranteed to finish the game in at most 2N moves.