Exercise 1624Combinatorics › Counting principlesOlympiadAdded 3 Nov 2026

Pigeonhole with 100 numbers

#pigeonhole#subsets#olympiad

Statement

Show that among any $n+1$ integers from $\{1,\ldots,2n\}$ , one divides another.

Hint

Write each number as $2^k\cdot m$ with $m$ odd. There are only $n$ odd numbers $\le 2n$ .

Show solutionHide solution

Setup. Every integer $x\le2n$ has a unique form $x=2^k\cdot m$ with $m$ odd, $1\le m\le2n$ .

Odd parts. There are $n$ odd integers in $\{1,\ldots,2n\}$ .

Pigeonhole. Among $n+1$ chosen integers, two have the same odd part $m$ : say $2^a m$ and $2^b m$ with $a<b$ . Then $2^am\mid2^bm$ .

Conclusion. One divides another.