Proof by pigeon hole principle.

Question

I've been practicing discrete math recently and I'm stuck on this problem. Could someone help me with this, give me some hint or direction? I figured it was the pigeonhole principle, but I can't figure out the boxes. The content of the task is as follows:

Prove that among $15$ distinct natural numbers not exceeding 100, there are four numbers $a,\ b,\ c,\ d$ such that: $a + b = c + d$ or the numbers $a, b, c$ form an arithmetic sequence.

Answer 1

Proof by contradiction: If none of any adjacent or non-adjacent gaps are equal, then we arrange the 15 numbers $a_1, a_2, ..., a_{15}$ acsendingly, and start from the smallest gap between some adjacent pair, for example, $\delta_1=a_i-a_j$, so we have $\delta_1\ge 1$, then $\delta_2\ge 2, ..., \delta_{14}\ge14$, but the sum of the gaps:

$$\sum\ge 1+2+...+14=105$$

which is impossible.

=============== To make it clear============

Suppose you pick up 15 numbers and arrange them acendingly, and you get $1, 5, 11, 24, 25, ...$,

then we have $\delta_1=25-24=1\ge1, \delta_2=5-1=4\ge2, \delta_3=11-5=6\ge3, ...$

Answer 2

Write the numbers $a_1,a_2,\ldots, a_{15}$ in increasing order. Let $b_1, b_2, \ldots, b_{14}$ be the natural numbers satisfying $b_i = a_{i+1}-a_i$. Then by the fact that the $a_i$s are distinct and increasing in $i$, it follows that each $b_i$ is positive but not necessarily distinct [in fact we will establish via Case 2 that the the upper bound of $100$ on the $a_i$s implies that $b_i$s are necessarily not distinct]. Thus we break down into $2$ cases:

Case 1: The $b_i$s are not distinct; equivalently, there exist distinct $i_1,i_2$ such that the equation $b_{i_1}=b_{i_2}$ holds. Assume without loss of generality $i_2>i_1$. Then the equation $b_{i_1}=b_{i_2}$ gives the equation $b_{i_1}=a_{i_1+1}-a_i = a_{i_2+1}-a_{i_2}=b_{i_2}$. If the equation $i_2=i_1+1$ holds, then the equation $a_{i_1+1}-a_i = a_{i_2+1}-a_{i_2}$ implies the equation $a_{i_1+1}-a_i = a_{i_1+2}-a_{i_1+1}$ so $a_{i_1},a_{i_1+1},a_{i_1+2}$ form an arithmetic sequence. Otherwise the equation $a_{i_1+1}-a_i = a_{i_2+1}-a_{i_2}$ imply the equation $a_{i_2+1}+a_i=a_{i_1+1}+a_{i_2}$, with $i_1,i_1+1,i_2,i_2+1$ distinct.

Case 2: There does not exist such integers $i_1,i_2$ as in Case 1; equivalently, the $b_i$'s are distinct. Then as the $b_i$s are each distinct positive integers, it follows that $a_{15}$ satisfies the following: $$a_{15} \ = \ a_1+\sum_{i=1}^{14} b_i$$ $$\ge \ a_1 + \sum_{i=1}^{14} i \ > \ 1+ 100.$$

You can finish from here, and see that Case 2 cannot be.