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
- They can coordinate before the game starts; there is no communication
(neither explicit nor hidden - such as moving cards, etc.) during the game.
- No need to find the precise maximum; just try to make the probability
as large as you can.
- What happens as the number of people increases?
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:
- Person i will find his name if and only if in the random permutation
i belongs to a cycle of length at most 50.
For example, if we have 8 people and the permutation is 13572864,
then the cycles are
(1) (235) (4768).
- Everyone will find his name if and only if the random permutation has no
cycle of
length larger than 50.
- The probability that a random permutation has a cycle of length
k > 50 equals
binomial(100,k) * (k-1)! * (100-k)! / 100! = 1/k.
- The probability that a random permutation has a cycle of length > 50 equals
1/51 + 1/52 + ... + 1/100, which is approximately ln 100 - ln 50 = ln 2, or about
0.693.
- The probability that everyone will find his name is therefore approximately
1 - ln 2, or about 30.7%.
- As the number of people increases to infinity,
the same computation shows
that the
probability converges to 1 - ln 2.
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?