Задача 60299

Темы:    [ Разбиения на пары и группы; биекции ] [ Принцип Дирихле (прочее) ] [ Делимость чисел. Общие свойства ]

Сложность: 4- Классы: 8,9,10

Условие

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

Решение

Рассмотрим наибольшие нечётные делители выбранных чисел. У чисел от 1 до 2n есть ровно n различных наибольших нечётных делителей (числа 1, 3, ...,  2n – 1).  Итак, два из выбранных чисел имеют одинаковые наибольшие нечётные делители. Это означает, что два выбранных числа отличаются только тем, что множитель 2 входит в них в разных степенях. Большее из них делится на меньшее.

Источники и прецеденты использования

книга
Автор	Алфутова Н.Б., Устинов А.В.
Год издания	2002
Название	Алгебра и теория чисел
Издательство	МЦНМО
Издание	1
глава
Номер	1
Название	Метод математической индукции
Тема	Индукция
параграф
Номер	2
Название	Тождества, неравенства и делимость
Тема	Индукция (прочее)
задача
Номер	01.026