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

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

Tags:

Combinatorics

Pigeonhole Principle

Related

Prove that $\sum_{l=0}^{n} \binom{n}{l}^2 (x+y)^{2l} (x-y)^{2(n-l)} = \sum_{l=0}^{n} \binom{2l}{l} \binom{2(n-l)}{n-l} x^{2l}y^{2(n-l)}$ Is there a *simple* example showing that uncorrelated random variables need not be independent? System with a Lyapunov function over $\mathbb{R}^n$ but not globally asymptotically stable Algebraic Geometry: What am I doing wrong? Prove that every compact metric space is separable Question on Iwasawa Theory In what sense is propositional logic "zeroth-order logic?" Find the height of a bar, given the lengths of shadows cast by it and another bar Find all $f : \mathbb{N} \to \mathbb{N}$ such that $f(a) + f(b) \mid a+b, \ \forall \ a, b \in \mathbb{N}$ I think I have discovered a proof for the irrationality of $\sqrt{2}$, but I'm not sure Prove that if fifteen bishops were placed on a chessboard, then at least two of them attack each other. Showing that $\lvert H K\rvert = \frac{| H\| K|}{ |H\cap K|}$

Recent Posts