Задача 35466

Темы:    [ Последовательности (прочее) ] [ Доказательство от противного ]

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

Условие

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

Подсказка

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

Решение

Обозначим числа через a₁, a₂, ... , a₂₀ в порядке возрастания, таким образом a₁<a₂<...<a₂₀. Допустим, что условие задачи не выполняется. Тогда среди 19 разностей d₁=a₂-a₁, d₂=a₃-a₂, ... , d₁₉=a₂₀-a₁₉ не больше трех разностей принимают значение 1, не больше трех разностей принимают значение 2, и т.д. Отсюда можно сделать вывод о том, что сумма всех 19 разностей d₁+d₂+...+d₁₉ = a₂₀-a₁ не меньше, чем (1+1+1)+(2+2+2)+(3+3+3)+(4+4+4)+(5+5+5)+(6+6+6)+7=70. Однако разность a₂₀-a₁, очевидно, меньше 70, так как числа a₂₀ и a₁ - натуральные, меньшие 70. Полученное противоречие доказывает справедливость утверждения задачи.

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

web-сайт

задача