Closed boxes in a room are numbered 1 to 4. Each box randomly contains a card uniquely paired with one of 4 players. For example boxes 1 to 4 might contain cards 3,1,2,4 in that order. Player 1 must enter the room and open box 1. If that box does not contain card 1 then he/she must open the box indicated by the card in box 1. Player 2 must start with box 2 etc. but players can enter the room in any order. No communication is allowed between players. In the example above player 1 would open box 1 then box 3. A maximum chain of two boxes are allowed, so player 1 would not find his/her card. Player 4 would succeed at the first box. What is the probability that all four players will find their numbers in two goes each or fewer?

Results from Computer Simulation: (Maximum Chain ie looks allowed = Players/2)

Players=Boxes                    10         100          1000       10000       Very large

Probability of Success        0.354    0.312       0.308      0.302       1-ln2=0.30685

The solution comes from considering the chain of boxes a player opens. For 100 players, the maximum chain must be 50. As shown below the probability of a chain of 51 is 1/51, similarly for 52 etc. The sum of the harmonic probability sequence 1/51 + 1/52 +1/53 + ... +1/100 is shown below to be approximately ln 2 which is nearly 0.7. Hence the probability of success is just over 0.3.

Prob of chain of length k: The number of combinations is nCk. Inside the chain there are (k-1)! permutations, not k!, since the last card in a chain must match the first box. Cards outside the chain can be permuted (n-k)! ways, Multiplying out and dividing by n! gives the required probability 1/k. Hence the probability of failure for 100 players is  1/51+1/52+1/53...+1/98+1/99+1/100.

The Prob of failure is close to the integral of 1/x from 51 to 100 which is ln(100)-ln(51) ie close to  ln 2. As the number of players increases, the probability of failure gets closer and closer to ln 2. What is the answer for 100 players with a maximum chain of 40?


To join the email list:

FaceBook YouTube Songs

YouTube -- Facebook -- CD Baby --

iTunes Albums