At a theater ticket office, $2n$ people are waiting to buy tickets. $n$ of them have only \$5 bills, and the other $n$ people have only \$10 bills. The ticket seller starts with no change. The price of a ticket is \$5. **Question:** What is the probability that everyone will be able to buy their ticket without any problem with change? Encode the line as a walk: assign $+1$ to each \$5-bill customer and $-1$ to each \$10-bill customer. The cashier can serve everyone if the partial sums of this walk never go negative. Instead of counting paths that satisfy the condition directly, count the **bad paths** — those that touch level $-1$ at some step — and subtract from the total $\binom{2n}{n}$. To count bad paths, apply the reflection principle: reflect the portion of the path **after** its first visit to $-1$ across the line $y = -1$. ### Preamble: Definitions and Modeling **Encoding the line as a walk.** For each customer, define the random variable $$ X_i = \begin{cases} +1 & \text{if the } i\text{-th customer has a \$5 bill}, \\ -1 & \text{if the } i\text{-th customer has a \$10 bill}. \end{cases} $$ Intuitively, $+1$ means the cashier receives a \$5, and $-1$ means the cashier must give back a \$5 as change. Define the **partial sum** (cumulative walk): $$ S_k = \sum_{i=1}^{k} X_i, \qquad S_0 = 0. $$ Since there are exactly $n$ customers of each type, the walk satisfies $S_{2n} = 0$. **Success condition.** The cashier can serve everyone in order if and only if the till never goes negative, i.e., $$ S_k \geq 0 \quad \text{for all } k \in \{1, 2, \ldots, 2n\}. $$ ### Step 1 : Total Number of Paths A path from $(0, 0)$ to $(2n, 0)$ is determined by choosing which $n$ of the $2n$ steps are $+1$. The total count is: $$ \binom{2n}{n}. $$ All $\binom{2n}{n}$ sequences of $n$ pluses and $n$ minuses are equally likely. So: $$ P(\text{success}) = \frac{\#\{\text{paths with } S_k \geq 0 \text{ for all } k\}}{\binom{2n}{n}}. $$ We now count the numerator. ### Step 2 : Counting Bad Paths Instead The goal now is to find $\#\{\text{paths with } S_k \geq 0 \text{ for all } k\}$, so we need to count how many paths have a cumulative sum that is always $\geq 0$. It is not easy to count the successful paths directly, so instead we will find a way to count the **bad** paths — those that violate $S_k \geq 0$ at some point, i.e., paths for which $$ \exists\, k \in [1, 2n] \text{ such that } S_k = -1. $$ It turns out that bad paths are easier to count, and once we know their number, we can deduce the count of good paths by subtraction. A path is bad if and only if it touches level $-1$ at some step (since the walk has unit steps, going below $0$ means first hitting $-1$). Let $$ \tau = \min\{k : S_k = -1\} $$ be the **first hitting time** of level $-1$. ### Step 3 : Using Reflection to Count bad paths For a bad path, **keep the portion from $0$ to $\tau$ unchanged**, and **reflect the portion from $\tau$ to $2n$ across the horizontal line $y = -1$**: - The point $(\tau, -1)$ lies on the axis of reflection and stays fixed. - The original endpoint $(2n, 0)$ has height $0$, which is at distance $1$ above $y = -1$. Its reflection has height $-2$, so it becomes $(2n, -2)$. This produces a path from $(0, 0)$ to $(2n, -2)$. Such a path has $2n$ steps with net change $-2$. If it has $a$ up-steps and $b$ down-steps: $$ a + b = 2n, \qquad a - b = -2 \;\;\Longrightarrow\;\; a = n - 1,\; b = n + 1. $$ The number of such paths is: $$ \binom{2n}{n-1} = \binom{2n}{n+1}. $$ (The two binomials are equal by symmetry $\binom{2n}{k} = \binom{2n}{2n-k}$.) $$ \boxed{ \text{So the number of bad paths is :} \binom{2n}{n-1} } $$ ### Step 4 : Count Good Paths $$ \#\{\text{good paths}\} = \binom{2n}{n} - \binom{2n}{n-1}. $$ Simplify using: $$ \binom{2n}{n-1} = \frac{(2n)!}{(n-1)!\,(n+1)!} = \frac{n}{n+1} \cdot \frac{(2n)!}{n!\,n!} = \frac{n}{n+1}\binom{2n}{n}. $$ Therefore: $$ \#\{\text{good paths}\} = \binom{2n}{n} - \frac{n}{n+1}\binom{2n}{n} = \frac{1}{n+1}\binom{2n}{n}. $$ ### Step 5 : Final Probability $$ P(\text{success}) = \frac{\frac{1}{n+1}\binom{2n}{n}}{\binom{2n}{n}} = \frac{1}{n+1}. $$ so : $$ \boxed{ P(\text{success}) = \frac{1}{n+1}. } $$

Counting Paths on a 2D Grid

Answer