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

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

Условие

Даны 20 различных натуральных чисел, меньших 70. Докажите, что среди их попарных разностей найдутся четыре одинаковых.

Подсказка

Расположите числа в порядке возрастания и предположите противное - среди разностей между последовательными числами нет четырех различных.

Решение

Обозначим числа через a1, a2, ... , a20 в порядке возрастания, таким образом a1<a2<...<a20. Допустим, что условие задачи не выполняется. Тогда среди 19 разностей d1=a2-a1, d2=a3-a2, ... , d19=a20-a19 не больше трех разностей принимают значение 1, не больше трех разностей принимают значение 2, и т.д. Отсюда можно сделать вывод о том, что сумма всех 19 разностей d1+d2+...+d19 = a20-a1 не меньше, чем (1+1+1)+(2+2+2)+(3+3+3)+(4+4+4)+(5+5+5)+(6+6+6)+7=70. Однако разность a20-a1, очевидно, меньше 70, так как числа a20 и a1 - натуральные, меньшие 70. Полученное противоречие доказывает справедливость утверждения задачи.

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

web-сайт
задача

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

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