2
$\begingroup$

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.

$\endgroup$

2 Answers 2

3
$\begingroup$

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

$\endgroup$
0
$\begingroup$
  • 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$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy