This puzzle again is from Haidong's website.
There are n people, each with a unique number from 1 to n. There are n identical lockers, each of which contains a paper with a unique number from 1 to n on it. However, you have no idea which locker contains what number. The purpose is for everyone to find the locker with his own number. Each one can open at most n/2 lockers and, once he looks at the number, he has to close the locker. If another person wants to see the same locker, he has to open it again himself. They can't exchange information with each other. Prove that there exists a certain constant that no matter how big n is, those people can always devise a strategy so all of them can find their own numbers with probability larger than that constant.
Note: this is surprising because if everyone picks n/2 lockers independent of other people, the probability that all of them find their own numbers is 1/(2^n), which goes to 0 as n goes to infinity.
I don't have a solution to this problem and the hint says "Use permutation theory from the group theory". Also, the non-zero probability obtained is 1 - ln 2, which is approximately 0.3. Someone please help me with this.
Update (11/12/09) Solution posted by "Anonymous" in comments!!!