# Using Pigeonhole Principle find two integers such that their difference equals an integer $j$

The source of the problem: https://courses.csail.mit.edu/6.042/spring18/mcs.pdf

The problem:

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

My Attempt at a Solution

Let the pigeons be the $$2n+1$$ numbers, and the holes be the equivalence classes of $$\bmod j$$. $$j \mid 2n \Rightarrow j \leq 2n$$, so by Pigeonhole principle there is at least one equivalence class with at least 2 integers. This means there are two integers, $$x, y$$ in the same equivalence $$\bmod j$$, so $$x \equiv y \pmod {j} \Rightarrow j \mid x - y$$.

Now here is where I am stuck. I don't know how I can show that there difference is exactly $$j$$. So far, I've only shown that there must be 2 selected numbers whose difference is a multiple of $$j$$. I'm thinking I might want to reuse the Pigeonhole principle, but I am not sure what I would use for pigeons and holes again.

Rearrange the integers from $$1$$ to $$4n$$ into

\begin{equation}\begin{aligned} \{& (1,j+1), (2, j + 2), (3, j + 3), \, \ldots \, , (j, 2j), \\ & (2j + 1, 3j + 1), (2j + 2, 3j + 2), \, \ldots \, , (3j, 4j), \\ & \vdots \\ & (4n - 2j + 1, 4n - j + 1), (4n - 2j + 2, 4n - j + 2), \, \ldots \, , (4n - j, 4n) \} \end{aligned}\end{equation}\tag{1}\label{eq1A}

Note each member of the set above is a pair of integers with a difference of $$j$$. Also, since $$j \mid 2n \implies 2j \mid 4n$$, all of the integers from $$1$$ to $$4n$$ are in this set exactly once each. Finally, this gives that the number of elements of the set is the $$4n$$ integers divided by the $$2$$ integers in each pair, i.e., $$\frac{4n}{2} = 2n$$. Alternatively, you also can get the number of elements by multiplying the number of columns times the number of rows, i.e.,

$$j \times \left(\frac{4n-2j}{2j} + 1 \right) = j \times \left(\frac{2n}j - 1 + 1\right) = 2n \tag{2}\label{eq2A}$$

Thus, by the Pigeonhole principle, choosing $$2n + 1$$ integers between $$1$$ and $$4n$$ means that both of the integers from at least one of the element pairs in \eqref{eq1A} must be chosen, with these $$2$$ integers therefore having a difference of $$j$$.

• If $$j$$ divides $$2n$$ then let $$k=\frac{2n}{j}$$

• Each of the $$j$$ equivalence classes $$\bmod j$$ partitioning $$\{1,2,\ldots, 4n\}$$ has $$\frac{4n}{j}=2k$$ holes.

• At least one of theses equivalence classes must have at least $$k+1$$ pigeons as $$jk =2n < 2n+1$$.

• $$k+1$$ pigeons and $$k$$ gaps between them would need at least $$2k+1$$ holes so, with only $$2k$$ holes, two of the pigeons must be in "adjacent" holes in their equivalence class, meaning they differ by exactly $$j$$

• Hi, thanks for your answer. Could you elaborate why each class has 4n/j holes? I’m not very sure what that means
– user843046
Apr 27, 2021 at 23:33
• @a6623 There are $4n$ possible values ("holes") in $\{1,2,\ldots, 4n\}$, split into $j$ classes so $\frac{4n}{j}=2k$ in each class Apr 27, 2021 at 23:36