100 cards


The names of 100 people (all names are different) are written on 100 cards. The 100 cards are taken to a closed room, randomly shuffled and put face down in a row.

Each person in turn enters the room and turns over cards one after another until either he finds the card with his name or he has turned 50 of the 100 cards. After that he leaves the room, without communicating anything to the others, and the cards are all turned back face down before the next person comes in.

How large can they make the probability that everyone will find the card with his name?

(If everyone turns 50 cards at random, the probability will be (1/2)100, which is about 8 * 10-31).


Notes
Answer

Let the names be 1, 2, ..., 100.

Consider the following strategy: Person number i starts by turning over card number i; let j be the number on it. If j = i, he is done. Otherwise, he turns over card number j; let k be the number on it. If k = i, he is done. If not, he turns over card number k. He then continues in this manner, until either he finds the card with number i, or he has turned over 50 cards.

We have:


I heard this from Assaf Naor, who heard it from ...

This solution is due to Sven Skyum.

References:




Another question

How large can they make the probability that NO ONE will find the card with his name?



GO TO
Sergiu Hart's
Puzzles
Main Menu