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

Question

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.

Answer 1

• 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$

Answer 2

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