Из чисел 1, 2, 3, ..., 2016 выбраны k чисел. При каком наименьшем k среди выбранных чисел обязательно найдутся два числа, разность которых больше 672 и меньше 1344?
Решение. Пусть Тогда и Предположим, что можно так выбрать числа, что среди них не найдется нужной пары чисел. Пусть m — наименьшее из выбранных чисел. Тогда числа не выбраны. Удалим их и число m из набора а оставшееся множество обозначим через E. Рассмотрим пары чисел
Их штук. Заметим, что объединение левых и правых частей этих пар дает множество E. Тогда любое выбранное число совпадает с левой или правой частью одной из пар. По предположению таких чисел ровно поэтому найдутся два из них, например a и b, принадлежащие одной паре. Тогда их разность равна или Значит, a и b удовлетворяют условию задачи, что невозможно.
Если выбраны числа 1, 2, 3, ..., 673, то нужные два числа найти не удастся.
PDF-версии: горизонтальная · вертикальная · крупный шрифт · с большим полем
Тогда 
и 
Предположим, что можно так выбрать 
числа, что среди них не найдется нужной пары чисел. Пусть m — наименьшее из выбранных чисел. Тогда числа 
не выбраны. Удалим их и число m из набора 
а оставшееся множество обозначим через E. Рассмотрим пары чисел 
штук. Заметим, что объединение левых и правых частей этих пар дает множество E. Тогда любое выбранное число совпадает с левой или правой частью одной из пар. По предположению таких чисел ровно 
поэтому найдутся два из них, например a и b, принадлежащие одной паре. Тогда их разность равна 
или 
Значит, a и b удовлетворяют условию задачи, что невозможно.