Find the number of ways of choosing three numbers from the set ${1,2,3,…,20}$, so that the sum of the three numbers is divisible by $3$. I wrote $a+b+c=3k$, where $k=1,2,...20$, till $k=6$, there were no problems, but then restrictions started($a<21$). Even if I come to know of the correct method from here, the summation of all the answers is a tedious job(the answers come in binomial coefficients). Therefore, s there a shorter way?


We only need concern ourselves with congruence $\bmod 3$.

There are $7$ numbers that are $1\bmod 3$

There are $7$ numbers that are $2\bmod 3$

There are $6$ numbers that are $0\bmod 3$

We now count the ways to add to $0\bmod 3$:

Three zeros:

$0+0+0$ (There are $\binom{6}{3}$ of these)

Two zeros:

One zero:

$0+1+2$ (There are $7\cdot7\cdot 6$ of these )

No zeros:

$1+1+1$ (There are $\binom{7}{3}$ of these)

$2+2+2$ (There are $\binom{7}{3}$ of these)

Adding up the answer is $\binom{6}{3}+7\cdot7\cdot6+2\binom{7}{3}=384$

There are $\binom{20}{3}=1140$ ways to choose, $3$ numbers of $20$. A third of that would be $380$. So more than a third of the subsets of size three are $0\bmod 3$


The three numbers might all be multiples of 3, in which case there are $6 \choose 3$ ways to pick them.

There are several other possibilities: they might all be congruent to 1 modulo 3, for example. Find all such possibilities and count accordingly.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy