1

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.

user1176409
  • 1
dampen_the_riot
  • 13

1 Answers1

1

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?

Alexander Geldhof
  • 2,439
  • 1
  • 6
  • 14
  • I don't understand how each $J_{i}$ contains 2⋅2/$j$ numbers. Wouldn't it contain 4n numbers? – dampen_the_riot Oct 22 '19 at 22:18
  • There are $j$ different J_i's and they are a partition (i.e. do not intersect); their union is the whole set. If they would all contain $4n$ numbers, then their union would contain $j \times 4n$ numbers. – Alexander Geldhof Oct 22 '19 at 22:20
  • Alright, I understand that part now, but I'm still not sure why if over half the numbers in at least of $J_{i}$ is selected, two must have difference $j$. – dampen_the_riot Oct 22 '19 at 22:53
  • Try explicitly writing one of those sets down. What is the difference of two adjacent numbers in such a set? And why does picking over half of the numbers in $J_i$ ensure there is an adjacent pair selected? – Alexander Geldhof Oct 23 '19 at 20:32
  • Thanks! I've got it now. – dampen_the_riot Oct 29 '19 at 04:23