3
$\begingroup$

In how many ways can you group $3$ different numbers from $1$ to $12$ wherein their sum is divisible by $3$?

This question is one of the questions asked in a Math contest for intermediate level, particularly for grade 5 pupils. I know the answer but I do not know how it was solved. I also have tried the counting method but have counted 44 combinations only. Also tried elimination but stuck with 164 combinations, don't know what combinations to subtract from $12C3$. The answer to the question is $76$. Help please?

$\endgroup$
4
$\begingroup$

Among our $12$, there are $4$ with remainder $0$ on division by $3$, $4$ with remainder $1$, and $4$ with remainder $2$.

We can get a sum divisible by $3$ if we use "$3$ of a kind" (same remainder) or if we use $1$ of each kind.

There are $3\cdot \binom{4}{3}$ ways to choose $3$ of a kind. And there are $4\cdot 4\cdot 4$ ways to choose $1$ of each kind.

$\endgroup$
4
$\begingroup$

Divide the numbers into $3$ groups by their remainders of division by $3$. $$S_0 = \{ 3,6,9,12\} $$ $$S_1 = \{ 1,4,7,10\} $$ $$S_2 = \{ 2,5,8,11\} $$ In the equation $$x+y+z \equiv 0 \mod 3 $$ The elements of $S_1$ and $S_2$ cannot appear exact $2$ times. So the only possible situations are

  1. All of them are from the same set.
  2. One from each of the $3$ sets. For example: $x\in S_0, \, y\in S_1, \, z\in S_2$.

So there are in total $3\cdot \binom{4}{3} + 4\cdot 4\cdot 4 = 76$ different ways to do that.

$\endgroup$
  • $\begingroup$ why did you multiply 4c3 by 3? $\endgroup$ – Mahmudul Hasan Aug 18 '16 at 7:00
  • $\begingroup$ @Mahmudul Hasan: There are $3$ sets so you can first choose one of them say $S_1$, then choose $3$ elements out of $4$, e.g. $\{1,4,7\}$. There are $3$ ways to choose the set so the factor $3$ before $\binom{4}{3}$. $\endgroup$ – corindo Aug 23 '16 at 8:01

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.