2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Vera Apr 21 '17 at 12:52
  • $\begingroup$ The numbers can't be repeated like 3,3 or 6,6 $\endgroup$ – Nipun Wahi Apr 21 '17 at 12:53
  • $\begingroup$ 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. $\endgroup$ – Gerry Myerson Apr 21 '17 at 12:55
  • $\begingroup$ 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 $\endgroup$ – Nipun Wahi Apr 21 '17 at 12:58
  • $\begingroup$ 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 $\endgroup$ – Nipun Wahi Apr 21 '17 at 13:01
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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$.
$\endgroup$
  • $\begingroup$ I tried your method and got stuck in the midway $\endgroup$ – Nipun Wahi Apr 21 '17 at 12:59

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.