Results 1 to 5 of 5

Math Help - TA’s Challenge Problem #6

  1. #1
    Senior Member TheAbstractionist's Avatar
    Joined
    Apr 2009
    Posts
    328
    Thanks
    1

    TA’s Challenge Problem #6

    (i) A box contains 6n balls of three different colours: red, green, blue. There are an equal number of balls of each colour, and balls of the same colour are identical. If C(n) denotes the total number of ways of selecting 3n balls from the box, show that C(n)-1 is divisible by 6.

    (ii) As previously, but now let D(n) be the total number of ways of selecting 3n balls such that there is at least one ball of each colour. Prove that D(n)+2 is divisible by 3.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member pankaj's Avatar
    Joined
    Jul 2008
    From
    New Delhi(India)
    Posts
    317
    Quote Originally Posted by TheAbstractionist View Post
    (i) A box contains 6n balls of three different colours: red, green, blue. There are an equal number of balls of each colour, and balls of the same colour are identical. If C(n) denotes the total number of ways of selecting 3n balls from the box, show that C(n)-1 is divisible by 6.

    (ii) As previously, but now let D(n) be the total number of ways of selecting 3n balls such that there is at least one ball of each colour. Prove that D(n)+2 is divisible by 3.
    At last there is some problem which I can do.

    Let x_{1},x_{2},x_{3} be the number of red,blue,green balls selected.

    C(n)=Number of solutions to the equation x_{1}+x_{2}+x_{3}=3n,

    =coefficient of x^{3n} in \left(1+x+x^2+x^3+....+x^{2n}\right)^{3}

    =coefficient of x^{3n} in (1-x^{2n+1})^3(1-x)^{-3}

    =coefficient of x^{3n} in (1-3x^{2n+1})(1-x)^{-3}(ignoring higher powers in the expansion)

    =coefficient of x^{3n} in (1-x)^{-3}-3.coefficient of x^{n-1}in (1-x)^{-3}

    = \binom{3n+3-1}{3-1}-3.\binom{n-1+3-1}{3-1}

    = 3n^2+3n+1

    (i) C(n)-1=3n(n+1) which is clearly a multiple of 6.

    (ii) D(n)+2=3(n^2+n+1) which is clearly a multiple of 3.


    But the real challenge would be to explain C(n) by using combinatorial argument.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member TheAbstractionist's Avatar
    Joined
    Apr 2009
    Posts
    328
    Thanks
    1
    NIce work, pankaj. Your formula for C(n) is spot on, but your formula for D(n) is incorrect. D(n)\ne C(n).

    And yes, there is a combinatorial argument to prove that C(n)=3n^2+3n+1. This is my method.
    Spoiler:
    For each k=0,1,\ldots,n-1,n,n+1,\ldots,2n, let there be exactly k red balls in the selection and calculate the total number of combinations of green and blue balls, then sum the totals over k.


    The formula for D(n) is different. Hint.
    Spoiler:
    Working out for small values of n, we find D(1)=1, D(2)=10, D(3)=25.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member pankaj's Avatar
    Joined
    Jul 2008
    From
    New Delhi(India)
    Posts
    317
    O.K..But method remains the same

    Let x_{1},x_{2},x_{3} be the number of red,blue,green balls selected.

    D(n)=Number of positive integral solutions to the equation x_{1}+x_{2}+x_{3}=3n,

    =coefficient of x^{3n} in \left(x+x^2+x^3+....+x^{2n}\right)^{3}

    =coefficient of x^{3n} in x^3\left(1+x+x^2+....+x^{2n-1}\right)^{3}

    =coefficient of x^{3n-3} in (1-x^{2n})^3(1-x)^{-3}

    =coefficient of x^{3n-3} in (1-3x^{2n})(1-x)^{-3}(Ignoring higher powers of x)

    = \binom{3n-3+3-1}{3-1}-3.\binom{n-3+3-1}{3-1}

    = 3n^2-2

    D(n)+2=3n^2 which is clearly a multiple of 3.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member TheAbstractionist's Avatar
    Joined
    Apr 2009
    Posts
    328
    Thanks
    1
    Yup, you got it this time.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Challenge Problem
    Posted in the Math Challenge Problems Forum
    Replies: 2
    Last Post: July 12th 2010, 02:07 PM
  2. TA’s Challenge Problem #7
    Posted in the Math Challenge Problems Forum
    Replies: 5
    Last Post: August 7th 2009, 08:39 AM
  3. TA’s Challenge Problem #5
    Posted in the Math Challenge Problems Forum
    Replies: 1
    Last Post: July 14th 2009, 06:44 PM
  4. TA’s Challenge Problem #3
    Posted in the Math Challenge Problems Forum
    Replies: 2
    Last Post: June 9th 2009, 11:54 PM
  5. TA’s Challenge Problem #2
    Posted in the Math Challenge Problems Forum
    Replies: 7
    Last Post: June 9th 2009, 02:35 AM

Search Tags


/mathhelpforum @mathhelpforum