[Math] Number of ways of selecting 3 numbers from $\{1,2,3,\cdots,3n\}$ such that the sum is divisible by 3

combinatoricsdivisibility

Find the Number of ways of selecting 3 numbers from $\{1,2,3,\cdots,3n\}$ such that the sum is divisible by 3. (Numbers are selected without replacement).

I made a list like this:
enter image description here
The sum of all elements along such diagonals are divisible by 3. Number of ways of selecting such numbers is $3n-2$

Then I shifted the second row by one element and third row by one element behind second row:

enter image description here
Again the sum of elements are divisible by 3. Total number of ways is $3n-4$.

In the next list, I will shift the second row by two elements and third row by 2 elements behind second row. The elements along a diagonal will be $\{1,4,7\}\cdots\{3n-6,3n-3,3n\}$. Sum is divisible by 3. Number of such possibilities is $3n-6$.

The total number of ways is $3n-2+3n-4+3n-6+\cdots$

what will be the last case?

Best Answer

Let $S = \{1, 2, 3, \ldots, 3n - 2, 3n - 1, 3n\}$. Let \begin{align*} A & = \{k \in S \mid k \equiv 0 \pmod{3}\}\\ B & = \{k \in S \mid k \equiv 1 \pmod{3}\}\\ C & = \{k \in S \mid k \equiv 2 \pmod{3}\} \end{align*} Observe that $|A| = |B| = |C| = n$. We can choose three numbers from $S$ in the following ways:

  1. Choose $3$ elements of $A$, which can be done in $\binom{n}{3}$ ways.
  2. Choose $3$ elements of $B$, which can be done in $\binom{n}{3}$ ways.
  3. Choose $3$ elements of $C$, which can be done in $\binom{n}{3}$ ways.
  4. Choose $1$ element from each subset, which can be done in $\binom{n}{1}^3$ ways.

Hence, the number of ways of selecting a subset of three numbers in $S$ whose sum is divisible by $3$ is \begin{align*} 3\binom{n}{3} + \binom{n}{1}^3 & = 3 \frac{n(n - 1)(n - 2)}{3!} + n^3\\ & = \frac{n^3 - 3n^2 + 2n}{2} + n^3\\ & = \frac{3n^3 - 3n^2 + 2n}{2} \end{align*}

Related Question