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

-
Please clarify your question. What is $p$? Are the numbers $a,b,c,d$ supposed to belong to $A$? – Michael Joyce Aug 25 '12 at 20:43
It would be nice to see some motivation for this, and some evidence that you have put some thought into it yourself. – Gerry Myerson Aug 25 '12 at 23:39
I mean, why have you worked on this problem, and not some other? Did you make it up? Did you find it somewhere? Is it part of a homework assignment? Does some other result depend on it? There is no shortage of mathematical problems a person could pose; why this one? – Gerry Myerson Aug 26 '12 at 0:39
I went to a mathematical olympiad this morning. There where three problems. I solved two out of three, I couldnt solve this one. I want to know how to solve it because I feel like it may be useful in another olympiad – Carry on Smiling Aug 26 '12 at 0:50
Good! That's what I like to see.... – Gerry Myerson Aug 26 '12 at 2:03

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.

-
how do you know that there are only 16 of those troublesome pairs and why is it a problem that $a$ belongs to $A$ – Carry on Smiling Aug 26 '12 at 1:54
There can be at most one "troublesome" pair for every $a\in A$. – Byron Schmuland Aug 26 '12 at 2:02
It's a problem if $a$ belongs to $A$ because, as in the example, you'd have $7-6=6-5$ and you'd wind up with $7+5=6+6$ and you wouldn't have distinct $a,b,c,d$. – Gerry Myerson Aug 26 '12 at 2:05

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

-
@Khromonkey: No, I’m asking what the possible values of $|a-b|$ are. – Brian M. Scott Aug 25 '12 at 21:38
@Khromonkey: It’s conceivable that all of the duplicated distances occur in triples like $4,11,18$ (for distance $7$), in which case you don’t get four distinct numbers. Somehow that possibility has to excluded. – Brian M. Scott Aug 25 '12 at 21:42