СДАМ ГИА: РЕШУ ЕГЭ
Образовательный портал для подготовки к экзаменам
Математика профильного уровня
≡ математика
сайты - меню - вход - новости


Задания
Версия для печати и копирования в MS Word
Задания Д16 C7 № 505941

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

Решение.

Обозначим наши числа Причем, пусть для определенности, они стоят в порядке возрастания:

Рассмотрим теперь набор чисел таких, что (то есть, увеличим все данные числа на единицу). Если у этих двух наборов есть хотя бы 4 общих числа, то задача решена, поскольку найдутся 4 разности, равные единице. Пусть нет, тогда в наборе по крайней мере 17 новых чисел, не содержащихся в Тогда рассмотрим набор чисел таких, что Если в наборе есть хотя бы четыре общих числа с набором или 4 числа общих с набором то задаче решена. Пусть нет, тогда в наборе по крайней мере 14 новых чисел, которых нет в наборах и Аналогично построим наборы (каждый раз увеличивая все числа предыдущего набора на единицу). Ясно, что самое большое из всех рассмотренных чисел не больше, чем то есть не больше 75. В тоже время в совокупности всех наборов не менее, чем 20 + 17 + 14 + 11 + 8 + 5 + 2 = 77 чисел. Получается противоречие, так как все числа натуральные. Что и требовалось доказать.

Источник: А. Ларин: Тре­ни­ро­воч­ный ва­ри­ант № 16.
Раздел кодификатора ФИПИ/Решу ЕГЭ: Числа и их свойства