TA’s Challenge Problem #6

**TheAbstractionist** · August 1st 2009, 04:07 PM

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

**pankaj** · August 1st 2009, 05:59 PM

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.

**TheAbstractionist** · August 2nd 2009, 05:11 AM

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:

The formula for $D(n)$ is different. Hint.

Spoiler:

**pankaj** · August 2nd 2009, 08:07 PM

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.

**TheAbstractionist** · August 3rd 2009, 03:58 PM

Yup, you got it this time.

Thread: TA’s Challenge Problem #6

LinkBack

Thread Tools

Display

TA’s Challenge Problem #6

Similar Math Help Forum Discussions

Challenge Problem

TA’s Challenge Problem #7

TA’s Challenge Problem #5

TA’s Challenge Problem #3

TA’s Challenge Problem #2

Search Tags