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

  • $\begingroup$ The problem is worng because by exampls for $k=23456712$ doesnt exist any solution. $\endgroup$ – Masacroso Jul 26 '15 at 23:16
  • $\begingroup$ 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. $\endgroup$ – Marconius Jul 26 '15 at 23:24
  • $\begingroup$ @Masacroso The problem is about $\exists k$ (Existential quantification), not $\forall k \in \mathbb{N}$. I fail to see how the problem is wrong. $\endgroup$ – 吖奇说 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.

  • $\begingroup$ Thanks - that's a nice argument. I knew I was fairly close after determining all the 1-gaps exactly. $\endgroup$ – Marconius Jul 27 '15 at 0:19

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.