Combinatorial Problem From Book

Find all the number of ways such that three elements selected from the set $\{ 1,2,3,....,4n\}$ sum of whose is divisible by $4$.

I cannot find the solution of this equation $x + y + z = 4k$. Solving this equation we can get our answer.

• Are you familiar with compositions (in the combinatorics sense)? – Pavelshu May 3 '14 at 3:03
• give me a eg. of composition den I can tell..@ pavelshu – soumajit das May 3 '14 at 3:05
• en.wikipedia.org/wiki/Composition_(combinatorics) – Pavelshu May 3 '14 at 3:06
• yaa...I know all these...this was the thing i wrote in my post....see...x + y + z = 4k.. @ Pavelshu – soumajit das May 3 '14 at 3:09
• @soumajit das should we not know whether there is replacement or not? – bobbym May 3 '14 at 10:10

We can do the job by considering various cases. There are various ways in which the sum can be divisible by $4$.

Case (i): The $3$ chosen numbers are all congruent modulo $4$ (have the same remainder on division by $4$). Then they must all be congruent to $0$ (have remainder $0$). Since $n$ of our numbers are divisible by $4$, there are $\binom{n}{3}$ possibilities. Note that if $n\lt 3$ then $\binom{n}{3}=0$.

Case (ii): We choose $2$ numbers congruent to $1$ modulo $4$, and $1$ congruent to $2$. That gives $\binom{n}{2}\binom{n}{1}$ ways.

Case (iii): We choose $2$ numbers congruent to $3$, and $1$ congruent to $2$. We get the same number of ways as in (ii).

Case (iv): We choose $2$ numbers congruent to $2$, and $1$ congruent to $0$. Again, we get the same number as in (ii).

Case (v): all the chosen numbers are incongruent modulo $4$. Then $1$ number is congruent to $1$, another to $3$, and another to $4$. That gives $\binom{n}{1}\binom{n}{1}\binom{n}{1}$ possibilities.