Let $A_n=\{1,2,3,...,2n\}$. Show that any $(n+2)\text{-}$element subset of $A_n$ contains two integers whose sum is in that subset.
Any idea how to choose the pigeonholes please ?
Asked
Active
Viewed 35 times
0
-
while the then number of pairs of an $n+2$ subset is ${n+2 \choose 2} = \frac {(n+2)(n+1)}2$ and then possible values of the sums can be as low as $1+2 =3$ to as high as $2n + (2n-1)= 4n-2$. so there are $4n-4$ possible values. – fleablood Sep 08 '20 at 17:34
-
isn't it $4n-1$ ? But how can i use that – PortoKranto Sep 08 '20 at 18:07
-
2Let $m$ be the largest element of the $(n+2)$-element subset $S \subset A_n$. – Daniel Fischer Sep 08 '20 at 18:24