Разделы 
Дополнительно
Задача по математике - 90
2014-06-07 
Даны 20 натуральных чисел $a_{1} < a_{2} < \cdots a_{20}$, не превосходящих 70. Доказать, что среди разностей $a_{j} – a_{k} (j > k)$ найдутся хотя бы 4 одинаковых числа.
Решение:
Предположим, что утверждение задачи неверно. Тогда среди 19 натуральных чисел
$a_{20}-a_{19}, a_{19}-a_{18} , \cdots , a_{2}-a_{1}$
нет 4 одинаковых чисел. Поэтому среди них ни одно из чисел 1, 2, 3, 4, 5, 6 не может встретиться более 3 раз. Следовательно, хотя бы одно из этих 19 чисел больше 6 (иначе чисел, не превосходящих 6, было бы более 18), хотя бы 3 из оставшихся 18 чисел больше 5, хотя бы 3 из оставшихся 15 чисел больше 4 и т. д. Поэтому их сумма
$( a_{20}-a_{19}) + ( a_{19}-a_{18}) + \cdots + ( a_{2}-a_{1}) \geq $
$ \geq 7 + (6+6+6) + (5+5+5) + \cdots + (1+1+1) = 70$
не может быть равна числу $a_{20} – a_{1} < 70 - 1 = 69$. Полученное противоречие доказывает требуемое утверждение.
Даны 20 натуральных чисел $a_{1} < a_{2} < \cdots a_{20}$, не превосходящих 70. Доказать, что среди разностей $a_{j} – a_{k} (j > k)$ найдутся хотя бы 4 одинаковых числа.
Решение:
Предположим, что утверждение задачи неверно. Тогда среди 19 натуральных чисел
$a_{20}-a_{19}, a_{19}-a_{18} , \cdots , a_{2}-a_{1}$
нет 4 одинаковых чисел. Поэтому среди них ни одно из чисел 1, 2, 3, 4, 5, 6 не может встретиться более 3 раз. Следовательно, хотя бы одно из этих 19 чисел больше 6 (иначе чисел, не превосходящих 6, было бы более 18), хотя бы 3 из оставшихся 18 чисел больше 5, хотя бы 3 из оставшихся 15 чисел больше 4 и т. д. Поэтому их сумма
$( a_{20}-a_{19}) + ( a_{19}-a_{18}) + \cdots + ( a_{2}-a_{1}) \geq $
$ \geq 7 + (6+6+6) + (5+5+5) + \cdots + (1+1+1) = 70$
не может быть равна числу $a_{20} – a_{1} < 70 - 1 = 69$. Полученное противоречие доказывает требуемое утверждение.
