Brainteasers & Puzzles

The Ticket Line

2n people line up for 5-dollar tickets, half paying with a five and half with a ten, and the seller starts with no change. How likely is everyone served without a holdup?

solvedmedium1 min

A theater has 2n2n people waiting to buy a $5 ticket each. Exactly nn of them carry a single $5 bill and the other nn carry a single $10 bill, and the seller starts with no change. In a uniformly random order, what is the probability that everyone can be served, meaning the seller always has a $5 to give as change to a $10 customer?

Reveal solutionHide solution

#A walk that must stay non-negative

Let the number of $5 bills in the till walk up by one when a $5 customer pays and down by one when a $10 customer takes a five in change. Everyone is served exactly when this walk never falls below zero, since a $10 customer who arrives at an empty till cannot get change. With nn fives and nn tens, the order is a sequence of nn up-steps and nn down-steps.

#Count the good arrangements

Sequences of nn ups and nn downs that never dip below zero are Dyck paths, counted by the Catalan number Cn=1n+1(2nn)C_n = \tfrac{1}{n+1}\binom{2n}{n}. The total number of orders, choosing which positions hold the $10 customers, is (2nn)\binom{2n}{n}.

0no changestays at or above 0
customers in line
Each five adds a bill the till can later break, each ten removes one. Everyone is served exactly when this walk never dips below zero. Those Dyck paths are the Catalan number out of all arrangements, a fraction 1/(n+1).

#The probability

P(all served)=Cn(2nn)=1n+1.(1)\PP(\text{all served}) = \frac{C_n}{\binom{2n}{n}} = \frac{1}{n+1}. \tag{1}

The clean answer hides the reflection argument behind the Catalan count, where every blocked order maps one to one onto an arrangement with one extra ten, and that bijection is what collapses the ratio to 1n+1\tfrac{1}{n+1}.