ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 60299
Темы:    [ Разбиения на пары и группы; биекции ]
[ Принцип Дирихле (прочее) ]
[ Делимость чисел. Общие свойства ]
Сложность: 4-
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

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


Решение

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

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

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

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .