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