Q:

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

A:

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)$$

