Skip to content
HTQHow To Quant
← Problem Bank

Ticket Line

CalcHard~25 min· Probability
Problem

The Problem

A queue has people, each holding either a $5 bill or a $10 bill. Tickets cost $5. The cashier starts with no change. People are served in queue order; each person tenders their bill and requires correct change if it's a $10.

How many of the possible orderings of $5-holders and $10-holders will allow the cashier to serve everyone without running out of change?

(This is the ballot problem / Catalan number setup, classic in quant interviews.)