Question

Let k be a positive integer. In how many ways can one select three distinct numbers from the set {1,2,..., 3k} such that their sum is divisible by 3

Answer 1

Reduce the numbers in the list modulo 3 to get the set

{1, 2, 0, 1, 2, 0, …, 1, 2, 0}

containing $k$ copies each of 1, 2, and 0.

Take any 3 elements from the list. Their sum is divisible by 3 if those elements' residues also sum to 3 ≡ 0 (mod 3). To get a sum of 0, we must make one of the following choices:

• 3 elements each with the same residue, so

0 + 0 + 0 ≡ 0 (mod 3)

1 + 1 + 1 ≡ 3 ≡ 0 (mod 3)

2 + 2 + 2 ≡ 6 ≡ 0 (mod 3)

• 1 element each with different residues, so

0 + 1 + 2 ≡ 3 ≡ 0 (mod 3)

There are

$\dbinom k3 \dbinom k0 \dbinom k0 = \dfrac{k(k-1)(k-2)}6$

ways of choosing 3 elements with a given residue and 0 elements with any other residue, hence

$3\dbinom k3\dbinom k0\dbinom k0 = \dfrac{k(k-1)(k-2)}2$

ways of choosing any 3 elements with the same residue, and there are

$\dbinom k1 \dbinom k1 \dbinom k1 = k^3$

ways of choosing any 3 elements with distinct residues.

So, the total number of ways of making the selection is

$3\dbinom k3\dbinom k0^2 + \dbinom k1^3 = \boxed{\dfrac32 k^3 - \dfrac32 k^2 - k}$