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$ ?

Thanks in advance!

  • $\begingroup$ @GerryMyerson They fixed it $\endgroup$ – mysatellite Jun 22 '15 at 13:47
  • $\begingroup$ 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 $\endgroup$ – Thomas Andrews Jun 22 '15 at 13:52
  • $\begingroup$ 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}. $\endgroup$ – 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.

  • $\begingroup$ You are also assuming order doesn't matter. $\endgroup$ – Thomas Andrews Jun 22 '15 at 13:54
  • $\begingroup$ @hunter got it. It was a silly after all. I overlooked the fact that no matter what group i chose 3 numbers from, their sum is divisible by 3. Thanks for that. $\endgroup$ – pr12015 Jun 23 '15 at 10:40
  • $\begingroup$ @ThomasAndrews there is nothing to assume here. The queastion itself guarantees the 'assumption'. $\endgroup$ – pr12015 Jun 23 '15 at 10:42

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.