# Given a set $A \subseteq \{1,2,3…150\}$ such that $|A|=25$. Prove there are $a,b,c,d\in A$ satisfying $a+b=c+d$

Given a set $A \subseteq \{1,2,3...150\}$ such that $|A|=25$. Prove using Pigeonhole Principle there are 4 different elements $a,b,c,d\in A$ satisfying $a+b=c+d$

A direction or hint would be appreciated.

• How many pairs of elements can you pick to make $a+b$? – Countingstuff Dec 31 '17 at 10:12
• Related problem. The argument given in this answer can be applied to your question. – J.-E. Pin Dec 31 '17 at 10:17

## 3 Answers

The number of pairs of elements in a set of $25$ elements is $\frac{25\cdot24}{2}=300$

If you assume all of those sums (pairwise) are different, then they have to be in $\{3 \dots 299\}$ as $A \subset \{1,2\dots 150\}$. However, the set $\{3 \dots 299\}$ contains $297$ elements and hence yo get a contradiction with the assumption that all the $300$ sums are different

Note that the statement is equivalent to that there exists $a,b,c,d\in A$ such that $a-c=d-b>0$.

Sort the elements of $A$: $a_1<a_2<\ldots <a_{25}$. Consider the sequence $$b_k=a_{k+1}-a_k,\;\;1\le k\le 24$$

If the statement is false, the elements of this sequence are pairwise different, positive integers, and hence: $$a_{25}-a_1=\sum_{k=1}^{24}b_k\ge1+2+\cdots+24=300$$

Remark: With this argument, you can prove it even for $|A|=17$.

• How do you know the values of $b_k$ are all distinct? Can't two successive terms $b_k,b_{k-1}$ be equal? – quasi Dec 31 '17 at 11:55

There are $\binom{25}{2}=300$ different pairs in the chosen numbers. The sums of the elements can range from $3$ to $299$, thus can't take $300$ different values, and we conclude by the pigeon hole principle

• Same as @asdf’s Answer... – Rohan Dec 31 '17 at 10:23
• The sums can range from 3 to 299. Can you explain the conclusion? – Moshe King Dec 31 '17 at 10:33
• There are less than 300 integer values between 3 and 299 – Taumen Dec 31 '17 at 10:35