Exercise 1103Combinatorics › Pigeonhole principleOlympiadAdded 3 Nov 2026

An odd number in a triple

#pigeonhole#parity#odd

Statement

Show that any set of $n+1$ integers from $\{1,\ldots,2n\}$ contains an odd integer and an even integer.

Hint

If all are odd, there are at most $n$ odds; if all are even, at most $n$ evens.

Show solutionHide solution

Odds. There are exactly $n$ odd numbers in $\{1,\ldots,2n\}$ .

Evens. Also $n$ even numbers.

Pigeonhole. With $n+1$ integers, if all were odd, we'd need $n+1$ distinct odd numbers but only $n$ exist. Same for evens.

Conclusion. The set contains both an odd and an even integer.