1
$\begingroup$

Find the number of ways in which three numbers can be selected from the set $\{1,2,\dots,4n\}$ such that the sum of the three selected numbers is divisible by 4.

My approach: If $n=1$ then the set is $\{1,2,3,4\}$ and only one valid combination exists, $\{1,3,4\}$. But in general how can I find the solution? Please help.

$\endgroup$
4
$\begingroup$

If three natural numbers add to a multiple of four, there are five possibilities for the individual numbers' residues modulo 4 up to ordering: $$000, 112, 220, 332, 013$$ Within $\{1,2,\dots,4n\}$ each residue modulo 4 occurs $n$ times. The number of valid selections for the $000$ case (i.e. each number in the selection is $\equiv0\bmod4$) is $\binom n3$, that for each of the $112/220/332$ cases $n\binom n2$ and that for the $013$ case $n^3$, so the total number of ways is $$\binom n3+3n\binom n2+n^3=\frac{8n^3-6n^2+n}3$$

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