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

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?

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.

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.

• why did you multiply 4c3 by 3? – Mahmudul Hasan Aug 18 '16 at 7:00
• @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}$. – corindo Aug 23 '16 at 8:01