At a ticket counter, eight people are standing in line. Four of them have one 100 Ft note each, and the other four have one 200 Ft note each, their order is random. The ticket price is $100 \mathrm{Ft}$, and the cash register is initially empty. Everyone wants to buy one ticket. What fraction of the possible line-ups allow the cashier to sell the tickets without running out of change?
I. solution. There is no deadlock if, no matter how long we look at the queue, at least as many people are waiting with 100 forints as with 200 forints.

Let's denote the former by $s$ and the latter by $k$, and calculate how many permutations of four $s$ and four $k$ letters do not result in a deadlock. In a good order, the first person must pay with a 100 forint note, and the last with a 200 forint note, so any good order is of the form $s$ $k$.

Let's group the good orders according to the position of the first viewer who wants to pay with 200 forints. If this is $K$, then $2 \leq K \leq 5$.

(i) $K=5$. There is only one such order: $s$ s $s k k k k$, and this is clearly good.

(ii) $K=4: s s k{ }^{k} \ldots \ldots \ldots$. By writing the fourth $s$ letter in any of the three possible positions, we get a good order, so in this case, we get 3 good orders.

(iii) $K=3: s s k-— — — k$. The remaining two $s$ letters can be written in $\binom{4}{2}=6$ ways into two of the four free positions. Out of these 6 orders, only 1 is not good, the one where the two $s$ letters are in the last two free positions. In this case, we get 5 good orders.

(iv) $K=2: s k$ $\qquad$ $k$. The third position can only be filled with an $s$ letter, otherwise, the queue would get stuck: $s k s$ $k$. This essentially leads us to the previous case, and we get another 5 good orders.

Having examined all possibilities, we have found 14 good orders. Since we can choose the four positions for the $s$ letters out of 8 in $\binom{8}{4}=70$ ways, the cashier can issue the tickets without deadlock in $\frac{14}{70}=\frac{1}{5}$ of all orders.

II. solution. Using the notation from the previous solution, we now count the "bad" orders. A deadlock occurs when an equal number of $s$ and $k$ letters appear before the deadlock, and a $k$ letter stands at the deadlock position. The deadlock itself thus occurred at the $(2 m+1)$-th position $(m=1,2,3,4)$.

Now let's modify such sequences as follows: if the deadlock occurs at the $(2 m+1)$-th position, then we swap the $s$ letters for $k$ letters and the $k$ letters for $s$ letters in the first $(2 m+1)$ positions. We do not change the letters in the positions after the deadlock.

$$
s s k k k\left|\_\rightarrow \quad k k s s s\right|
$$

$\qquad$
This way, we get a sequence consisting of 5 $s$ and 3 $k$ letters. Conversely, if we consider a $(5 s, 3 k)$ sequence, we can uniquely obtain a bad sequence from it: since there are more $s$ than $k$, there will be a first position where the $s$ letters outnumber the $k$ letters, and this will occur at some odd position. Swapping $s \leftrightarrow k$ up to this position, we get a bad sequence.

The number of bad sequences is thus $\binom{8}{3}=56$, and the number of good sequences is $\binom{8}{4}-56=14$.

Based on the work of Csötönyi Nóra (Bonyhád, Petőfi S. Gimn., 10. o.t.)

Remarks. 1. The above counting can also be given a geometric interpretation: each sequence can be represented by a broken line starting from the origin: for an $s$ letter, we step forward by the $\mathbf{f}(1,1)$ vector, and for a $k$ letter, by the $\mathbf{l}(1,-1)$ vector.

Thus, we get broken lines starting from the origin and ending at the $(8 ; 0)$ point. A path is bad if it touches or crosses the $y=-1$ line. For the "bad" broken lines, perform the $\mathbf{f} \leftrightarrow \mathbf{l}$ swap up to the first intersection point with the $y=-1$ line, and we get a path starting from the origin and ending at the $(8,2)$ point. There are $\binom{8}{3}$ such paths.

2. Another, more intuitive way to execute the above "reflection" and the corresponding counting is as follows:

Reflect the part of a bad path $(0,0) \rightarrow(8 ; 0)$ after its first intersection with the $y=-1$ line over the $y=-1$ line. This way, we get a path starting from $(0,0)$ and ending at $(8,-2)$, consisting of $(3 s, 5 k)$. Conversely, any such path clearly intersects the $y=-1$ line; reflecting the part of the path after the first intersection point, we get a bad sequence.

Thus, the number of bad sequences is $\binom{8}{3}$.

3. By any of the above methods, we find that if $2 n$ customers are waiting in front of the cashier, with half of them having 100 forints and the other half 200 forints, then the total number of orders is $\binom{2 n}{n}$, and the number of bad ones is $\binom{2 n}{n-1}$.

In this case, the cashier can issue the tickets without deadlock in $\frac{\binom{2 n}{n}-\binom{2 n}{n-1}}{\binom{2 n}{n}}=\frac{1}{n+1}$ of all orders.

Using the reflection method, we can also get an answer to the question of the problem if the number of people waiting with 100 forints and 200 forints is different. If $n$ viewers are waiting with 100 forints and $m$ with 200 forints ($n \geq m$), then we similarly find (Fig. 3) that the number of bad orders is $\binom{n+m}{m-1}$.
![](https://cdn.mathpix.com/cropped/2024_05_02_69853f92c6134195fcb5g-2.jpg?height=952&width=1216&top_left_y=126&top_left_x=454)