2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ +1 That doesn't really apply the hint, though. The hint is suggesting an alternate technique $\endgroup$ – Thomas Andrews May 15 '13 at 17:19
  • $\begingroup$ Definitely a perfect proof , but I was wondering how would go about applying the hint? $\endgroup$ – metric-space May 15 '13 at 17:22
  • 1
    $\begingroup$ @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$ $\endgroup$ – Ross Millikan May 15 '13 at 17:34

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.