Many odd numbers

#pigeonhole#odd#sums

Statement

Show that among any $n+1$ integers chosen from $\{1,\ldots,2n\}$ , at least $\lceil (n+1)/2\rceil$ have the same parity.

Hint

$2$ parities, $n+1$ integers.

Show solutionHide solution

Pigeonhole. $n+1$ integers split into $2$ parity classes: one has $\ge\lceil(n+1)/2\rceil$ .

Conclusion. At least $\lceil (n+1)/2\rceil$ have the same parity.