Районная олимпиада, 2004-2005 учебный год, 9 класс

Даны $n+1$ различных натуральных чисел, меньших $2n$. Докажите, что из них можно выбрать три таких числа, что одно из них равно сумме двух других.

Комментарий/решение

Немного не понял условие задачи. Предположим есть ряд чисел

$$1,2,3,4,5,6,7,8$$

Из него выбираем три числа : $1+2=3$

И что, получается, добавление чисел в ряд не меняет ситуации: все равно можно выбрать числа $1,2,3$, и одно из них равно сумме двух других

Неужели так просто решается?

Нет, они не обязательно последовательные или какие-либо еще, просто даны n+1 чисел из набора {1, 2, ... , 2n - 1}

Возьмем из данных $n+1$ чисел, число A которое меньше $2n - 1$.

Возьмем из оставшихся $n$ чисел, числа $a[1], a[2], ... , a[n - 1]$, которые также меньше $2n-1$, несложно понять что это возможно сделать.

Рассмотрим числа $A + a[i]$, при $i = 1, 2, ... , n - 1$

Они все меньше $2n$, следовательно принадлежат набору ${1, 2, ... , 2n - 1}$, но таких чисел у нас $n - 1$, в то время как чисел в наборе ${1, 2, ... , 2n - 1}$, которые нам изначально не дали ровно $n - 2$, следовательно найдется B которое нам изначально дали и при этом $B = A + a[i]$, для некоторого $i$