Условие
Даны 1002 различных числа, не превосходящих
2000. Докажите, что из них можно выбрать три таких числа, что
сумма двух из них равна третьему. Останется ли это утверждение
справедливым, если число 1002 заменить на 1001?
Решение
Докажем по индукции, что если из чисел от 1 до
2
n - 2
(
n 
3) выбрано
n + 1 различное число, то из них можно
выбрать три таких числа, что сумма двух из них равна третьему.
При
n = 3 утверждение задачи очевидно. Предположим, что
утверждение доказано для
n =
k и рассмотрим случай
n =
k + 1. Если
k + 1 из выбранных чисел попали в промежуток от 1 до 2
k - 2, то
применимо предположение индукции. Если же это не так, то
обязательно должны быть выбраны числа 2
k - 1 и 2
k. Другие
k
выбранных чисел находятся на отрезке от 1 до 2
k - 2. Разбивая
этот отрезок на пары (1, 2
k - 2), (2, 2
k - 3),..., (
k - 1,
k),
получаем, что одна из пар состоит из выбранных чисел. Но тогда
они дают в сумме 2
k - 1. Если число 1002 заменить на 1001, то
утверждение перестанет быть верным. Примером может служить набор
1000, 1001,..., 2000.
Источники и прецеденты использования
