No Change at the Box Office
Half the queue pays with coins, half with bills, and the till starts empty. How often does everyone get a ticket without waiting for change?

The third person has a dollar, and the till is empty: the queue is stuck. Press “New queue”, or click two people to swap them.
Watch the video
What’s going on
A ticket costs 50 cents. Ten people line up at the window: five hold a 50-cent coin and five hold a one-dollar bill. The cashier opens with an empty till.
A coin is easy: it goes into the till. A dollar is trouble: the cashier has to hand back a 50-cent coin, and the only coins in the till are the ones paid by people earlier in the line. If a dollar arrives while the till is empty, the queue is stuck.
The people stand in a random order. What is the chance that nobody gets stuck? Five coins and five bills sounds balanced, so a fair guess is “about half”. Press Run 1,000 queues in the scene above. Only about one queue in six goes through.
Draw the till as a mountain
Below the queue, the scene draws the number of coins in the till after each person. A coin is a step up, a bill is a step down. Five ups and five downs, so the line always ends where it started, at zero.
A queue goes through exactly when the line never dips below zero. The first time it touches −1, the red dashed line, someone is holding a dollar in front of an empty till.
Click two people to swap them and watch the line change. Moving coins to the front of the queue lifts the mountain; moving bills forward pushes it down.
Counting the stuck queues
How many orders are there? Choose which 5 of the 10 places hold the coins: 252 ways. To find the stuck ones, Vilenkin uses a beautiful trick. Get a stuck queue (press New queue until one gets stuck), then press Mirror the tail:
- Find the first person who gets stuck.
- Everyone behind them swaps: coins become bills and bills become coins.
- On the chart, the rest of the line flips upside down in the red −1 line.
Before the flip, the line was at −1 and had to climb back to 0, one step up. After the flip it has to go one step down instead, so it ends at −2. The new queue has 4 coins and 6 bills.
The trick works backwards too. Any line with 4 ups and 6 downs ends at −2, so it must cross −1 somewhere. Flip it after the first touch and you get back a queue of 5 + 5 that gets stuck. So stuck queues of 5 + 5 match one-to-one with queues of 4 coins and 6 bills, and there are 210 of those (choose 4 places out of 10 for the coins).
That leaves 252 − 210 = 42 good queues, and 42 out of 252 is exactly 1/6.
The general answer
With n coins and n bills there are C(2n, n) orders, and the mirror trick shows that C(2n, n + 1) of them get stuck. A little algebra turns the difference into a very short answer:
The chance that the queue goes through is 1/(n + 1).
One pair: 1/2. Five pairs: 1/6. A hundred pairs: less than 1 %. Move the slider to check. The numbers of good queues, 1, 2, 5, 14, 42, 132, … are the Catalan numbers, and they turn up all over mathematics.
Try it yourself
1. A coin in the till
The cashier starts with one 50-cent coin. The queue still has five coins and five bills. What is the chance now?
Answer
132 out of 252, a little over a half (11/21 ≈ 52%). Now a queue is stuck only if the line reaches −2. Mirror the tail in the −2 line: it then ends at −4, which means 3 coins and 7 bills. There are 120 such queues, so 252 − 120 = 132 go through. One spare coin changes the chance from 1/6 to more than 1/2.2. More coins than bills
Six people have coins and four have bills, and the till starts empty. What is the chance that nobody waits?
Answer
3/7. There are 210 orders (choose 4 places out of 10 for the bills). The line ends at +2. In a stuck queue, mirror the tail in the −1 line: the end moves from +2 to −4, which means 3 coins and 7 bills, and there are 120 such queues. So 210 − 120 = 90 orders go through, and 90/210 = 3/7. In general, with m coins and k bills (k ≤ m) the chance is (m − k + 1)/(m + 1).3. Brackets
How many ways are there to write three pairs of brackets correctly, so that every bracket that closes has an open one before it? For example, (()()) is fine, but ())(() is not.
Answer
Five: ((())), (()()), (())(), ()(()), ()()(). An opening bracket is a coin and a closing bracket is a dollar: a correct line of brackets is exactly a queue that never gets stuck. So the answer is the Catalan number for n = 3, which is 5.Go deeper
- The numbers 1, 2, 5, 14, 42, … are named after the Belgian mathematician Eugène Catalan, who studied them in the 19th century. They also count the ways to cut a polygon into triangles and many other things.
- In 1887 Joseph Bertrand asked a similar question about an election count: if A wins with more votes than B, how likely is it that A stays ahead during the whole count? It is called the ballot problem, and it is solved with the same kind of mirror trick.
- This puzzle and its picture come from Naum Vilenkin’s Combinatorics (1969), a much-loved Russian book of counting puzzles. Vilenkin also solves the version where the cashier starts with some coins.
Inspired by the problem «Очередь в кассу» in the book Combinatorics («Комбинаторика») by N. Vilenkin, 1969. The drawing by O. Dobrolyubova is reproduced from the book with its labels translated into English; the text and code are our own.
Comments
No comments yet. Be the first to share what you noticed.