Combinatorics Problem From JMO

Question

In how many ways $four$ different numbers can be chosen from $0,1,2,3,4,5,6,7,8,9$ such that the sum of those four numbers is divisible by $3$? Here $(a,b,c,d)$;$(b,a,c,d)$....are considered to be the same.

Answer 1

To begin with, you can simplify the problem by taking $\bmod 3$.

The list $\{0,1,2,3,4,5,6,7,8,9\}$ becomes $\{0,1,2,0,1,2,0,1,2,0\}$.

Now lets list possible multiples of $3$.

$$1 1 1 0 : 4C1 = 1\cdot 4$$ (We have three ones and we need to select one $0$ from four $0$'s.)

$$1 1 2 2 : 3C2\cdot 3C2 = 9$$ (We have three $2$'s , three $1$'s and we need to select two $2$'s and $1$'s.)

$$1 2 0 0 : 3C1\cdot 3C1\cdot 4C2 = 54$$ (We have three $1$'s ,three $2$'s, four $0$'s and we need to select one $2$ and one $1$ and two $0$'s.)

$$2 2 2 0 : 3C3\cdot 4C1 = 4 .$$ (We need to select three $2$'s and one $0$).

$$0 0 0 0 : 1 .$$ (We need to select four $0$'s ).

Total : $4 + 9 + 54 + 4 + 1 = 72.$