How to Solve this Using the Pigeonhole Principle? 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$.
 A: 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. 
A: 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.
A: 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.
