0
$\begingroup$

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

$\endgroup$

closed as off-topic by Carl Mummert, José Carlos Santos, B. Mehta, Saad, Xander Henderson May 20 '18 at 0:48

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Carl Mummert, José Carlos Santos, B. Mehta, Saad, Xander Henderson
If this question can be reworded to fit the rules in the help center, please edit the question.

1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thank you. But why y,x_0, z are distinct? $\endgroup$ – str May 12 '18 at 14:13
  • 1
    $\begingroup$ since we fixed $x_0$ as the smallest element of $S$, it follows that $x_0< y, z$ . And since $x_0>0$ we get that $y>z$ so all are distinct. $\endgroup$ – Hayk May 12 '18 at 14:18
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Considering this solution has shown up twice i'm wondering if mine (below) is incorrect? $\endgroup$ – William May 12 '18 at 6:00
  • $\begingroup$ It seems that when you say "k choose 2" differences, you are implicitly assuming that these differences are pairwise distinct. That may not be so. $\endgroup$ – caffeinemachine May 12 '18 at 6:06
0
$\begingroup$

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

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.