[Math] Pigeonhole Principle Issue five integers where their sum or difference is divisible by seven.

combinatoricsdiscrete mathematicspigeonhole-principleproof-writing

Given any five integers, there will be two that have a sum or difference divisible by 7. I'm trying to solve this using the Pigeonhole Principle, but it is not making sense to me, how this principle holds true in this case. Aren't the "pigeons" in this case "five" and the "holes" are "seven"? I'm so confused.

Best Answer

consider $a_n = x_n \mod 7$ In order to avoid a difference divisible by 7, all 5 $a_n$ must be distinct.

In order to avoid a sum divisible by 7, no two $a_n$ can sum to 7

So we actually have only 4 holes in which to put our 5 $a_n$

1) $a_n=0$

2) $a_n = 1 $ or $a_n = 6$

3) $a_n = 2 $ or $a_n = 5$

4) $a_n = 3 $ or $a_n = 4$

To avoid a sum or difference divisible by 7 we would need to put 5 integers into 4 holes with no more than one in each hole. This can't be done, therefore having at least one pair whose sum or difference is divisible by 7 is unavoidable.