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?

  • 2
    $\begingroup$ 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. $\endgroup$ – JMoravitz Feb 10 '16 at 3:22
  • $\begingroup$ I understood the mistake in my method. Thank you @JMoravitz $\endgroup$ – Aditya Dev Feb 10 '16 at 3:41
  • $\begingroup$ This question appeared at this MSE link I and at this MSE link II. $\endgroup$ – Marko Riedel Feb 10 '16 at 22:33

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

  • $\begingroup$ @JMoravitz That's reassuring. $\endgroup$ – 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.

  • $\begingroup$ Is my method wrong? $\endgroup$ – Aditya Dev Feb 10 '16 at 3:13
  • $\begingroup$ 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. $\endgroup$ – JMoravitz Feb 10 '16 at 3:16

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.