TA’s Challenge Problem #6

• Aug 1st 2009, 05:07 PM
TheAbstractionist
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.
• Aug 1st 2009, 06:59 PM
pankaj
Quote:

Originally Posted by TheAbstractionist
(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.
• Aug 2nd 2009, 06:11 AM
TheAbstractionist
NIce work, pankaj. Your formula for $C(n)$ is spot on, (Nod) but your formula for $D(n)$ is incorrect. $D(n)\ne C(n).$ (Shake)

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.$
• Aug 2nd 2009, 09:07 PM
pankaj
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.
• Aug 3rd 2009, 04:58 PM
TheAbstractionist
Yup, you got it this time. (Clapping)