1
$\begingroup$

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.

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

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.

Finally, add up.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.