Eight Integers

Book: A Walk through Combinatorics

Prove that among eight integers, there are always two whose difference is divisible by seven.


Let's write each number as 7xi+yi7x_i+y_i.

If yi=yjy_i = y_j for some i,ji, j, then the difference between the iith and jjth number

7xi+yi7xjyj=7(xixj)7x_i + y_i - 7x_j - y_j = 7(x_i - x_j)

which is divisible by 77.

Now we prove that there must always be some i,ji, j such that yi=yjy_i = y_j via the Pigeonhole Principle.

The possible set of values for yiy_i is {0,1,2,3,4,5,6}\{0, 1, 2, 3, 4, 5, 6\}.

The set only contains 77 values while we have 88 integers. So by the pigeonhole principle, one of the 77 values will be repeated.