Steven G
Elite Member
- Joined
- Dec 30, 2014
- Messages
- 14,362
There are 34 people in line to get into a theater. Admission costs 50 cents. Of the 34 people, 28 of them have a 50-cent piece and 6 have a $1 bill. Suppose that the box office has an empty cash register, how many ways can the people line up so that change is available when needed?
Here is what I see. The first person must pay 50 cents. After this 1st person all we need is NOT to have at any point the number of bill payers exceed the number of coin payers.
I put this on a x-y coordinate system. I think that I should start at (1,0) and go to (28,6) without crossing y=x (touching is ok)
Now you can go through (6,0) (and then go to the right) and proceed to (28,6). You can do this in (5C5)*(27C21)ways
Or you can go through (6,1) (and then go to the right) and proceed to (28,6). You can do this in (6C5)*(26C21) ways
Or you can go through (6,2) (and then go to the right) and proceed to (28,6). You can do this in (7C5)*(25C21) ways
Or you can go through (6,3) (and then go to the right) and proceed to (28,6). You can do this in (8C5)*(24C21) ways
Or you can go through (6,4) (and then go to the right) and proceed to (28,6). You can do this in (9C5)*(23C21) ways
Or you can go through (6,5) (and then go to the right) and proceed to (28,6). You can do this in (10C5)*(22C21) ways
Or you can go through (6,6) (and then go to the right) and proceed to (28,6). You can do this in (11C5)*(21C21) ways
I added these all up and got
The problem is that the result is 1066648. I am sure that there are more efficient ways to do this problem. I would be thrilled if you can show me some of them. I also want to know where I over counted.
Here is what I see. The first person must pay 50 cents. After this 1st person all we need is NOT to have at any point the number of bill payers exceed the number of coin payers.
I put this on a x-y coordinate system. I think that I should start at (1,0) and go to (28,6) without crossing y=x (touching is ok)
Now you can go through (6,0) (and then go to the right) and proceed to (28,6). You can do this in (5C5)*(27C21)ways
Or you can go through (6,1) (and then go to the right) and proceed to (28,6). You can do this in (6C5)*(26C21) ways
Or you can go through (6,2) (and then go to the right) and proceed to (28,6). You can do this in (7C5)*(25C21) ways
Or you can go through (6,3) (and then go to the right) and proceed to (28,6). You can do this in (8C5)*(24C21) ways
Or you can go through (6,4) (and then go to the right) and proceed to (28,6). You can do this in (9C5)*(23C21) ways
Or you can go through (6,5) (and then go to the right) and proceed to (28,6). You can do this in (10C5)*(22C21) ways
Or you can go through (6,6) (and then go to the right) and proceed to (28,6). You can do this in (11C5)*(21C21) ways
I added these all up and got
The problem is that the result is 1066648. I am sure that there are more efficient ways to do this problem. I would be thrilled if you can show me some of them. I also want to know where I over counted.