I hope somebody can help me with this question.
Let $A \subseteq \{1,2,...,n\}$ be a $k$-element subset with $k > 2\sqrt{n} + 1$. Show that there exist two distinct pairs $(a_1,b_1), (a_2,b_2) \in A\times A$ with $a_1 < b_2$ and $a_2 < b_2$ such that $a_1 + b_1 = a_2 + b_2$.
I think applying the pigeonhole principle might be one step to the solution. But, I can't figure out where to apply it. I tried to look at all possibilities to choose such pairs from $\{1,2,...,n\}$ and then to apply the principle. I could not figure out how. Help or some hints would be much appreciated!
The set $\{1,2,\dots, n\}$ has $2n-3$ possibles sums of differents terms (all numbers from 3 to 2n-1 are possible here), so, in $A$, you have at most $2n-3$ sums.
In the other hand, you have $\binom{k}{2}=\frac{k(k-1)}{2}>\frac{(2\sqrt{n}+1)(2\sqrt{n})}{2}=2n+\sqrt{n}$. This says that you have at least $2n+\sqrt{n}>2n-3$ forms to choose two terms of $A$ to sum, so, by the pigeonhole principle, there will be at least two pairs of different numbers in $A$ with the same sum.