Exercise 1093Combinatorics › Pigeonhole principleL1Added 3 Nov 2026

Divisibility via pigeonhole

#pigeonhole#divisibility#subsets

Statement

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

Hint

Write each integer as $2^k\cdot m$ with $m$ odd. There are only $n$ odd numbers in $\{1,\ldots,2n\}$ .

Show solutionHide solution

Solution

Odd part. Every integer $x$ has a unique form $2^k\cdot m$ with $m$ odd.

Odd parts. There are $n$ possible odd parts $m\in\{1,3,\ldots,2n-1\}$ .

Pigeonhole. With $n+1$ integers and $n$ odd parts, two integers share the same odd part, say $2^a m$ and $2^b m$ with $a<b$ . Then $2^am\mid 2^bm$ .

Conclusion. One divides the other.

Divisibility via pigeonhole

Statement

Solution

More problems in Pigeonhole principle