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$

Question

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.

Answer 1

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

Answer 2

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

Answer 3

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