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

Solution 1:

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\}$

Solution 2:

Just an idea.

Divide the set $T=\{a_1<a_2<...<a_{69}\}$ in to two parts. With first $k$ numbers (set $A$) we make all sums (set $A'$) and with the rest of the numbers (set $B$) we make positive differences (set $B'$).

Say $A= \{a_1,a_2,...a_k\}$ (so $a_k\leq 100-(69-k) = 31+k$) and $$A' = \{a_i+a_j|\, i\ne j; i,j\leq k\}$$

Since we have: $$a_1+a_2<a_1+a_3<...<a_1+a_k<a_2+a_k<...<a_{k-1}+a_k$$

then $|A'|\geq 2k-3$ and $A'\subseteq \{3,4,...61+2k\}$

Say $B= \{a_{k+1},a_{k+2},...a_{69}\}$ (so $a_{k+1}\geq k$) and $$B' = \{a_i-a_j|\, i> j\geq k+1\}$$

Since we have: $$a_{69}-a_{68}<a_{69}-a_{67}<...<a_{69}-a_{k+1}$$

then $|B'|\geq 68-k$ and $B'\subseteq \{1,2,3,4,...99-k\}$

Now we have to chose apropriate $k$ such that $|A'\cap B'|\geq 1$.

Say there is no such $k$. Then $|A'\cap B'| =0$ and thus: $$ |A'\cup B'| = |A'|+|B'|\geq 65+k$$

and $|A'\cup B'|\leq \max\{99-k,61+2k\}$. ...