Combinatorics proof (any set of 16 numbers from 1 to 100 contains repeated sums)

Suppose that $A$ is a set of 16 distinct natural numbers and that $1\leq p\leq100$ for every $p$ in $A $.

Prove that $A$ contains 4 different numbers $a$, $b$, $c$, and $d$, such that $a+b=c+d$.

This is number 17 of the introductory problems section in the book 102 Combinatorial Problems from the training of the USA IMO team by Titu Andreescu and Zuming Feng.

Here is a paraphrase of their solution.

There are ${16\choose 2}=120$ pairs of numbers from $A$. Since the absolute differences range from 1 to 99, there must be two different pairs $\{a,c\}$ and $\{d,b\}$ with $a-c=d-b$ and hence $a+b=c+d$.

The problem is that $\{a,b,c,d\}$ may not be distinct. Well, what could go wrong? We may end up with pairs like $\{7,6\}$ and $\{6,5\}$. In this case, we may call the number 6 "bad". Generally, we call $a\in A$ a bad number if there exist $a_1<a<a_2\in A$ with $a_2-a=a-a_1$.

Note that if $a$ is bad for two different pairs of pairs, then we have a solution. That is, if $a_1<a<a_2\in A$ so that $a_2-a=a-a_1$ and $a_3<a<a_4\in A$ so that $a_4-a=a-a_3$, then we have $a_1+a_2=a_3+a_4$. You can check that $a_1,a_2,a_3,a_4$ really are distinct in this case.

So the only real problem are pairs of numbers in $A$ whose midpoint $a$ also belongs to $A$, such that no other pair has the same midpoint. There are at most 16 such troublesome pairs, so there are $120-16=104$ pairs left. Applying the pigeonhole principle to this reduced set gives the solution.

Note: This solution is for the problem as originally posed, without the requirement that $a,b,c$, and $d$ be distinct. That requirement makes it significantly harder, and I’ll have to think about it a bit more if I have time.

(I’m assuming that you mean that if $p\in A$, then $1\le p\le 100$.) Here’s an extended hint.

Let $D=\{|a-b|:a,b\in A\text{ and }a\ne b\}$, the set of pair differences.

1. How many pairs $\{a,b\}\subseteq A$ are there with $a\ne b$?

2. If $1\le a\le 100$ for every $a\in A$, what numbers could be in $D$? How many such numbers are there?

3. Use the pigeonhole principle to find $a,b,c,d\in A$ such that $a-c=d-b$.

a computer search shows that there is a set of 13 numbers between 1 and 100 with no four satisfying a+b=c+d: $$(1, 2, 12, 18, 22, 35, 43, 58, 61, 73, 80, 85, 87)$$ (and 87 is the lowest maximum that is achievable), but that the lowest possible maximum for a set of 14 positive integers with no a+b=c+d is 106: $$(1, 2, 7, 15, 28, 45, 55, 67, 70, 86, 95, 102, 104, 106)$$ so in fact, any set of 14 integers in the range 1 to 100 has repeated sums. (I would have added this as a comment, rather than an answer, but I am new to math.stackexchange, so haven't accumulated the requisite reputation to comment)