0
$\begingroup$

I am trying to understand how to prove a Statement using the pigeonhole principle.

Prove the following result using the pigeon-hole principle. In every collection of 7 integers there are at least two whose difference is divisible by 6. any ideas? thanks in advance

$\endgroup$
  • $\begingroup$ Use the fact that for every $3$ consecutive integers, one will be divisible by $3$ and for every $2$ consecutive integers one will be even and divisible by $2$. $\endgroup$ – JohnColtraneisJC Nov 29 '17 at 14:28
  • 3
    $\begingroup$ Hint: there are exactly $6$ possible remainders on division by six. If you have seven integers, then at least two have to have the same remainder. $\endgroup$ – lulu Nov 29 '17 at 14:28
0
$\begingroup$

Consider the residues of the 7 numbers when divided by 6 (their classes modulo 6). There are 6 possible residues, so one must be used twice, by the pigeonhole principle. The difference of the corresponding original integers is a multiple of 6.

$\endgroup$
0
$\begingroup$

There are six possible remainders modulo 6: those are $0, 1, 2, 3, 4, 5$.

Since there are $7$ integers in your set, by the pigeonhole principle there will be at least two of them with the same remainder modulo 6. Their difference will then be divisible by $6$.

$\endgroup$
0
$\begingroup$

By the remainder's theorem, every integer number divided by $6$ is of the form: $$n=6q+r$$ where $0 \leq r < 6$

Since there are $6$ possible remainders, while you have $7$ numbers, at least two numbers must have the same remainder divided by $6$. Therefore, the difference of these two numbers must be divisible by $6$.

$\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.