0
$\begingroup$

Show that given any set of seven distinct integers, there must exist two integers in this set whose sum or difference is a multiple of 10.

I'm having a hard time with this pigeon hole section. So I'm not sure how to go about this problem. I know that the first digit can be 1-9 and next 0-9 and so forth but the last must only be 0.

$\endgroup$
3
$\begingroup$

The basic argument you want works something like this. We can deal with all of the numbers modulo $10$, since divisibility by $10$ is all we care about.

Suppose the numbers somehow defied the condition. Then all of the numbers would have to be different modulo $10$; otherwise, the difference between two numbers that are the same modulo $10$ would be divisible by $10$.

Now how about their sums? There are six possible ways the sum of two numbers might be divisible by $10$:

  • They are both equivalent to $0$ (modulo $10$).
  • They are equivalent to $1$ and $9$.
  • They are equivalent to $2$ and $8$.
  • They are equivalent to $3$ and $7$.
  • They are equivalent to $4$ and $6$.
  • Or, they are both equivalent to $5$.

There are thus six different classes of numbers, and whenever two numbers are in the same class, either their sum or their difference (or both) must be divisible by $10$.

Can you take it from there?

$\endgroup$
  • $\begingroup$ So the congruence classes mod 10 are pigeon holes? $\endgroup$ – StillLearning Apr 24 '17 at 5:38
  • $\begingroup$ @StillLearning: Not quite. The equivalence classes are the bulleted items above. $\endgroup$ – Brian Tung Apr 24 '17 at 15:17

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.