Задача
NT-B1-M01-P021 Пара с делимостью
#21
★★★★☆ Уровень 4 из 5
Из множества \(\{1,2,\ldots,2n\}\) выбрали \(n+1\) чисел. Докажите, что среди выбранных есть два числа, одно из которых делит другое.
Представьте каждое число в виде \(2^tq\), где \(q\) нечетно.
Каждое число от \(1\) до \(2n\) единственно представляется в виде \(2^tq\), где \(q\) нечетно. Возможных нечетных \(q\) не больше \(n\): это \(1,3,5,\ldots,2n-1\). Среди \(n+1\) выбранных чисел по принципу Дирихле найдутся два с одинаковой нечетной частью \(q\): \(2^aq\) и \(2^bq\), где пусть \(a
Задача соединяет разложение на простые множители и принцип Дирихле.