Theater Ticket Queue Probability

This question describes a finite queueing-style scenario where payments and change form a constrained random process. Candidates must think about all possible orders in which two types of customers can appear and understand when the cashier runs into trouble because of insufficient change. The setup is symmetric and simple to state, but the real difficulty lies in translating the "never run out of change" requirement into a clean mathematical condition on the sequence of arrivals. Variants of this structure often appear in quantitative finance interviews and probability-heavy quant research roles, where comfort with combinatorial models of path constraints is valued.

Solving it leans on discrete-time stochastic process ideas, combinatorial counting, and path-wise constraints. Strong answers typically bring in lattice-path interpretations, recognize classical structures behind the scenes, and reduce the probability to a ratio of two well-understood counts. Interviewers look for facility with conditioning on paths, mapping "good" versus "bad" trajectories, and using symmetry or bijections rather than brute-force enumeration. Clarity about why the non-negativity condition is central, and how it filters the total sample space, is often more important than just producing the final probability.

What it tests

This problem class is governed by the principle of constrained lattice paths, specifically Dyck paths, which model processes where a running total must never become negative. The key is that each 'up' step (here, a \$5 bill) must always be sufficient to cover each 'down' step (a \$10 bill), so the cumulative sum never dips below zero. The total number of unconstrained sequences is simply the number of ways to arrange the two types of steps, but the constraint dramatically reduces the count. The reflection principle and Catalan numbers arise because the constraint is equivalent to counting the number of non-negative walks that start and end at zero, which is a classic combinatorial structure. This pattern holds because any violation (a negative cumulative sum) can be mapped bijectively to a forbidden sequence, allowing us to subtract the 'bad' cases from the total.