Results 1 to 2 of 2

Math Help - a combinatorial problem

  1. #1
    Newbie
    Joined
    Jan 2011
    Posts
    24

    a combinatorial problem

    Ok, so we've got twelve balls all marked with a distict number between 1 and 12.
    ( 1 ) ( 2 ) ( 3 ) ( 4 ) ( 5 ) ( 6 ) ( 7 ) ( 8 ) ( 9 ) (10) (11) (12)
    In how many ways can we pick three balls from the twelve so that the difference between the numbers written on them is at least 2.

    For example: we are not allowed to pick ( 1 ) ( 2 ) ( 5 ) since 2-1=1, but are allowed to choose ( 1 ) ( 5 ) (12).
    -----------------------------------------------------
    The answer should be 120, but why?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,682
    Thanks
    614

    Re: a combinatorial problem

    Hello, mgarson!

    We have twelve balls each marked with a distict number between 1 and 12.

    In how many ways can we pick three balls from the twelve
    so that the difference between the numbers written on them is at least 2?

    For example: we are not allowed to pick {1, 2, 5} since 2 - 1 = 1,
    . . but are allowed to choose {1, 5, 12}.

    The answer should be 120, but why?

    In desperation, I started a brute-force Listing of the possible triples,
    . . then I discovered a pattern.


    Suppose the smallest number is 1 and the next number is 3.
    . . Then the largest number must be 5 or more: .8 choices.

    Suppose the smallest number is 2 and the next number is 4.
    . . Then the largest number must be 6 or more: .7 choices.

    Suppose the smallest number is 3 and the next number is 5.
    . . Then the largest number must be 7 or more: .6 choices.

    . . . . . . . . \vdots

    Suppose the smallest number is 1 and the next number is 10.
    . . Then the largest number must be 12: .1 choice.

    Hence, when the smallest number is 1,
    . . there are: . 1 + 2 + 3 + \hdots + 8 \:=\:36 ways.



    When the smallest number is 2, we find that the number of triples is:
    . 1 + 2 + 3 + \hdots + 7 \:=\:28 ways.

    When the smallest number is 3, we find the number of triples is:
    . . 1 + 2 + 3 + \hdots + 6 \:=\:21 ways.

    And so on . . .



    We see that the total number of ways
    . . is the sum of the first 8 Triangular Numbers.

    This is a Tetrahedral Number: . T(n) \:=\:\frac{n(n+1)(n+2)}{6}

    Therefore: . T(8) \:=\:\frac{8\cdot9\cdot10}{6} \:=\:120

    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Combinatorial problem
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: October 4th 2011, 09:05 AM
  2. Combinatorial Problem
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: August 8th 2010, 01:20 PM
  3. combinatorial problem
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: April 18th 2010, 12:22 PM
  4. combinatorial problem??
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: September 23rd 2009, 10:29 PM
  5. Combinatorial problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 19th 2008, 06:19 PM

Search Tags


/mathhelpforum @mathhelpforum