Properties of numbers picked from sets.

146 Views Asked by At

So this is a two-part, pigeonhole principle exercise.

The first part:

Prove that if we choose n+2 numbers from the following set:

{1,2,3,...,2n-1}

then the sum of two of those numbers will be equal to a third number we chose.

The second part:

Find one subset of [2n-1] which contains n+1 elements in which there is no sum of two numbers equal to a third number of the subset.

1

There are 1 best solutions below

0
On

The first part: It suffices to prove that we can choose at most $n+1$ elements in set $B= \{ 1,2, \ldots , n \}$ so that no sum of two numbers from $n+1$ is equal to one of $n+1$ numbers.

Indeed, let $t$ is maximum element in $B$ Then at most one of $\{ i,t-i \}$ is element of $B$ where $i=1,2,...,\lfloor \frac{t}{2} \rfloor$. And since $t$ is maximum element, we get that $$|B| \leq \lfloor \frac{t}{2} \rfloor +1 \leq \lfloor \frac{2n+1}{2} \rfloor +1 =n+1.$$

The second part: We can't always construct such set $B$ for all $n$. From the above proof, you can notice that we only deal with the condition where $a+b=2n+1$ where $2n+1 \in B$, but not for others $x \in B$. The first part only gives us a weak upper bound of $|B|$ of such set $B$.

Not related: This set $B$ is called sum-free set. Erdos proved that for any $n$ positive integers, we can choose at least $\frac 13 n$ numbers to create a sum-free subset.