# 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.

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).

• The problem is worng because by exampls for $k=23456712$ doesnt exist any solution. – Masacroso Jul 26 '15 at 23:16
• Only one value of $k$ is needed where there are three different pairs with a difference of $k$. Any two pairs can have one element in common, in my interpretation of the problem. – Marconius Jul 26 '15 at 23:24
• @Masacroso The problem is about $\exists k$ (Existential quantification), not $\forall k \in \mathbb{N}$. I fail to see how the problem is wrong. – 吖奇说 ARCHY SHUō Jul 26 '15 at 23:24

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.