Prove that any 11 numbers chosen from 1 to 20 contain a pair where one divides the other, and show the statement fails for 10.

Prove that any 11 numbers chosen from 1 to 20 contain a pair where one divides the other, and show the statement fails for 10.

Approach: Write every integer as an odd number times a power of two and group by the odd part, then count how many groups exist against how many numbers are chosen.

Write each chosen number as 2^a * m with m odd. There are exactly 10 odd values of m available in the range 1 to 20, namely 1, 3, 5, ..., 19, so choosing 11 numbers forces two of them to share an odd part by the pigeonhole principle. If those two are 2^a m and 2^b m with a < b, the first divides the second, which proves the claim. The same grouping shows why 10 is not enough: the set 11, 12, 13, ..., 20 has one number for each odd part and no divisibility chain inside it, since any proper multiple of a number that is at least 11 is at least 22 and falls outside the range. That extremal construction shows 11 is the smallest count that forces the conclusion, and the general statement is that any n+1 numbers from 1 to 2n contain such a pair.

Follow-up: How many numbers must you choose from 1 to 30 to force three of them in a divisibility chain?

Key concepts: pigeonhole principle, odd part, divisibility chain, extremal construction.