|
|
 |
Условие
Даны n + 1 попарно различных натуральных чисел, меньших 2n (n > 1).
Докажите, что среди них найдутся три таких числа, что сумма двух из них равна третьему.
Решение 1
Воспользуемся методом математической индукции.
База. При n = 2 выбранными оказываются числа 1, 2, 3. При этом 1 + 2 = 3.
Шаг индукции. Пусть есть n + 2 натуральных числа, меньших 2n + 2. Возможны два случая.
1) Среди выбранных чисел нет числа 2n + 1. Тогда из чисел, меньших 2n, выбрали по крайней мере n + 1 число. По предположению индукции, найдутся три числа, сумма которых равна третьему.
2) Среди выбранных чисел есть число 2n + 1. Разобьём числа 1, 2, ..., 2n на n пар, в сумме дающих 2n + 1: {1, 2n}, {2, 2n – 1}, ..., {n, n + 1}. Поскольку в набор входит ещё n + 1 число, то какая-то из пар входит в набор целиком. Числа этой пары и число 2n + 1 образуют искомую тройку.
Решение 2
Пусть a1 – самое маленькое из этих чисел. Рассмотрим набор чисел {a2, ..., an+1, a2 + a1, a3 + a1, ..., an+1 + a1}. В нём 2n чисел, но все они находятся на отрезке [a1 + 1, a1 + 2n – 1], который состоит из 2n – 1 числа. Следовательно, в наборе есть два равных числа, то есть ai = aj + a1, что и требовалось.
Замечания
Заметим, что мы доказали более сильное утверждение: одним из трёх искомых чисел всегда можно выбрать минимальное число в наборе.
