Problem
NT-B1-M01-P021 A Pair with Divisibility
#21
★★★★☆ Level 4 of 5
From the set \(\{1,2,\ldots,2n\}\), \(n+1\) numbers are chosen. Prove that among the chosen numbers there are two such that one divides the other.
Write each number as \(2^tq\), where \(q\) is odd.
Every number from \(1\) to \(2n\) is uniquely written as \(2^tq\), where \(q\) is odd. There are at most \(n\) possible odd values \(q\): \(1,3,5,\ldots,2n-1\). Among \(n+1\) chosen numbers, by the pigeonhole principle two have the same odd part \(q\): \(2^aq\) and \(2^bq\), with \(a
The problem combines prime factorisation with the pigeonhole principle.