There are $2 \cdot n$ people in the queue to the theater office; n people on only banknotes worth $20$ zlotys, and the remaining n people only have banknotes worth $10$ zlotys . At the beginning of the sale at the box office there is no money. Each person buys one ticket worth 10 zlotys.

If one with only $20$-zlotys banknotes is in the first of the queue, then he/she needs to wait for another guy with only 10-zlotys banknote to complete his/her transaction, because the ticket office does not have any change to offer at that time.

What is the probability that no one will wait for the change?

$A$ = no one will wait for the rest. $P (A) = 1-P (A ')$, that is, it subtracts the waiting persons from the whole and will leave me without waiting, but I do not know how to calculate it.

  • $\begingroup$ I don't understand the question $\endgroup$ – Zubin Mukerjee Mar 13 at 20:25
  • $\begingroup$ What is PLN 10? Has it to do with Zlotys? Then it should be PLZ 10 perhaps...What is $A'$. And why is no one waiting for the rest of the people? $\endgroup$ – Dietrich Burde Mar 13 at 20:28
  • 1
    $\begingroup$ The question still makes no sense even if zloty ambiguities are resolved $\endgroup$ – Zubin Mukerjee Mar 13 at 20:39
  • 1
    $\begingroup$ @JaroslawMatlak Thank you, this is interesting! $\endgroup$ – Dietrich Burde Mar 13 at 20:40
  • 1
    $\begingroup$ @ZubinMukerjee, hopefully my edit makes it clear $\endgroup$ – MoonKnight Mar 13 at 21:08

Not a full answer but a hint and not so elegant. The elegant approach would count random walks with increments $(1,\pm 1)/\sqrt{2}$ staying at or above a line of slope $-1/2.$

You are asking for the number $K_n$ of $$x=(x_1, \ldots, x_{2n})\in \{2,-1\}^{2n}$$ divided by $$\binom{2n}{n}$$ to make it a probability, with exactly $n$ $x_i$ equal to $2$ such that the partial sums $$ S(x,t)=\sum_{k=1}^t x_t,\quad t=1,\ldots,2n, $$ are all nonnegative. A recursive approach starting with $n=1,$ obviously works but there may be a nice closed form.

I won't do the division. When $n=1,$ $(2,-1)$ is fine but $(-1,2)$ is not so $K_1=1.$

As far as the recursion if a $2n$ pattern fails all its extensions fail. Since the non failing pattern for $n=1,$ has sum $1$ both of its extensions will pass, thus $K_2=2,$ with sums $0$ or $3$. The next step is similar and note that if a sum is $1$ or more it is safe for the next iteration, it cant go negative.


The number of ten-zloty notes in the cash box goes up by one when a customer with a ten-zloty note comes to the window, and it goes down by one when a customer with a twenty-zloty note comes to the window, so this is a question about Catalan numbers and Dyck paths. If you Google either of those terms, you'll get lots of hits, and you'll see how to solve the problem.

If I recall the formula correctly for the catalan numbers correctly,, the answer is $${1\over n+1}$$


Define $P(a,b)$ as the probability of reaching the end with no one waiting when there are still $a$ people with 10-zlotyes and $b$ people with 20-zlotyes left. So the answer to your problem is $P(n,n)$ in this notation.

Obviously we have

  • $P(a,0) = 1$
  • $P(a,b) = 0 \quad(\text{when } a<b)$

And the recurrence relation $$ P(a,b) = \frac{a}{a+b}P(a-1, b) + \frac{b}{a+b}P(a, b-1) $$

You can manually calculate a few layers $P(a,1)$, $P(a,2)$ etc. It won't be long before you start to find there is an simple expression for it $$ P(a,b) = 1 - \frac{b}{a+1} \quad (\text{when } a\geq b) $$

Now let me prove this is the correct expression.

  1. Obviously it is true for $b=0$.
  2. Even though we are only interested in the cases when $a\geq b$, but it can be easily verified that the expression above also holds for $b=a+1$ ($P(a,a+1)=0$). So when we are calculating $P(a,a)$, we can still use the expression above to represent $P(a-1,a)$.
  3. Now the main step $$ P(a,b) = \frac{a\frac{a-b}{a-1+1} + b \frac{a+2-b}{a+1}}{a+b} = 1 + \frac{-2b(a+1) + b(a+2-b)}{(a+1)(a+b)} = 1 - \frac{b}{a+1} $$

Now, it is easy to see from this general expression that $$ P(n,n) = \frac{1}{n+1} $$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.