Pigeonhole Principle for n+1 distinct integers

Question

Given a set of $n + 1$ distinct integers, each smaller than $2n$, prove that one can find three numbers among them, such that one of them is equal to the sum of the other two.

How would I use P.P. for this? Thanks.

Answer 1

Hint: Prove that the largest one is a sum of two smaller ones.

More precisely, you do it by contradiction: If the largest one is $n+k$ (where $1\leq k\leq n-1$), then for each one of the remaining numbers $p$ in your set, the number $n+k-p$ should not be in your set. But this gives a partition of $\left\{1,\ldots,n+k-1\right\}$ into two disjoint sets with $n$ elements each.

Answer 2

Set your integers as $K_1$, $K_2$, $K_3$, ... $K_{n+1}$. Then subtract $K_1$ from $K_{n+1}$, $K_2$ from $K_{n+1}$, and so on until you subtract $K_n$ from $K_{n+1}$. You will then have n distinct integers, all less than $2n$ (because you are subtracting a positive quantity from a quantity that is already less than $2n$). Since you can only have $2n-1$ distinct integers and when you add $n+1$ integers with $n$ integers you get $2n+1$ total integers, which means that there must be at least two repetitions.