Exercise 1815Combinatorics › Pigeonhole principleOlympiadAdded 3 Nov 2026

Sum of two distinct elements

#pigeonhole#sum#distinct

Statement

Show that among any $n+1$ integers from $\{1,\ldots,2n\}$ , there exist two whose sum is odd.

Hint

If no two sum to odd, all integers have the same parity.

Show solutionHide solution

Odd sum condition. Two integers have odd sum iff one is odd and one is even.

Contrapositive. If no two sum to odd, then all integers have the same parity: all odd, or all even.

Count. There are only $n$ odd numbers and $n$ even numbers in $\{1,\ldots,2n\}$ . So we cannot choose $n+1$ all of the same parity.

Conclusion. Among $n+1$ integers, at least one is odd and one is even, giving an odd sum.