Another counting problem: There are 34 people in line to get into a theater....

Jomo

Elite Member
Joined
Dec 30, 2014
Messages
3,281
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.
 

Jomo

Elite Member
Joined
Dec 30, 2014
Messages
3,281
1 2 3 ............. 27 28 29 30 31 32 33 34
Is this the same as:
2 1 3 ............. 27 28 29 30 31 32 33 34 ?
1 2 3 ............. 27 28 29 30 31 32 33 34
Is NOT the same as:
2 1 3 ............. 27 28 29 30 31 32 33 34 ?
 

JeffM

Elite Member
Joined
Sep 14, 2012
Messages
3,258
Jomo

i do not have time to think this through all the way, but I suspect that you may need only to think about the first 12 in line. Once 6 of the 50-cent people have paid, there will always be enough in the cash box. Given that there are only 6 of the one-dollar, after 12 people you necessarily will have had at least 6 50-cent people.

If you pick the first 6 from 50-centers, then any order after the first six is fine. So

\(\displaystyle \dfrac{28!}{6!} * 28!.\)

If you pick 6 of the first 7 from 50-centers, then any order after the first seven is fine, but we must exclude from that those cases with the very first customer coming from from the one-dollar group. So

\(\displaystyle 28 * \left ( \dfrac{6!}{5} * \dfrac{27!}{5!} * 6 \right ) * 27!.\)

To explain, there are 28 ways to choose the first customer. For the next six customers, there are 6 ways to choose from the one-dollar customers and 27!/5! ways to order five of the remaining 50-cent customers and 6 places to slot the one-dollar customer. That takes care of the first seven, and (34 - 7)! ways to order the rest.

If you pick 6 of the first 8 from 50-centers, then any order after the first 8 is fine, but we cannot start dollar, dollar, or dollar, 50, or 50, dollar, dollar. So

\(\displaystyle \left \{ \left ( \dfrac{6!}{4!} * \dfrac{28!}{6!} \right ) * \left ( \dbinom{8}{2} - 3 \right ) \right \} * 26!.\)

And so on.

Edited.

Further edit: I am beginning to suspect that there may be a formula.

If the first six are 50-centers we have

\(\displaystyle \left \{ \dfrac{6!}{(6 - 0)!} * \dfrac{28!}{6!} * \left ( \dbinom{6}{6} - 0 \right ) \right \} * (34 - 6)!.\)

If the first seven include only one dollar-biller, we have to exclude the the dollar biller coming before any 50-center

\(\displaystyle \left \{ \dfrac{6!}{(6 - 1)!} * \dfrac{28!}{6!} * \left ( \dbinom{7}{1} - 1 \right ) \right \} * (34 - 7)!.\)

If the first eight include exactly two dollar-billers, we have to exclude those two being among the first three.

\(\displaystyle \left \{ \dfrac{6!}{(6-2)!} * \dfrac{28!}{6!} * \left ( \dbinom{8}{2} - \dbinom{3}{2} \right ) \right \} * (34 - 8)!.\)
 
Last edited:

Jomo

Elite Member
Joined
Dec 30, 2014
Messages
3,281
1 2 3 ............. 27 28 29 30 31 32 33 34
Is NOT the same as:
2 1 3 ............. 27 28 29 30 31 32 33 34
Earlier today I got some big numbers just having the 28 coin payers up front and the 6 $1 bill payers in the view of the line. I am sorry but I was wrong and in fact the 28 (and 6) theaters goers are indistinguishable.

So 1 2 3 ............. 27 28 29 30 31 32 33 34
IS the same as:
2 1 3 ............. 27 28 29 30 31 32 33 34
 

JeffM

Elite Member
Joined
Sep 14, 2012
Messages
3,258
I was fairly confident that I had the correct answer, but I was wrong.
 
Last edited:

JeffM

Elite Member
Joined
Sep 14, 2012
Messages
3,258
No need for an explanation of a wrong answer.
 
Last edited:

JeffM

Elite Member
Joined
Sep 14, 2012
Messages
3,258
You don't think mine is correct?
Mon vieux, I have no idea whether your formula is correct or not. You have given no explanation for it, and I am still wandering in the wilderness.
 

JeffM

Elite Member
Joined
Sep 14, 2012
Messages
3,258
OK. I am going to work through this over multiple threads in the hope that if I make an error, someone will come to the rescue.

We have 6 people in class D and 28 people in class F. The number of distinct orderings of these

people is obviously \(\displaystyle 34!\).

We consider an ordering good if the first occurrence of a D is preceded by at least one F, the second occurrence of a D is preceded by at least two F's, etc. An ordering that is not good is considered bad.

Let a = the number of D's in the first 11 positions Therefore the number of F's in the first 11 positions is 11 - a.

Class I: a = 6. All orderings in this class are bad. The number in this class is

\(\displaystyle \alpha = \left \{ \dbinom{6}{6} * \dbinom{28}{11 - 6} * 11! \right \} * 23! = 23! * \dfrac{28!}{5! * 23!} = \dfrac{28!}{5!}.\)

Let b = the number of D's in the first 9 positions. Therefore the number of F's in the first 9 positions 9 - b.

Cases such that a = 6 and b \(\displaystyle \ge\) 5 are included in Class I. But cases such that a = 5 = b are not.

Class II: a = 5 = b. All orderings in this class are bad. The number in this class is

\(\displaystyle \beta = \left \{ \dbinom{6}{5} * \dbinom{28}{9 - 5} * 9! \right \} * \left \{ \dbinom{6 - 5}{0} * \dbinom{28 - (9 - 5)}{11 - 9} * 2! \right \} * 23! =\)

\(\displaystyle \left \{ 6 * \dbinom{28}{4} * 9! \right \} * \left \{ \dbinom{24}{2} * 2! \right \} * 23! = 6 * \dfrac{28!}{4! * 24!} * 9! * \dfrac{24!}{2! * 22!} * 2! * 23! =\)

\(\displaystyle 30 * 23 * 9! * \dfrac{28!}{5!}\).

To be continued. Please call out any idiocies.
 

Jomo

Elite Member
Joined
Dec 30, 2014
Messages
3,281
"sorry" won't cut it: to the corner!!
You caused me to lose sleep, and Jeff to see his shrink:(

OK. The given answer of 1,066,648 is correct.

u = 28
v = 6
a = arrangement = ?

Simple formula: a = (u+v)C(u) * (u+1-v)/(u+1) where u>v

34C28 * 23/29 = 1344904 * 23/29 = 1066648
It is a still a valid problem either way.
 
Top