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.

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

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

  • $\begingroup$ How do you know the values of $b_k$ are all distinct? Can't two successive terms $b_k,b_{k-1}$ be equal? $\endgroup$ – 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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.