combinatorics problem - sum of integers

Question

I'm studying for my combinatorics exam and I'm not quite convinced about this problem:

How many pairs of distinct integers from $1, 2, 3, ..., 60$ are there whose sum of integers is divisible by $3$?

The way I solved it is, I divided the integers into $3$ groups:

$0 \bmod 3, 1 \bmod 3, 2 \bmod 3$ (0m3,1m3,2m3 for future references).

Each group includes $20$ integers, and from there I sorted out all the possible combinations.

It's a sum of two integers, so possible combinations are:

(0m3,0m3),(1m3,1m3),(2m3,2m3),(0m3,1m3),(0m3,2m3),(1m3,2m3).

If two integers are from the same group, then it's $C(20,2)$, and if they are not it's $20^2$. Since there are 3 cases for each group, the answer would be:

$3\cdot C(20,2) + 3\cdot (20^2)$

It turns out that was not the answer. What am I missing here?

Answer 1

The problem with your solution is that your cases (1m3,1m3), (2m3,2m3), (0m3,1m3), and (0m3,2m3) don't work. The counterexamples to each cases are actually all numbers that fit the criteria, but here are some specifics so you can see for yourself: (4,4), (5,5), (3,4), and (3,5).

Now the remaining cases that work are (0m3, 0m3) and (1m3, 2m3). The first case has $\binom{20}{2}$ that work. The second case has $20^2$ cases that work.

Answer 2

There are only 2 cases which satisfy your criterion - (0m3,0m3) and (1m3,2m3) . The numbers are $\binom{20}{2}+ 20^2=590$.

Answer 3

You're almost there.

The two ways, as you've stated, are adding two numbers that are $0 \mod 3$, or adding a number that's $1 \mod 3$ to one that's $2 \mod 3$.

Since you're drawing from the same pool of numbers in the first case, choose two of them since they have to be distinct: $_{20}C_2$.

In the second case, you know that the numbers are distinct (no number is both $1 \mod 3$ and $2 \mod 3$) so pick one from the first group, and one from the second: $20^2$.

So, $190 + 400 = 590$ pairs.

Answer 4

Others have pointed out your mistake, so I'll just add a way to answer this question a little differently.

Yes, if you look at the numbers modulo $3$, there are an equal number of numbers in each group. But that means that the sums of pairs of numbers will also be divisible in $3$ equally sized groups. Hence, the number of pairs whose sum is divisible by $3$ is exactly one third of all possible pairs.

So that is:

$$\frac{60 \choose 2}{3}=590$$

EDIT

@antkam correctly noted that this logic only works with replacement! OK, so why was I getting the correct result? It is because $3$ is odd. That is, we can save the above argument by pointing out that there is a one third chance of getting a number that is $\equiv 0$, in which case you need a number from the same group to get a 'match', i.e. there is a $\frac{19}{59}$ chance of getting a 'match', and for each of the other groups you need a number from a different group, and thus you have a $\frac{20}{59}$ chance of getting a match for each of those ... for a total of a one third chance of getting a match. This logic will generalize for any odd number, since for each of the groups with modulo not zero the match has to come from a different group.