# In how many ways 3 numbers can be chosen from a from the set {1, …, 18} so that their sum is divisible by 3?

In how many ways 3 numbers can be chosen from a from the set {1, ..., 18} so that their sum is divisible by 3?

Now, I've seen the solution, but I can't get my head around one detail. The solution goes as follows: $$3C^{6}_{3}+C^{6}_{1}C^{6}_{1}C^{6}_{1}=216+60=276$$

The question is: Why do we need to multiply $C^{6}_{3}$ by $3$ ?

• @GerryMyerson They fixed it – mysatellite Jun 22 '15 at 13:47
• Are you counting ordered sums? Is $\{1,2,3\}$ the same as $\{1,3,2\}$? Are repetitions allowed? This question, as is, is not complete – Thomas Andrews Jun 22 '15 at 13:52
• I thought it was clear that if you add up {1, 2, 3} you get the same as when you add up {1, 3, 2}. – pr12015 Jun 22 '15 at 14:08

For the sum to be divisible by $3$, either all numbers must be congruent to each other mod $3$, or all numbers must be different mod $3$.
All numbers congruent mod $3$: there are $3$ congruence classes to choose with $6$ numbers a piece. So we get $3 {6 \choose 3}$ if you aren't allowed to repeat, and $3 \cdot 6^3$ if you are. (Presumably you aren't, by your formula.) If you don't multiply by $3$ here, you're only counting one of the 3 congruence classes.
All numbers distinct mod $3$: now you get $6^3$, since you're choosing one from each set of $6$.
So the final answer is $$6^3 + 3{6 \choose 3}$$ as you have written.