3

The following question is from cut-the-knot.org's page on the pigeonhole principle

Question

Prove that however one selects 55 integers $1 \le x_1 < x_2 < x_3 < ... < x_{55} \le 100$, there will be some two that differ by 9, some two that differ by 10, a pair that differ by 12, and a pair that differ by 13. Surprisingly, there need not be a pair of numbers that differ by 11.

The Hint

Given a run of $2n$ consecutive integers: $a + 1, a + 2, ..., a + 2n - 1, a + 2n$, there are n pairs of numbers that differ by n: $(a+1, a+n+1), (a + 2, a + n + 2), \dots, (a + n, a + 2n)$. Therefore, by the Pigeonhole Principle, if one selects more than n numbers from the set, two are liable to belong to the same pair that differ by $n$.

I understood the hint but no concrete idea as to how to apply it, but here are my current insights:

My Insights

break the set of 100 possible choices into m number of 2n(where $n \in \{9,12,13\}$ ) consecutive numbers and since 55 numbers are to be chosen , show that even if one choses randomly there will be n+1 in one of the m partitions and if so, by the hint there will exist a pair of two numbers that differ by n.

metric-space
  • 341

2 Answers2

5

The easiest example is to do $10$. Then break up your set into $5$ sets, $$\{1,\dots,20\}\\\{21,\dots 40\}\\\vdots\\\{81,\dots,100\}$$

Since you have selected $55$ elements, you must have selected $11$ elements from one of these partitions. Then from the hint, you are done.

The case for $10$ is easy because $20$ divides $100$. The case of $12$ is harder. Partition the numbers as:

$$\{1,\dots,24\}\\\{25,\dots,48\}\\\{49,\dots,72\}\\\{73,\dots, 96\}\\\{97,98,99,100\}$$

Now we know that we've selected at least $51=55-4$ from the first four sets, and hence at least $13$ from one of them, and again we are done by the hint.

The problem for $11$ is that the "remainder" is large. When we partition $100$ into sets of $22$, we are left with $12$ elements. That's a large enough number of elements left to "break" the logic above - we can pick up to $11$ different elements from that remainder, and we have $44$ to parcel out amongst the first four partitions, which we can do by putting $11$ in each partition. It is not hard to find a counter-example for $11$ precisely this way.

More generally, given $N$ and $k$, let $m=k\left\lfloor \frac{N}{2k}\right\rfloor$. Then you can select from $\{1,\dots,N\}$ the following number of elements:$$m + \min(k,N-2m)$$ and not get a pair that differ by $k$. But it you try to select more than that number, you must get a pair with difference $k$.

In the case $N=100$ and $k=11$, $m=44$ and $\min(k,N-2m)=11$ so we can select $55$ such numbers.

Thomas Andrews
  • 177,126
3

Here is $9$ done explicitly: Break the set into subsets with a difference of $9$: $\{1,10,19,28,\ldots,100\},\{2,11,20,\ldots 92\},\ldots \{9,18,27,\ldots 99\}$. Note that there is one subset with $12$ members and eight with $11$ members. If you want to avoid a pair with a difference of $9$ among your $55$ numbers, you can't pick a pair of neighbors from any set. That means you can only pick six from within each set, but that gives you only $54$ numbers, so with $55$ you will have a pair with difference $9$.

The reason this fails with $11$ is you get one subset with $10$ members and ten with $9$ members. You can pick $5$ out of each and avoid neighbors.

Ross Millikan
  • 374,822
  • 2
    +1 That doesn't really apply the hint, though. The hint is suggesting an alternate technique – Thomas Andrews May 15 '13 at 17:19
  • Definitely a perfect proof , but I was wondering how would go about applying the hint? – metric-space May 15 '13 at 17:22
  • 2
    @nerorevenge: To apply the hint for $9$, break the numbers into $[1,18],[19,36],[37,54],[55,72],[73,90],[91,100]$ The first five can accommodate $9$ numbers each, so you need to pick all $10$ of the last set. But that includes $91$ and $100$ – Ross Millikan May 15 '13 at 17:34