Choose 8 distinct integers from $\{1, 2,\dots,16,17\}$. Show that the eight contain at least three pairs with a common difference for _any_ choice.

Question

This problem is from the 1999 Canada National Olympiad. I am stuck trying to prove the first part using the pigeonhole principle. Is there a refinement that will allow it to be used more sharply, or is there some clever use of parity that would prove part 1? or another approach?

As far as part 2 is concerned, I imagine that a solution will emerge naturally from the solution to part 1.

Suppose $a_1,a_2,\dots,a_8$ are eight distinct integers from $\{1,2,\dots,16,17\}$. Show that there is an integer $k>0$ such that the equation

$a_i−a_j=k \tag{1}$

has at least three different solutions.

---

Also, find a specific set of 7 distinct integers from $\{1,2,\dots,16,17\}$ such that the equation $a_i−a_j=k$ does not have three distinct solutions for any $k>0$.

---

Suppose that the selected $a_n$ are ordered so that $a_1<a_2<\dots<a_8$. Define the 1-gaps between successive terms as

$\alpha_n = a_{n+1}-a_n,\: 1 \le n \le 7 \tag{2}$

Clearly these seven $\alpha_k$ can sum to at most 16. If three of these 1-gaps have the same value, $k$, then equation (1) will have three solutions for that same $k$, so this must be avoided. To meet both these conditions

$(\alpha_1,\alpha_2,\dots,\alpha_7)\text{ must be a permutation of }(1,1,2,2,3,3,4) \tag{3}$

In an effort to apply the pigeonhole principle, now define the 2-gaps

$\beta_n = a_{n+2}-a_n,\:\text{ for }1 \le n \le 6 \tag{4}$

These relate to the 1-gaps as $\beta_n = \alpha_n + \alpha_{n+1},\:\text{ for }1 \le n \le 6 \tag{5}$

There are six 2-gaps, and they can have values such that for all $n$

$4 \le \beta_n \le 7 \tag{6}$

We can have only one of the $\beta_n=4$, as there is an $\alpha_n=4$. Since two different $\beta_n$ can share the same value (for $5,6,7$), there are thus seven slots and only six objects to place, so the pigeonhole principle does not force three solutions to equation (1).

Answer 1

You're almost there – now you just need to combine the information about the $1$-gaps and the $2$-gaps.

Assume there are two $2$-gaps of $7$. Then the $1$-gap of $4$ must be surrounded by the two $1$-gaps of $3$. But that leaves no $1$-gaps to create $2$-gaps of $6$, and by your pigeonhole argument we must have at least one $2$-gap of $6$.

So there aren't two $2$-gaps of $7$, and we know there's at least one, so there's exactly one. So the $4$ is next to a $3$, and since we're missing a $7$ we need to fill all the remaining $2$-gap slots. To get the two $2$-gaps of $6$, we need to put the second $3$ on the other side of the first $3$ and a $2$ on the other side of the $4$. But that doesn't allow us to create two $2$-gaps of $5$, which completes the proof.

Answer 2

Here's a slightly different approach: Having nailed down the values 1-gaps, let's try to determine the exact sequence.

Consider the sequence of 1-gaps.
Since the 2-gaps cannot be 2, the 1-gaps of $1, 1$ have to be apart.
Since the 2-gaps cannot be 3, the 1-gaps of $1, 2$ have to be apart.
Since the 2-gaps can be 4 at most once, the 1-gaps of $1, 3$ and $2, 2$ can only occur at most once.
Hence, $1$ can only be paired with 4 and 3 (once), which means the sequence must look like (or its reverse):
$$1, 4, A, B, C , 3, 1$$

We already have $1, 3$, so we cannot have $2, 2$, thus the sequence must be (or its reverse):

$$1, 4, 2, 3, 2, 3, 1$$

Now, the 2-gaps of 5 appears 3 times, hence contradiction.