Results 1 to 6 of 6

Math Help - Combinations brain twister

  1. #1
    Newbie
    Joined
    Mar 2009
    Posts
    4

    Combinations brain twister

    This problem drives me crazy. The legend says is a 5th grade problem. I doubt.

    - 10 marbles (0 to 9)
    - 3 bowls.
    - Each bowl can hold 3 non-consecutive marbles.
    How many different combinations?

    I have managed to solve it using a computer and brute force. I have solved an easier variant (5/2/2) without the help of a computer.


    Thank you.

    P.S. I have finished the school a long time ago, be gentle.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,901
    Thanks
    1756
    Awards
    1
    We need some clarifications.
    Are the bowls identical or are they distinct?
    You are putting nine balls into three bowls, three balls per bowl. Is that correct?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Mar 2009
    Posts
    4
    I hope this example will make things clearer:

    Valid combination: 023 145 769. The order of bowls does not count, i.e. 145 769 023 is the same. Also the order of marbles in a bowl does not count, i.e. 451 976 203 is the same.

    Invalid combination: 201 845 367. The marbles in first bowl are successive.

    Invalid combination: 023 045 769. 0 is repeated.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,901
    Thanks
    1756
    Awards
    1
    Let's be clear: \boxed{023}\;,\;\boxed{486}\;,\;\boxed{975} would be valid.
    Note that 23 in the bowl.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Mar 2009
    Posts
    4
    Yes, 023 is valid. 123 or 231 is not valid.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Mar 2009
    Posts
    4

    Solution?

    The count of successive-marbles combinations is:
    S( R, M ) = R – M + 1
    where
    R is the total number of marbles;
    M is the number of marbles a bowl is holding.
    In our case S( 10, 3 ) = 8.

    Let B be the number of bowls.




    Method 1. Remove the successive-marbles combinations from start.
    1. The count of M marbles combinations is: U = C( R, M ) (120, in our case)
    2. The count of M marbles combinations, except for the successive-marbles combinations is V = C( R, M ) – S( R, M ) (112, in our case)
    3. The count of B bowls combinations (bowls containing only non-successive marbles) is W = C( V, B ) (227920, in our case).
    4. From W set we now have to remove the combinations that contain the same marble more than once. That is a dead end; for me, at least.
    Method 2. Remove the identical marble combinations right from the start.
    1. The count of non-identical-marble combinations is the first bowl is C( R, M ); the number of combinations of the remaining R – M marbles is C( R – M, M ); and so on until we fill all B bowls. The total number of combinations is C( R, M ) * C( R – M, M ) * … Since the bowls may change places we have to divide it by B!. That is: Q = C( R, M ) * C( R – M, M ) * … / B! (2800 in our case).
    2. Now remove the successive combinations. Someone I know managed to compute this number for our case (504), but did not manage to come up (yet) with a general equation.

    a. First put 012 in the first bowl. Following the same reasoning at 1. we find 70 combinations.
    b. Same for 123: 70 combinations; 012 cannot be among those combinations.
    c. Same for 234: 70 combinations; 012 and 234 cannot be among those combinations.
    d. 345: 66 combinations; the total number of 345 combinations is 70 but 012 occurs 4 times, so we have to subtract 4.
    e. Follow the same reasoning at d. until we reach the 789 combination.
    f. 70 + 70 + 70 + 66 + 62 + 58 + 55 + 53 = 504
    g. ANSWER = 2800 – 504 = 2296, that is the same answer I got using brute force.
    Comments are welcome.
    Last edited by gaga; March 18th 2009 at 02:21 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Brain Teasers
    Posted in the Calculus Forum
    Replies: 3
    Last Post: December 1st 2008, 09:54 AM
  2. Brain Thinkers
    Posted in the Algebra Forum
    Replies: 2
    Last Post: November 25th 2008, 09:00 AM
  3. Brain Teaser
    Posted in the Algebra Forum
    Replies: 5
    Last Post: May 7th 2007, 11:01 AM
  4. Brain freeze
    Posted in the Algebra Forum
    Replies: 2
    Last Post: March 17th 2007, 12:19 AM
  5. problem solving-brain twister
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: March 3rd 2007, 05:44 PM

Search Tags


/mathhelpforum @mathhelpforum