Известная задача про {1,2,...,2n}

[qwert129]

.:

Среди чисел $1,2,3,...,2n$ выбрано $n+1$ чисел. Докажите, что среди этих чисел есть два, одно из которых делится на другое.


Я знаю всем известное доказательство. Просьба доказать эту задачу по другому методу . Нужно доказать без представления $2^km$.попробовал по индукции, не смог.

[Gagarin1968]

qwert129 в сообщении #1632105 писал(а):

Я знаю всем известное доказательство

Это какое же? Я знаю как минимум два.
У $n+1$ выбранных чисел рассмотрите их наибольшие нечётные делители. И примените принцип Дирихле.

[qwert129]

Да, это мне известно. А какое второе?

[TOTAL]

"Другое" доказательство, скорее всего, будет просто замаскированным тем же самым.

Вот, например. Меньшее из чисел заменим на удвоенное. Если в наборе получили два одинаковых числа, то утверждение доказано. А если всё ещё нет одинаковых чисел, то снова удвоим меньшее. И т.д. Очевидно, за конечное число шагов в наборе появятся два одинаковых числа, что будет означать, что в исходном наборе два числа отличались множителем вида $2^k$