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