How to Solve this Using the Pigeonhole Principle?

Question

Consider the set $S$ of numbers $1, 2, 3 ... 18, 19$. Prove that any subset of $S$ consisting of $11$ elements will have at least one triple of numbers $(a, b, c)$ so that $a+b=c$.

Answer 1

Hint:

We have to choose $11$ numbers from $19$ numbers.

If we start choosing numbers, assume that we have chosen $10$ numbers such that no such triple is obtained. Now, argue that any $11^{th}$ chosen number will be either the sum of any $2$ numbers $(c=a+b$) or absolute difference of any two ($c-b=a$)

Edit: You can also argue in this way: for every $a$ and $b$ chosen, we have to exclude $c=a+b$ from collection of numbers we can select from, otherwise we get a triple. This $c$ will only be excluded if $a+b \leq 19$ otherwise $a+b$ is not in our set. Show that we can get atmost $10$ such numbers (eg. $10, 11, 12, ..., 19)$ and the collection we can choose from is empty after that.

Answer 2

Let $M=\{a_1<a_2<...<a_{11}\}$ and let $M' = \{(x,y);\;x,y\in M,\;x<y \}$.

Let $f:M'\to \mathbb{N}$ be such that $f(x,y) =y-x$.

Since $a_{11}-a_1>a_{11}-a_2>...>a_{11}-a_{10}$ we have $|f(M')|\geq 10$.

Now suppose $f(M')\cap M = \emptyset$. Then by PIE we have:

$$ 19\geq |f(M')\cup M| = |f(M')|+|M| \geq 10+11 $$

A contradiction. Thus the conclusion.

Answer 3

Consider the largest element $n$ of the $11$ selected. Then the numbers below this sum to this value in pairs $(1,n-1), (2,n-2)$ etc. with a possible single value of $n/2$ left over without a partner. These form $\lfloor n/2\rfloor$ groups.

In this case the maximum value for $n$ is $19$ and thus there are no more than $\lfloor 19/2\rfloor = 9$ summing groups (pairs). By the pigeonhole principle we must choose two from one of these groups, which form a pair that sums to the maximum value.