[Math] Let $T$ be any subset of $\{1,2,3,…,100\}$ with $69$ elements. Prove that one can find four distinct integers such that $a+b+c=d$.

combinatoricspigeonhole-principle

I have a question on combinatorics, related to the pigeonhole principle:

Consider the set $S= \{1,2,3,…,100\}$. Let $T$ be any subset of $S$ with $69$ elements. Then prove that one can find four distinct integers $a,b,c,d$ from $T$ such that $a+b+c=d$. Is it possible for subsets of size $68$?

Best Answer

Well, I just realized that I’ve seen this problem days ago... the solution goes like this:

Let the numbers in $T$ be $1\le a_1<a_2<...<a_{69}\le 100$. Clearly, $a_1\le 32$.

Now, consider the sequences $$b_n:=a_n+a_1, 3\le n\le 69$$ $$c_n:=a_n-a_2, 3\le n\le 69 $$

Apparently, $1 \le b_i,c_i\le 132$. Since the two sequences have totally $134$ elements (greater than $132$), there is some number in both sequences, i.e. $\exists i,j\in \{3,4,\ldots,69\}$ such that $a_i+a_1=a_j-a_2$. Then $a_1+a_2+a_i=a_j$, as desired.

The second question has an answer “false”. Counterexample is the set $\{33,34,\ldots,100\}$

Related Question