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