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

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

• As for your proposed method, you seem to miss several valid outcomes such as $1,2,12$. Every outcome you seem to count follows an arithmetic progression $a-k,a,a+k$, but this need not be the case. – JMoravitz Feb 10 '16 at 3:22
• I understood the mistake in my method. Thank you @JMoravitz – Aditya Dev Feb 10 '16 at 3:41
• This question appeared at this MSE link I and at this MSE link II. – Marko Riedel Feb 10 '16 at 22:33

## 2 Answers

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*}

• @JMoravitz That's reassuring. – N. F. Taussig Feb 10 '16 at 3:20

Number of solutions to $a+b+c=k$ where $a,b,c$ are positive integers is $\binom{k-1}{2}$. So the number of ways to choose is $$\sum_{k=1}^n\binom{3k-1}{2}={n\over2}(3n^2-1)$$

Edit: As JMoravitz notes below this counting accounts for ordered triples from the given set rather than subsets.

• Is my method wrong? – Aditya Dev Feb 10 '16 at 3:13
• Although true, the number of solutions to $a+b+c=k$ assumes that $a$ is considered different than $b$ as well as different from $c$. It also allows for repeated values to occur. Both of which seem to not be intended. I would consider the question to be about the number of subsets, not the number of ordered triples. As such, I don't expect this to be the solution intended. – JMoravitz Feb 10 '16 at 3:16