2

Question:

22 people go to a movie theater. 11 of them are carrying a 50 dollar bill while the other 11 are carrying a 100 dollar bill. The ticket for the movie theater costs $50. The cashier initially has no money. In how many ways can the 22 people pay for their tickets if the cashier will always change to pay back?

No idea how to even begin the question. Any help?

Gummy bears
  • 3,408
  • 2
    You notice that he can't give back change more than he received change... So one condition is that you can't have more 100$ bill holder before than 50$ bill holders – Martigan Jan 06 '15 at 16:13
  • 1
    @Martigan That I noticed. – Gummy bears Jan 06 '15 at 16:15
  • 1
    The third question on the right side of this page, under Related, is very similar. I remember the problem from other MSE posts. – André Nicolas Jan 06 '15 at 16:17
  • Second hint: there are as much ways of trying to pay with the good conditions than with the wrong ones. – Martigan Jan 06 '15 at 16:19
  • Hmmm..... @Martigan That I didn't know. Let me see how that can help. – Gummy bears Jan 06 '15 at 16:20
  • @Martigan Does that simply mean that there will be a 2 in the denominator; – Gummy bears Jan 06 '15 at 16:22
  • No, since there are ways that do not satisfy either the "more 100$ or more 50$ bill before the other". There are ways that alternate between the two positions (crossing the line so to speak). – Martigan Jan 06 '15 at 16:24
  • no,if at some point in time the cashier has recieved more 100 dollar billers she can't give change, this is because every 100 dollar biller takes a fifty, – Asinomás Jan 06 '15 at 16:24
  • In fact my hints are to point you toward the second proof in the link provided by Zubin Mukerjee below. – Martigan Jan 06 '15 at 16:26
  • @Martigan Yes. That makes sense. As you cannot cross the diagonal, there are as many ways above the diagonal as below. Thus as many ways right as wrong. – Gummy bears Jan 06 '15 at 16:28

1 Answers1

1

This is the eleventh Catalan number: $$C_{11}=\frac{1}{12}\binom{22}{11}=\boxed{58786}$$

Zubin Mukerjee
  • 17,832