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

Comments

  1. Anonymous5:15 PM, October 29, 2009

    Here's a possible solution.
    The 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).

    ReplyDelete
  2. Pratik Poddar1:26 PM, October 31, 2009

    God max solution..
    Thanx..

    BTW, Who is this anonymous?

    ReplyDelete
  3. sid11:43 PM, April 29, 2010

    http://www.math.dartmouth.edu/~pw/solutions.pdf
    I believe this link will put this problem in perspective. (and also on some more problems :P)

    ReplyDelete
  4. Pratik Poddar4:21 PM, May 06, 2010

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

    ReplyDelete

Post a Comment

Popular posts from this blog

Buying Dimsums

Source: Alok Goyal (Stellaris VP, Ex-Helion VC) puzzle blog Problem: A fast food restaurant sells dimsums in boxes of 7 and 3. What’s the greatest number of dimsums a person cannot buy. Generalize it for p and q where p and q are relatively prime. I loved the puzzle. Hope you enjoy it too.
Read more

Fraction Brainteaser

Source: Sent to me by Gaurav Sinha Problem: Siddhant writes a Maths test and correctly answers 5 out of 6 Arithmetic questions and 20 out of 28 Geometry questions.  In total, Siddhant scores 25 out of 34.  Vaibhav writes another Maths test and correctly answers 20 out of 25 Arithmetic questions and 6 out of 9 Geometry questions. in total, Vaibhav scores 26 out of 34. Note that a) Vaibhav scores more than Siddhant b) Siddhant score better than Vaibhav in both individual topics -  5/6 > 20/25 and 20/28 > 6/9 How is it possible? 
Read more

Consecutive Heads

Let's say A keep tossing a fair coin, until he get 2 consecutive heads, define X to be the number of tosses for this process; B keep tossing another fair coin, until he get 3 consecutive heads, define Y to be the number of the tosses for this process. 1) Calculate P{X>Y} 2) What's the expected value of X 3) What's the expected value of Y This is probably the hardest puzzle I have ever put on my blog. Hence, I will post its solution in the post directly rather than on comment. Solution: 1) (Solved by me finally after 13 months :)) Make a state diagram. Let the state be (a,b) where a is the number of consecutive heads streak "A" is on currently and b is the number of consecutive heads streak "B" is on currently. So, (0,3) (1,3) are final accepted states and (2,0) (2,1) (2,2) (2,3) are failure states. If you get tails, your contribution to the state reaches to "0" f(State) = P(X>Y | "State" configuration initially) ...
Read more