### Find your number

This puzzle again is from Haidong's website.

Problem:

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!!!

Problem:

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!!!

Here's a possible solution.

ReplyDeleteThe prisoners randomly allot each other numbers from 1 to n. Let us assume that prisoners are A1 A2 A3...An and each Ai has received number i.

Now the prisoner Ai goes in, checks ith box(lets call this box as his first box). Then he checks the box of that prisoner whose name he found in the first box. Then he checks the box of that prisoner whose name he found in the second box.. and he continues on till he either finds his name in a box, or his n/2 chances are over.

Note that we are basically searching for cycles in the permutation of prisoner names. So a prisoner will not get his name only if there is a cycle whose length is > n/2.

Number of permutations with a cycle of length exactly k > n/2 is given by nCk*(k -1)!*(n -k)!. Total no. of permutations is n!. Therefore probability comes out as 1/k. So probability of failure is 1/(n/2)+1(n/2+1)+...(1/n). Noting that the harmonic series goes as ln(n), this sum goes as ln(n)-ln(n/2)=ln(2). Probability of success is 1-ln(2).

God max solution..

ReplyDeleteThanx..

BTW, Who is this anonymous?

http://www.math.dartmouth.edu/~pw/solutions.pdf

ReplyDeleteI believe this link will put this problem in perspective. (and also on some more problems :P)

Thanx Sid.. Awesome set of problems.. Will post them one by one for discussion :)

ReplyDelete