Results 1 to 13 of 13
Like Tree1Thanks
  • 1 Post By Plato

Thread: Line 'em up!

  1. #1
    MHF Contributor
    Joined
    Feb 2015
    From
    Ottawa Ontario
    Posts
    1,957
    Thanks
    361

    Line 'em up!

    There are 34 people in line to get into a theater. Admission cost is 5 dollars.
    Of the 34 people, 28 have only a 5 dollar bill and 6 have only a 10 dollar bill.
    To complicate matters, the ticket office has an empty cash register.
    In how many ways can the people line up so that change is available when needed?

    Example with 4 people, 2 (a and b) with 5's and 2 (c and d) with 10's:
    a b c d
    a b d c
    b a c d
    b a d c
    a c b d
    a d b c
    b c a d
    b d a c
    So 8 ways...
    Last edited by DenisB; Jun 7th 2018 at 01:44 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,686
    Thanks
    1495

    Re: Line 'em up!

    You only need to look at the first 11 positions. There are 34! arrangements without restriction.
    There are $6\times 33!$ arrangements that fail because the first person has only a 10.
    There are $28\times 6\times 5 \times 31!$ ways that the first person has a 5 and the second and third both have 10s.
    Next we want 5,10,5,10,10,anything (because any other arrangement that fails in the first 5 people was already counted above)
    $28\times 6\times 27 \times 5 \times 4 \times 29!$
    We see the pattern:
    $$\displaystyle 34!- \sum_{n=1}^6\dfrac{28!}{(29-n)!}\cdot \dfrac{6!}{(6-n)!}\cdot (35-2n)!$$

    The chances that if people line up randomly, there will be enough change for everyone is $\dfrac{4621}{5797} \approx 80\%$.
    Last edited by SlipEternal; Jun 8th 2018 at 09:26 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Feb 2015
    From
    Ottawa Ontario
    Posts
    1,957
    Thanks
    361

    Re: Line 'em up!

    Thanks Slip. And that's basically the same as:
    u = 28
    v = 6
    a = ? (arrangements)

    a = (u + v)! * [(u + 1 - v)/(u + 1)]
    = 234 150 150 962 444 663 430 869 931 786 240 000 000

    which is the exact number of ways the people can line up...right?

    Btw, a / 34! = ~.7931 (close to 80% as you're showing).

    Question:
    what if the 28 fivers are undistinguishable, so are the 6 teners?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,686
    Thanks
    1495

    Re: Line 'em up!

    Quote Originally Posted by DenisB View Post
    Question:
    what if the 28 fivers are undistinguishable, so are the 6 teners?
    $\dbinom{34}{6}-\dbinom{33}{5}-\dbinom{31}{4}-\dbinom{29}{3}-\dbinom{27}{2}-\dbinom{25}{1}-\dbinom{23}{0} = 1,072,072$
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,686
    Thanks
    1495

    Re: Line 'em up!

    Quote Originally Posted by DenisB View Post
    Thanks Slip. And that's basically the same as:
    u = 28
    v = 6
    a = ? (arrangements)

    a = (u + v)! * [(u + 1 - v)/(u + 1)]
    = 234 150 150 962 444 663 430 869 931 786 240 000 000

    which is the exact number of ways the people can line up...right?

    Btw, a / 34! = ~.7931 (close to 80% as you're showing).
    One of us is using the wrong formula. Consider when the breakdown is 17 to 17. Then, my formula gives:

    $$\displaystyle 34!-\sum_{n=1}^{17}\dfrac{17!}{(18-n)!}\cdot \dfrac{17!}{(17-n)!}(35-2n)! \approx \dfrac{34!}{3}$$

    while your formula gives $\dfrac{34!}{18}$.
    Last edited by SlipEternal; Jun 8th 2018 at 11:55 AM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Feb 2015
    From
    Ottawa Ontario
    Posts
    1,957
    Thanks
    361

    Re: Line 'em up!

    Whoops...forgot to include u>v
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,686
    Thanks
    1495

    Re: Line 'em up!

    u=18,v=16 with my method gets around $.36*34!$ but your method gets $34!(3/19) $ which is less than half of what I get. How did you come up with the $34!(u+1-v)/(u+1)$?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Feb 2015
    From
    Ottawa Ontario
    Posts
    1,957
    Thanks
    361

    Re: Line 'em up!

    Take it easy on me Slip, I'm just an old guy trying to learn!

    I came up with that from here (similar old problem):
    https://en.wikipedia.org/wiki/Bertra...ballot_theorem

    And now I'm at the stage where solution is:
    34*33*32*31*30*29/6! * 23/29 = 1066648 instead of your 1072072

    Soooo...enlighten me!
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Joined
    Feb 2015
    From
    Ottawa Ontario
    Posts
    1,957
    Thanks
    361

    Re: Line 'em up!

    Well, I'm now pretty well convinced answer is 1,066,648.

    And this is formula:
    a = (u+v)C(u) * (u+1-v)/(u+1) = 34C28 * 23/29 = 1344904*23/29 = 1066648
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,686
    Thanks
    1495

    Re: Line 'em up!

    Quote Originally Posted by DenisB View Post
    Take it easy on me Slip, I'm just an old guy trying to learn!

    I came up with that from here (similar old problem):
    https://en.wikipedia.org/wiki/Bertra...ballot_theorem

    And now I'm at the stage where solution is:
    34*33*32*31*30*29/6! * 23/29 = 1066648 instead of your 1072072

    Soooo...enlighten me!
    I did not say I was right and you were wrong. I said one of us was using the wrong formula, and I did not understand where yours came from. Nor do I understand why my formula is not correct. I must be overcounting somehow.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor
    Joined
    Feb 2015
    From
    Ottawa Ontario
    Posts
    1,957
    Thanks
    361

    Re: Line 'em up!

    Let's make it a lineup of 10 this way: u = fivers = 7 and v = teners = 3
    Let u be represented with 1's and v with 2's:
    then total lineups = 120, from 1 1 1 1 1 1 1 2 2 2 to 2 2 2 1 1 1 1 1 1 1
    (p = position)
    1: eliminate cases where p1 = 2 : that's 36 cases; left = 120-36 = 84
    2: eliminate cases where p2=p3=2: that's 7 cases; left = 84 - 7 = 77
    3: eliminate cases where p3=p4=p5=2: that's 1 case; left = 77 - 1 = 76
    4: eliminate cases where p2=p3=p5=2: that's 1 case; left = 76 - 1 = 75 ***

    *** perhaps you missed this case?

    My formula will give 75.
    Not sure what yours will give; probably 76?
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor

    Joined
    Aug 2006
    Posts
    22,042
    Thanks
    2957
    Awards
    1

    Re: Line 'em up!

    Quote Originally Posted by DenisB View Post
    Let's make it a lineup of 10 this way: u = fivers = 7 and v = teners = 3
    Let u be represented with 1's and v with 2's:
    then total lineups = 120, from 1 1 1 1 1 1 1 2 2 2 to 2 2 2 1 1 1 1 1 1 1
    My formula will give 75.
    This form is a much more workable problem than the original
    Arranging the string $FFFFFFFTTT$ in $\dbinom{10}{3}=120$ ways.
    I agree with your answer of $75$. But I counted dircctly, no elimations.
    Here are the possible strings to count:
    1) $FFF~\_~\_~\_~\_~\_~\_~\_$ i.e. beginning with three fives.
    2) $FTFF~\_~\_~\_~\_~\_$ i.e. beginning with three fives & one T.
    3) $FFTF~\_~\_~\_~\_~\_$ i.e. beginning with three fives & one T.
    4) $FTFTF~\_~\_~\_~\_~\_$ i.e. beginning with three fives & two T.
    5) $FFTTF~\_~\_~\_~\_~\_$ i.e. beginning with three fives & two T.

    For #1, there are $\dbinom{7}{3}=35$ acceptable such strings. SEE HERE

    For each of 2) & 3) there are $\dbinom{6}{2}=15$ acceptable such strings.

    For each of 4) & 5) there are $\dbinom{5}{1}=5$ acceptable such strings.

    That adds to $75$.
    Thanks from DenisB
    Follow Math Help Forum on Facebook and Google+

  13. #13
    MHF Contributor
    Joined
    Feb 2015
    From
    Ottawa Ontario
    Posts
    1,957
    Thanks
    361

    Re: Line 'em up!

    Quite clear and elegant; merci Plato.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 5
    Last Post: Sep 1st 2012, 04:15 PM
  2. Replies: 1
    Last Post: Aug 30th 2012, 12:56 PM
  3. Replies: 3
    Last Post: May 23rd 2012, 05:39 PM
  4. Replies: 3
    Last Post: Nov 4th 2011, 06:42 PM
  5. Replies: 0
    Last Post: Oct 22nd 2009, 11:04 AM

/mathhelpforum @mathhelpforum