Probability of following the right person

Question

The following question was found in my textbook on probability. It is a question from the math olympiade final in Belgium, edition 1992 (actually the Flemish part of Belgium, the contest is called 'De Vlaamse Wiskunde Olympiade). I gave it a shot. Below is the question and my attempt at a solution.

Through an informant in the underworld, the police have learned where a gang gathers. The identity of the gang members is unknown. An agent is tasked with shadowing the leader of the gang. He only knows that the gang leader is the tallest of five individuals, all of different heights. After the meeting, the gangsters leave the building one by one, leaving a quarter of an hour between each departure. The agent cannot see who the tallest person is and decides to let the first two go, then follow the first one who is taller than those who left before him. What is the chance that the agent shadows the right man?

According to my book, the correct answer should be $13/30$.

Attempt at a solution: There are a total of $5! = 120$ possibilities. We will count the favorable possibilities. Note that if the leader leaves the building first or second, the agent can not follow the leader. Therefore, we need to consider the leader leaving third, fourth or fifth.

• If the leader is the third person to leave: the agent will follow him, no matter the order the other gangsters appear in. Number of possibilities: $4! = 24$

• If the leader is the fifth person to leave: the second tallest gangster had to leave first or second in order for the agent to follow the correct person. There are 3 remaining possibilities for the other gangster leaving first or second. The order of the remaining two gangsters is fixed: from largest to smallest. Therefore, there are a total of $2\cdot 3\cdot 1 \cdot 1 = 6$ possibilities to follow the leader if he appears last.

• If the leader is the fourth person to leave: We distinguish two cases: If the second tallest gangster appeared first or second, there is no problem. Number of possibilities: $2 \cdot 3! = 12$. If the second talles gangster did not appear first or second, he needs to appear last. The third tallest gangster should then appear first or second, otherwise the agent will follow him. Therefore, there are $2\cdot 2\cdot 1 \cdot 1 = 4$ possibilities.

This totals $24 + 6 + 12 + 4 = 46$ cases.

Unfortunatly $46/120$ does not simplify to the desired answer.

Question: What cases am I missing? I'm also interested to know other approaches to this problem.

EDIT: as pointed out by Heropup and Bram28, I made a mistake in the part where the leader emerges last: the police only follows if a gangster is taller than all previous gangsters. Therefore, if the second tallest gangster left first or second, the police will follow the leader, no matter what order the other three gangster emerge. There are $2 \cdot 3! = 12$ possibilities instead of $6$.}

Answer 1

You are missing some cases. Let's rank the heights from $1$ to $5$ with $1$ being the leader (tallest) and $5$ being shortest. If the leader is fifth, then the second tallest gangster could be in the first position, e.g. $$(2,?,?,?,1)$$ or he could be in the second position, e.g., $$(?,2,?,?,1).$$ In each case, there are $3! = 6$ permutations of the remaining gangsters, so there should be $12$ such outcomes.

The rest of your reasoning is fine, and indeed, we have $$\frac{24+12+12+4}{120} = \frac{13}{30}.$$

Answer 2

There are $12$, not $6$, possible ways with the tallest person leaving last:

Like you say, the second tallest needs to have left first or second, and that will ensure that the agent follows the right person at the end, no matter how the other 3 gang members are leaving. So: $2$ possible positions for the second tallest person, times $6$ possible positions for the last 3 gang members, gives $12$ possible ways.

Answer 3

Enumerating all 120 permutations and then enumerating all successful permutations, to arrive at fraction 52/120, is certainly a possibility.

Another possibility is to calculate the probabilities directly; this is often simpler because you don't need to care about the positions of the irrelevant gangsters.

For instance, the probability that the leader is third is 1/5. You can see this directly without going the complicated route 24/120.

Calling L the leader, S the second-tallest and T the third-tallest and writing the probabilities equation that follows directly from your reasoning: \begin{align*} P(\text{follow L}) & = P(\text{L3}) \\ & + P(\text{L4})\times \big( P(\text{S1 or S2} \,|\, \text{L4}) + P(\text{S5} \,|\, \text{L4}) \times P(\text{T1 or T2} \,|\, \text{L4,S5}) \big) \\ & + P(\text{L5})\times P(\text{S1 or S2} \,|\, \text{L5}) \\ & = \frac 1 5 + \frac 1 5 \times \left( \frac 2 4 + \frac 1 4 \times \frac 2 3 \right) + \frac 1 5 \times \frac 2 4 \\ & = \frac {6+4+3}{30} = \frac{13}{30} \end{align*}