Select $2n+1$ numbers from {$1,2,3,…,4n$}, prove any positive integer j that divides $2n$,there must be two selected numbers whose difference is j.

pigeonhole-principle

I'm doing practice problems to familiarize myself with the Pigeonhole Principle, and I encountered this:

Suppose $2n+1$ numbers are selected from {$1,2,3,…,4n$}. Using Pigeonhole Principle, show that for any positive integer $j$ that divides $2n$, there must be two selected numbers whose difference is $j$.

I've been trying to figure out this problem for hours without any luck; any pointers would be much appreciated.

Best Answer

Note that half the numbers plus one are selected.

Let $j$ be such a positive integer. We can now divide the set into $j$ sets $J_i$ of equal size (because $j$ divides $4n$), determined by their remainder after division by $j$. I.e.

$$J_i = \{ n | n \cong i \mod j \}$$

with $i$ ranging from $0$ to $j - 1$.

Each of them contains $2\cdot \frac{2n}{j}$ numbers, which is an even number.

As we have picked $2n + 1$ numbers, through the pigeonhole principle, over half of the numbers in (at least) one of the $J_i$ have been selected. Two of them must have difference $j$. Why?

Related Question