Queue in the bank

Question

Six men are queuing in the bank when the clerk decides to take a break for 10 minutes! Before leaving, he gives to the six men a numbered ticket, in the same order of the queue (ticket #1 to the first man, #2 to the second, etc.).

After a while, when the clerk returns, the men become terribly confused and start pushing each other to become the first in line, not worried about their tickets.

Trying to calm down the men, the clerk says, "Stop! Let's make a game! There is a chance that all of you will receive twice the money you're asking, but otherwise you won't get anything! Let me explain the rules.

"The last person in the queue at this moment checks his ticket number. If it's not 6 (in which case the game immediately ends), he occupies the position suggested by his ticket. Then, whoever was previously standing in that position checks his ticket, too. If it's 6, he goes to the end of the queue and the game ends, but otherwise he goes to the position indicated by his ticket, and so on. The game ends when someone, looking at his ticket, goes to the sixth position. You win the money only if, at the end of the game, you're all in the correct positions as indicated by your tickets."

What's the probability that the six men get double the money?

Example: The sixth man looks at his ticket and reads 4, so he goes to the 4th position. Now the man who previously was 4th looks at his ticket and reads 6, so he occupies the last position. In this case, they win only if the men occupying the first, second, third and fifth position already were in the correct position (ergo they respectively had the tickets 1,2,3,5).

Answer 1

Here's a long, rather brute-force calculation:

There is a $\frac{1}{6}$ chance that the first person to check his ticket has ticket #6. If this is the case, then the men win the game if they happen to already be in the right order, which happens with probability $\frac{1}{5!} = \frac{1}{120}$. Otherwise, let the probability that the men win once the person at the end of the line switches positions be $P_1$. (We will calculate the value of $P_1$ below.) Altogether, then, the probability that the men with the game is

$\frac{1}{6}(\frac{1}{120}) + \frac{5}{6}P_1$

Now, we calculate $P_1$. Once the first man moves into position, there is a $\frac{1}{5}$ chance that the second man has ticket #6. If this is the case, then we know that the first and second men are in the correct positions once the second man moves to the back, so the probability that the men win is the probability that the other four men are in the correct positions, or $\frac{1}{4!} = \frac{1}{24}$. Otherwise, let the probability that the men win once the second man moves into position be $P_2$. The value of $P_1$ in terms of $P_2$ is therefore

$\frac{1}{5}(\frac{1}{24}) + \frac{4}{5}P_2$

We continue recursively until we reach the base case where the sixth man to move is the one holding ticket #6:

• Once the third man moves into position, he has ticket #6 with probability $\frac{1}{4}$ and in that case, the chances that the remaining three men are in position is $\frac{1}{3!}$. Hence, $P_2 = \frac{1}{4}(\frac{1}{6}) + \frac{3}{4}P_3$.
• Once the fourth man moves into position, he has ticket #6 with probability $\frac{1}{3}$ and in that case, the chances that the remaining two men are in position is $\frac{1}{2!}$. Hence, $P_3 = \frac{1}{3}(\frac{1}{2}) + \frac{2}{3}P_4$.
• Once the fifth man moves into position, he has ticket #6 with probability $\frac{1}{2}$ and in that case, the only remaining man must be in the correct position. Hence, $P_4 = \frac{1}{2}(1) + \frac{1}{2}P_5$.
• If the final man has ticket #6, then the men must win. Hence, $P_5 = 1$.

Working our way back up, calculating exact values for $P_1$ through $P_5$, we find:

• $P_4 = \frac{1}{2}(1) + \frac{1}{2}P_5 = \frac{1}{2}(1) + \frac{1}{2}(1) = 1$
• $P_3 = \frac{1}{3}(\frac{1}{2}) + \frac{2}{3}P_4 = \frac{1}{3}(\frac{1}{2}) + \frac{2}{3}(1) = \frac{5}{6}$
• $P_2 = \frac{1}{4}(\frac{1}{6}) + \frac{3}{4}P_3 = \frac{1}{4}(\frac{1}{6}) + \frac{3}{4}(\frac{5}{6}) = \frac{2}{3}$
• $P_1 = \frac{1}{5}(\frac{1}{24}) + \frac{4}{5}P_2 = \frac{1}{5}(\frac{1}{24}) + \frac{4}{5}(\frac{2}{3}) = \frac{13}{24}$

And finally, the overall probability that the men win the game is

$\frac{1}{6}(\frac{1}{120}) + \frac{5}{6}P_1 = \frac{1}{6}(\frac{1}{120}) + \frac{5}{6}(\frac{13}{24}) = \frac{163}{360} = 0.452\overline{7}$

Answer 2

Kevin (who has successfully escaped from my labyrinth) has the right final answer, but here's a shorter, simpler, and hopefully more intuitive proof.

• The probability that the game ends immediately is $\frac{1}{6}$ (the man at the back has ticket #6). In this case, they get double their money with probability $\frac{1}{5!}$.
• The probability that it ends after the first man moves into position is $\frac{5}{6}\times\frac{1}{5}$ (the man at the back doesn't have ticket #6 but the man he replaces does). In this case, they get double their money with probability $\frac{1}{4!}$.
• The probability that it ends after the first two men move into position is $\frac{5}{6}\times\frac{4}{5}\times\frac{1}{4}$ (neither the man at the back nor the man he replaces has ticket #6 but the next man does). In this case, they get double their money with probability $\frac{1}{3!}$.
• Similarly, the probability that it ends after the first three men move into position is $\frac{5}{6}\times\frac{4}{5}\times\frac{3}{4}\times\frac{1}{3}$ and in this case they get double their money with probability $\frac{1}{2!}$.
• Similarly, the probability that it ends after the first four men move into position is $\frac{5}{6}\times\frac{4}{5}\times\frac{3}{4}\times\frac{2}{3}\times\frac{1}{2}$ and in this case they get double their money with probability $\frac{1}{1!}$.
• Finally, the probability that it ends after the first five men move into position is also $\frac{5}{6}\times\frac{4}{5}\times\frac{3}{4}\times\frac{2}{3}\times\frac{1}{2}$ and in this case they get double their money with probability $1$ since everyone's in position.

So the game is equally likely to end at any of the six possible times, and the answer is $\frac{1}{6}\times(\frac{1}{5!}+\frac{1}{4!}+\frac{1}{3!}+\frac{1}{2!}+\frac{1}{1!}+1)=\frac{1+5+20+60+120+120}{720}=\frac{326}{720}.$

Answer 3

Lets think of the problem in terms of permutations. The initial positions of the 6 men form one of 6! permutations. The clerk's action is to apply the cycle of the permutation containing 6 (see "Cycle notation"). This sorts a subset of the men.

E.g the ordering 351642 corresponds to the permutation (13)(2645). The clerk applies the (2645) part to make the order 321456.

So now the problem is to calculate how many permutations have either a single cycle or all cycles not containing 6 already sorted. Consider each possible length of the subcycle containing 6. Adding a term for each of these possibilities gives $1+5+5*4+5*4*3+5*4*3*2+5*4*3*2*1 = 326$.

• 1 way to have 6 on its own (everything already sorted)
• 5 ways to swap 6 with something
• $5*4$ ways to form a triple
• etc.

The final probability is thus 326/6!

Answer 4

My answer

32 / 6! = 32 / 720

Considering Cm,n as combination of m elements for each n (or whatever is the proper wording in english), the total probability is the sum of probabilities for the required number of replacements until the number 6 gets to the end of the line:

0 replacement => C5,0 = 1
1 replacement => C5,1 = 5
2 replacements => C5,2 = 10
3 replacements => C5,3 = 10
4 replacements => C5,4 = 5
5 replacements => C5,5 = 1

total probability = (1 + 5 + 10 + 10 + 5 + 1) / 6!