Results 1 to 5 of 5

Thread: 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 $\displaystyle 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 $\displaystyle C(n)$ denotes the total number of ways of selecting $\displaystyle 3n$ balls from the box, show that $\displaystyle C(n)-1$ is divisible by 6.

    (ii) As previously, but now let $\displaystyle D(n)$ be the total number of ways of selecting $\displaystyle 3n$ balls such that there is at least one ball of each colour. Prove that $\displaystyle 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
    318
    Quote Originally Posted by TheAbstractionist View Post
    (i) A box contains $\displaystyle 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 $\displaystyle C(n)$ denotes the total number of ways of selecting $\displaystyle 3n$ balls from the box, show that $\displaystyle C(n)-1$ is divisible by 6.

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

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

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

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

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

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

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

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

    =$\displaystyle 3n^2+3n+1$

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

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


    But the real challenge would be to explain $\displaystyle 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 $\displaystyle C(n)$ is spot on, but your formula for $\displaystyle D(n)$ is incorrect. $\displaystyle D(n)\ne C(n).$

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


    The formula for $\displaystyle D(n)$ is different. Hint.
    Spoiler:
    Working out for small values of $\displaystyle n,$ we find $\displaystyle D(1)=1,$ $\displaystyle D(2)=10,$ $\displaystyle 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
    318
    O.K..But method remains the same

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

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

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

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

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

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

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

    =$\displaystyle 3n^2-2$

    $\displaystyle 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: Jul 12th 2010, 02:07 PM
  2. TA’s Challenge Problem #7
    Posted in the Math Challenge Problems Forum
    Replies: 5
    Last Post: Aug 7th 2009, 08:39 AM
  3. TA’s Challenge Problem #5
    Posted in the Math Challenge Problems Forum
    Replies: 1
    Last Post: Jul 14th 2009, 06:44 PM
  4. TA’s Challenge Problem #3
    Posted in the Math Challenge Problems Forum
    Replies: 2
    Last Post: Jun 9th 2009, 11:54 PM
  5. TA’s Challenge Problem #2
    Posted in the Math Challenge Problems Forum
    Replies: 7
    Last Post: Jun 9th 2009, 02:35 AM

Search Tags


/mathhelpforum @mathhelpforum