Property of natural numbers using pigeonhole principle

Question

Let $n$ be a natural number larger than $3$. Let $S$ be a subset of $\{1,2,\ldots, n\}$ such that the number of elements of $S$ is more than $n/2+1$. Show that there exist distinct elements $x, y, z$ such that $x=y+z$ in $S$.

Answer 1

Let $x_0 \in S$ be the minimal element of $S$. Then the set $S - x_0$ is contained in $\{0,...,n-1\}$ and has $|S| - 1$ elements in the range $\{1,...,n\}$ (we eliminate the $0$). Now, we have two sets $S$ and $S- x_0$ in $\{1,...,n\}$ and $$ |S| + |S - x_0| = |S| + |S| - 1 \geq 2(1+n/2) - 1 = n + 1. $$ By pigeonhole principle $S$ and $S - x_0$ have to intersect, and let $y\in S \cap (S - x_0)$ be in the intersection. Hence $$ y = z - x_0 , \text{ for some } z \in S, $$ from where $$ y + x_0 = z. $$

Answer 2

NOTE I believe this solution to be wrong as I assumed the differences to be pairwise distinct.

Imagine you had the bag of numbers, and you put the first two out. You have to keep selecting numbers so that no three satisfy $x + y = z$. If there are $k$ numbers selected already, you can't select any of their differences (how many differences are there? k choose 2).

So first you have n - (1 choose 2) choices, then you have that - (2 choose 2 choices), then that minus (3 choose 2) choices... when do you run out of choices? Since these numbers are finite, pigeonhole would apply.

At least the way I did it, I showed that $n - \sum_{i}^{\frac{n}{2}} \tbinom{i}{2} < 0$ for $n \ge 3$, which would show by the pigeonhole principle that there must be some such $x,y,z$.

Answer 3

Let $S=\{a_1, \ldots, a_k\}$ where $k\geq n/2+1$, and assume that whenever $x, y, z\in S$, then $x+y\neq z$.

Say $a_k=\max S$. Then none of the numbers $$a_k-a_1, a_k-a_2, \ldots, a_k-a_{k-1}$$ are in $S$. Further, these numbers are pairwise distinct and all belong in $\{1, \ldots, n\}$.

So we have have a disjoint union $$S\cup\{a_k-a_i:\ 1\leq i< k\}\subseteq \{1, \ldots, n\}$$ But then $n\geq |S|+ k-1=2k-1\geq n+1$, which is a contradiction.