0
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

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.