# Thread: TA’s Challenge Problem #6

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.

2. Originally Posted by TheAbstractionist
(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.

3. 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.$

4. 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.

5. Yup, you got it this time.