A group of N people is being tested for their ability to cooperate and plan. A game is set up as follows. A deck of N cards is secretly created. The numbers 1...N appear on the front of the cards, and the N peoples' names appear on the back of the cards.

A room is prepared with the cards laid out on a table, number side up. The people are brought into the room one at a time. A person's goal when visiting the room is to find her own card. She is allowed to turn over up to N/2 cards in this quest. After each visit to the room, the cards are returned to their original state.

The group wins if every single one of them finds her own card. The group loses if any one of them fails. The group can meet and plan their strategy before the game starts, but once the game starts, no further communication is allowed.

The problem is to find a strategy for the group which gives a significant probability of victory i.e. more than some positive constant.

Wait a minute! It's easy to see that (no matter what) each person has at most a 50% chance of finding her own name. This clearly implies that the group collectively, can win with probability at most (1/2)^N. So the puzzle is impossible, right?