Доказать что из 11 различных натуральных чисел меньших 20 можно выбрать три числа так чтобы одно число было равно сумме двух других

Привет! Давай докажем это утверждение вместе.

Шаг 1: Подготовительный

Нам нужно доказать, что из любого набора из 11 различных натуральных чисел, каждое из которых меньше 20, всегда можно найти три числа (a, b, c), таких, что a + b = c.

Шаг 2: Доказательство от противного

Предположим, что существует такой набор из 11 чисел, для которого нельзя найти три числа, удовлетворяющих условию a + b = c. Попробуем построить такой набор.

Шаг 3: Построение "худшего" набора

Чтобы избежать ситуации a + b = c, нам нужно выбирать числа так, чтобы сумма любых двух из выбранных чисел не равнялась никакому другому числу из этого набора. Начнем с самого большого числа, которое меньше 20, то есть с 19.

Теперь будем добавлять числа в порядке убывания, следя за тем, чтобы не нарушалось наше условие:

• 19 (самое большое число)
• 18 (19 - 1 = 18, сумма не равна 19)
• 17 (17 + 18 = 35 > 19, 17 + 19 = 36 > 19, всё хорошо)
• 16 (16 + 17 = 33 > 19, 16 + 18 = 34 > 19, 16 + 19 = 35 > 19, всё хорошо)
• 15 (15 + 16 = 31 > 19, ..., всё хорошо)

И так далее. В какой-то момент мы придем к тому, что добавление нового числа нарушит условие. На самом деле, можно построить такой набор, в котором разница между любыми двумя числами будет больше, чем самое маленькое число в наборе.

Шаг 4: Рассуждение о минимальном наборе

Рассмотрим наименьший возможный набор из 6 чисел, который удовлетворяет условию, что никакое число не является суммой двух других. Это числа: 10, 11, 12, 13, 14, 15, 16, 17, 18, 19.

Если мы возьмем числа: 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, то минимальная сумма двух чисел из этого набора будет 10 + 11 = 21.

Шаг 5: Противоречие и вывод

Теперь посмотрим на "худший" случай. Пусть мы выбрали 11 чисел, начиная с наибольших: 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19. Самая маленькая сумма двух чисел будет 9+10 = 19. Набор 11 чисел: {9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19}.

В этом наборе 19 = 9+10.

Следовательно, наше предположение о существовании набора из 11 чисел, не удовлетворяющего условию, неверно.

Шаг 6: Заключение

Значит, из любых 11 различных натуральных чисел, меньших 20, всегда можно выбрать три числа, таких, что одно из них равно сумме двух других.

Ответ: Доказано.