No Change At The Movies
Ten students want to buy a ticket for a movie. The ticket costs $10. Five of them have a $10 note, and the other five have a $20 note. They all line up in a random order, and each uses their note to buy the ticket. Of course, those with $20 expect a change, and unfortunately, you don't have any money to start with. You can use the $10 you receive to make a change for the $20, though. What is the probability that everyone will receive their ticket and change as desired?
Your answer can be represented as where are non-negative integers that are relatively coprime. Enter your answer as .
The answer is 7.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
Moderator note:
Good recognition of the relation to Catalan numbers.
The answer is 6 1 .
Note that we are successful if and only if at any time, the number of students with $10 that have had their ticket is not less than the number of students with $20 that have had their ticket. (Every $20 student expects a $10 change; if there are more $20 students, you don't have enough $10 notes to cover them all.)
Imagine that we start on ( 0 , 0 ) on a lattice grid. Every time we have a student with $10, we move one step right, and every time we have a student with $20, we move one step up. Clearly we will finish on ( 5 , 5 ) , since we make five right steps and five up steps. The condition that there are at least as many $10's as $20's is equivalent to that we never go above the line y = x . Now, this problem is a popular one: Catalan number . Out of the ( 5 1 0 ) ways to reach ( 5 , 5 ) , there are 6 1 ( 5 1 0 ) ways that don't go above the line, so that's a probability of 6 1 .