Brainteasers & Puzzles

The Ticket Line

n customers hold fives, n hold tens, and the seller starts with no change. Serving everyone requires each prefix of the line to hold at least as many fives as tens, a ballot condition counted by the Catalan numbers, giving probability 1/(n+1).

solvedmedium1 min

A theatre 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}.