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

Проект МЦНМО
при участии
школы 57
Задача 66151
Темы:    [ Доказательство от противного ]
[ Упорядочивание по возрастанию (убыванию) ]
Сложность: 3+
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

На доске написаны  n > 3  различных натуральных чисел, меньших чем  (n – 1)!.  Для каждой пары этих чисел Серёжа поделил большее на меньшее с остатком и записал в тетрадку полученное неполное частное (так, если бы он делил 100 на 7, то он бы получил  100 = 14·7 + 2  и записал бы в тетрадку число 14). Докажите, что среди чисел в тетрадке найдутся два равных.


Решение

Предположим противное. Пусть a1, a2, ..., an – числа на доске в порядке возрастания, а qi – неполное частное от деления ai+1 на ai  (i = 1, 2, ...,
n – 1);  тогда  ai+1qiai.  Так как все qi различны, то  q1q2...qn–1 ≥ (n – 1)!.  Значит,  an/a1 = an/an–1·an–1/an–2·...·a2/a1q1q2...qn–1 ≥ (n – 1)!.  Но это невозможно, поскольку a1 и an – натуральные числа, меньшие  (n – 1)!.

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

олимпиада
Название Всероссийская олимпиада по математике
год
Вариант 2016/2017
этап
Вариант 5
класс
Класс 9
задача
Номер 9.5

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

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