# Total number of ways of selecting two numbers from the set {1,2,3,4,5…,3n} so that their sum is divisible by 3 is S. Find S?

Total number of ways of selecting two numbers from the set $\{ 1,2,3,4,5..........,3n \}$ so that their sum is divisible by $3$ is $S$. Find $S$?

This question came in my test and we were supposed to do it in less than $3$ minutes. I still can't get the answer

• Question: are the selected numbers allowed to be equal? Hint: if one number has been selected then how many possibilities are left for the second number? – Vera Apr 21 '17 at 12:52
• The numbers can't be repeated like 3,3 or 6,6 – Nipun Wahi Apr 21 '17 at 12:53
• Can you solve it for $n=1$, Nipun? for $n=2$? $n=3$? maybe seeing how those cases work out will give you the idea for the general case. – Gerry Myerson Apr 21 '17 at 12:55
• I tried replacing values for n and found the general case in the test after finding upto n=4 but I couldn't prove it for all natural number – Nipun Wahi Apr 21 '17 at 12:58
• Gerry myerson I got the idea of using induction now , first find the general case by putting values of n and then prove it by induction to be true – Nipun Wahi Apr 21 '17 at 13:01

If the first number is divisible by $3$, then so is the other one; we choose two multiples of $3$ out of $n$, total ${n\choose 2}$ possibilities.

If the first number (say, $n$) is not divisible by $3$, then the remainder of the second number ($m$) by division by $3$ is different. So either $n$ or $m$ is $1\mod 3$ and the other $2\mod 3$. Since order isn't relevant, we can assume $n\equiv 1\mod 3$ and $m\equiv 2\mod 3$, so that we have ${n\choose 1}{n\choose 1}$ possibilities.

Thus,

$$S={n\choose 2}+{n\choose 1}{n\choose 1}=\frac12n\left(3n-1\right)$$

Hint: there are two different cases, so try to calculate how many ways there are for each case separately, and add. The two cases are:

1. choose two multiples of $3$;
2. choose one number which leaves remainder $1$ when divided by $3$, and one number which leaves remainder $2$.
• I tried your method and got stuck in the midway – Nipun Wahi Apr 21 '17 at 12:59