Solution
One Bill in the Till
Show the problem again
A ticket costs $5. Twelve customers line up in uniformly random order: six of them pay with a $5 bill and six pay with a $10 bill (and need $5 change). The cashier starts with exactly one $5 bill in the till and no other money, and she can only give change from bills she has received or the one she started with. What is the probability that she can give every customer correct change when they reach the front? Give a reduced fraction.
Worked solution
**Answer: 13/28.** Let the till's surplus of $5 bills, minus the starting bill, perform a walk: +1 for a $5 customer, −1 for a $10 customer. The walk starts at 0, ends at 0 after 12 steps, and the cashier gets stuck exactly when the walk first reaches −2. Reflect a bad walk after its first visit to −2. It becomes a walk from 0 to −4, i.e. one with 4 up-steps and 8 down-steps, and this is a bijection onto all such walks (each of which must pass −2). So the number of bad orders is C(12, 4) = 495, out of C(12, 6) = 924. The good orders number 429, and 429/924 = 13/28. (Without the starting bill the answer would be the Catalan fraction 1/7; one spare bill more than triples it.)
Source: Variant of the classical theatre-queue (ticket-change) problem. Statement written for AxiomIQ.