Prove that among any set of 34 different positive integers that are at most 99, there is always a pair of numbers that differ by at most 2.

Question

Alright, so I'm pretty new at this. I feel like this should be a pretty simple solution, but I don't know how to start.

So here's where I was going

If we have a set $\{1,2,...,99\}$ and then I start making groups that have a pair of integers that differ by 2 at the most. $$ \text{group}_1 = (1,2)\\ \text{group}_2 = (3,4) \\ \vdots \\ \text{group}_{49} = (97,98) $$ Now I know I don't use $99$ but it says at most $99$. Another thing I could do is make the groups like so \begin{align} \text{group}_1 &= (1,3) \\ \text{group}_2 &= (2,4)\\ \text{group}_3 &= (5,7)\\ \text{group}_4 &= (6,8)\\ &\vdots\\ \text{group}_{48} &= (94,96)\\ \text{group}_{49} &= (95,97)\\ \text{group}_{50} &= (98,99) \end{align} and I think this works better.

Now from here I'm not sure how to progress, in fact I think this is the wrong path to go down but I don't know how to solve this in a different way. Maybe I could use the pigeon hole principle but I don't know how.

Answer 1

If you want no pair of integers to differ by two or less, then once you pick one integer in your set, you can't pick either number to the left or right of it. So it's helpful to think about picking 34 blocks of three consecutive integers: $(x-1,x,x+1)$ where $x$ is the number we're actually including in our set. The blocks centered at 1 and 99 can be thought to include 0 and 100 even though those aren't in our set. Just remembered we can't pick a block centered at 0 or 100.

Then notice that we actually can't have these blocks overlap either since if they did their centers would differ by two or less. So we can reformulate the problem as asking: is there a way to pick 34 blocks of three consecutive integers in the set $\{0, 1, \ldots , 100\}$ so that no two blocks overlap? The answer is no by the pigeonhole principle. We'd have $34 \times 3 = 102$ numbers in these blocks but only have 101 numbers in our set.

Edit: I actually had this exact question on my discrete math midterm in undergraduate and got completely stumped. Three years later I'm in a math PhD program hoping to work in combinatorics!

Edit 2 (cleaner, direct solution): We can split the set $\{1, \ldots, 99\}$ into the blocks: $[1,2,3], [4,5,6], \ldots [97,98,99]$. There are 33 blocks. If we pick any 34 numbers from this set, then we will pull two from the same block by the pigeonhole principle. But then these numbers would differ by two or fewer.

Answer 2

The fastest and simplest way to prove this is:

List the distinct positive integers as $z_1,\dotsc,z_{34}$ and try to construct the $z_n$'s s.t. there isn't a consecutive pair of positive integers that differ by at most 2. Clearly the best strategy would be "$z_1=1$" and "add 3" so you can fit as many $z_n$'s as possible. Then we have $$z_1=1,z_2=4,\dotsc$$ If you keep going, you will deduce that $z_n=3(n-1)+1$ so $z_{34}=3(34-1)+1=100>99$. This means that on constructing the 34th integer, in order to maintain the fact that "there isn't a consecutive pair of positive integers that differ by at most 2", $z_{34}$ must be $100$. But the $z_n$'s must be at most 99 so you can't do that. Hence even the best strategy constructs a list of $z_n$'s s.t. there is a consecutive pair of positive integers that differ by at most 2.

Answer 3

This is a proof by contradiction:

1. Assume that there exists a set A, with cardinality 34, and has no pairs $(a,b)$ such that the difference $|b-a| < 3$.

2. The set doesn't have duplicates. Order them by value. So we have $a_1 < a_2 < a_3 < ... < a_{34}$.

3. Consider the pair $(a_1, a_2)$. For each $i > 1$, let's define $a_i^{L}$ which denotes the lowest possible value $a_i$ could take given the assumption in step 1.

4. $a_2^L$ should be greater or equal to $a_1 + 3$; otherwise $(a_1, a_2)$ will have $|a_2 - a_1| < 3$.

5. We also know $a_1 < a_2^L \leq a_2$. Or $a_1 + 3 \leq a_2^L \leq a_2$

6. Similarly, for any $i, (i+1)$, we have $a_i + 3 \leq a_{i+1}$.

7. So, $a_2^L + 3 \leq a_3^L$. This in turn implies $a_1 + (2 * 3) \leq a_3^L$, $a_1 + (3 * 3) \leq a_4^L$, ..., and $a_1 + (33 * 3) \leq a_{34}^L$.

8. The lowest possible value $a_1$ could take is $1$. For $a_1 = 1$, the lower bound of $a_{34}$ is $ 1 + 33 * 3 = 100$. We know that $a_{34}^L \leq a_{34}$. For any value of $a_1 \gt 1$, $a_{34}$ will be greater than 100. This is a contradiction because by definition all integers are lower than 100. Therefore, the assumption in step 1 must be false, proving your statement.

Answer 4

This actually uses the pigeonhole principle ( the idea that having more objects than containers forces 2 from/into the same container) . You started out with the correct idea, just a bad implementation of the idea. Subtraction solutions (differences) only care about 1 endpoint in their count. So for a difference of 2 to occur, you need numbers in sets of cardinality 3. As 99=3*33 you can only make 33 such sets that are disjoint (don't have a common element). But selecting 34 numbers from 33 sets, we must select 2 from the same set, the differences of which, don't exceed 2 (3 consecutive integers).

This actually works for any sets of 34 integers, taken from a set of 99 consecutive integers.