Show that if 12 integers are chosen there are always two whose sum or difference is divisible by 20.

Question

Also, prove that this is sharp, i.e., one can pick 11 integers so that the sum or the difference of any two of the chosen integers will never be divisible by 20.

I'm trying to solve this problem using the pigeon hole principle.

Answer 1

Welcome to MSE! For the best response from the MSE community, could you please show your efforts and working next time?

For part 1:

We see that amongst any group of 12 integers, there is always going to be two numbers who sum is a multiple of 10, and who have the same tens digit (for example, 62 and 68 or 76 and 74).

Hence they will end in 0, and have an even tens digit, as odd + odd = even, and even + even = even and thus be divisible by 20. So by the pigeonhole principle, we can see that amongst any 12 numbers, two numbers' sum will be divisible by 20.

For part 2

As pointed out by @AlexeyBurdin and @Peter, we can simply just use the integers 0 - 10, non of which have a difference or sum divisible by 20, as 10 + 9 (largest possible numbers in this set) do not even reach 20 in their sum.

Edit:

In case you weren't convinced, see this excellent exhaustive code program written by @AlexeyBurdin which proves the 2nd part, and which I thought I'd acknowledge due to its clarity and usefulness.

Answer 2

The numbers must have distinct reisudes mod $20$ to avoid that a difference is divisible by $20$. Now consider the pairs $(1,19),(2,18),\cdots (9,11)$ At most one of the residues in any of those pairs is allowed to occur, with residues $0$ and $10$ we get that we can have at most $11$ residues.

The set of the integers from $0$ to $10$ proves that this bound is sharp.