4
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ Just to check: is the answer 326/720 = 163/360 ? $\endgroup$ – ace May 22 '15 at 20:47
  • $\begingroup$ @ace That's what I got in my answer. $\endgroup$ – Kevin May 22 '15 at 21:01
6
$\begingroup$

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}$

$\endgroup$
  • $\begingroup$ Got the same with a computer-aided pure brute force method. $\endgroup$ – ace May 22 '15 at 21:02
  • $\begingroup$ Congratulations on your escape! I didn't follow all of your answer, so constructed my own, shorter, one :-) $\endgroup$ – Rand al'Thor May 23 '15 at 0:42
  • $\begingroup$ @randal'thor I hate to ask, since you just kidnapped me, but... ;-) What about my answer isn't clear? Is there something specific, or is it just generally hard to follow? $\endgroup$ – Kevin May 23 '15 at 1:59
  • $\begingroup$ @Kevin It was nothing personal - I just couldn't tell one Kevin from another at that stage ;-) I admit that I didn't have a proper read through your answer, since I already knew I could write a shorter one. It looks very similar to mine actually, only with more words; and the inductive $P_n$ notation makes it a bit more unwieldy. Sorry if I sounded too critical! There's no doubt you were the first to get and justify the right answer. $\endgroup$ – Rand al'Thor May 23 '15 at 10:14
  • $\begingroup$ Well done! Correct answer! $\endgroup$ – leoll2 May 23 '15 at 14:37
3
$\begingroup$

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}.$

$\endgroup$
  • 1
    $\begingroup$ Good job! This is slightly clearer than Kevin's answer, you deserve an upvote, but he was faster and his answer is still complete :-) $\endgroup$ – leoll2 May 23 '15 at 14:37
1
$\begingroup$

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!

$\endgroup$
-1
$\begingroup$

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!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.