# Combinatorics riddle: Sorting people in a cinema line.

Say i want to go to the cinema. There are two types of movies.

1. Action movie.

2. Drama movie.

Because action is more interesting it costs 50$. And the cost for drama is 10€. There are 200 people which wanna go action movie. 100 of those have 50 dollar bills, And the other 100 people got 100 dollar bill. In addition there are 150 people which wanna buy a ticket for the drama movie, So that 80 have 10€ bill, and the other 70 got 20€ bills. At the start of the day the cinema is empty, In how many ways can you sort the 350 people in a line so that anyone would be able to get an exact change for his money? • Is there a subtle statement in the fact that action movies are paid in US currency and drama movies in European currency? :-) – joriki Apr 20 '13 at 9:34 ## 1 Answer The first queue is exactly equivalent to arranging 100 pairs of brackets in a line: think of anyone with a 50\$ bill as an openning bracket, and with a 100\$- as a closing bracket. You want that at any point the number of opening brackets is not less than the number of the closing ones. This number is called Catalan number, and denoted$C_n$. So, in your case, the asnwer will be $$C_{100}=\frac{1}{100}\binom{200}{100}$$ To the second queue, in the same way, the generalized Catalan number, for 80 openning and 70 closing brackets. That is: $$C_{80,70}=\frac{80-70+1}{80+1}\binom{70+80}{70}$$ Now multiply both numbers. Edit 1: I forgot that we are talking about people. You need to multiply by the permutations between the people, i.e. by$100!\cdot100!\cdot80!\cdot70!$Edit 2: There is just one queue, so, as @joriki mentioned, you need to multiply by$\binom{350}{150}$• You also need to multiply by$\displaystyle\binom{350}{150}$for choosing the spots for the$150$and$200\$ people. – joriki Apr 20 '13 at 9:30
• Oh, I got it wrong - I thought there are two different queues.. – Dennis Gulko Apr 20 '13 at 9:36