# Integer pick with pigeon hole principle

Consider any set of $7$ unique positive integers. Prove that there's alway a way to pick a pair where either the difference or the sum of the pair is a multiple of $10$.

I know this is a trivial problem but it's driving me nuts. For some reason I can't find the right approach.

I've tried to consider all $\binom{7}{2} = 21$ possible pairs, and tried fitting them into $mod\space 10$ integer spaces. By the pigeon hole principle, there will be at least a set of $3$'s such that all three pair have the same congruence mod $10$. But I'm not sure how to proceed from that point, or if I'm on the right path.

## 2 Answers

If two of these 7 numbers, say $p$ and $q$, leave the same remainder, when divided by 10, then $p-q$ is divisible by 10.

If all 7 leave the 7 different remainders, when divided by 10, then at least 5 of their remainders are non-zero and different from 5, and hence are 5 different members of $$1, 9,\,\,\,\, 2,8,\,\,\,\, 3,7,\,\,\,\,4,6$$ Apparently, since they are five different ones, they occupy at least one of the four pairs above - each of these pairs has sum 10.

Let the nos be a1 , a2 , a3 ,a4 ,a5 ,a6 , a7 and without loss of generality , let a1 be the largest no

Define two groups Group 1 : a1+a2 a1+a3 a1+a4 ... a1+a7

Group 2 a1-a2 a1-a3 a1-a4 ... a1-a7

Now we have 14 nos , dividing them by 10 and comparing their remainders , we find that , by pigeon hole principle , atleast 2 leave the same remainder (as no of numbers = 14 , while no of possible remainders = 10)

Case 1 : Both numbers that have the same remainder lie in group 1 - Without loss of generality , let the nos be a1+a2 and a1+a3 , then the required no is a2-a3 ( subtracting two no that leave equal remainders (when divided by 10 ) results in a no divisible by 10

Case 2 : both nos lie in group 2 - Perform same operation as in case 1

Case 3: one lies in group 1 and one lies in group 2 - Perform same operation

Therefore , there is always a number divisible by 10