How many ways to select 3 numbers from $1-30$ (each number is used only one time) so that the sum of them is a multiple of 3?
I got the answer is $1360$ by programming (check the sum of every combination), and
I also know the formula is $10^{3}+3\cdot\binom{10}{3}$, but how to explain it?
Best Answer
Consider the general case where $S\subset \mathbb{Z}$.
Let $A_i:=\{n\in S: n\equiv i \pmod{3} \}$, for $i=0,1,2$. Then the sum of three distinct numbers of $S=A_0\cup A_1\cup A_2$ is divisible by $3$ iff it has one of these forms: $$a_0+a_0+a_0,\quad a_1+a_1+a_1,\quad a_2+a_2+a_2,\quad a_0+a_1+a_2$$ with $a_i\in A_i$. Now enumerate them and you will get: $$\binom{|A_0|}{3}+\binom{|A_1|}{3}+\binom{|A_2|}{3}+|A_0||A_1||A_2|$$ where $|A_i|$ denotes the cardinality of the set $A_i$.