Олимпиадная задача по индукции и принципу Дирихле для 9-10 классов

Решение 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:   Пусть a₁ – самое маленькое из этих чисел. Рассмотрим набор чисел  {a₂, ..., a_n+1,  a₂ + a₁,  a₃ + a₁,  ...,  a_n+1 + a₁}.  В нём 2n чисел, но все они находятся на отрезке  [a₁ + 1,  a₁ + 2n – 1],  который состоит из  2n – 1  числа. Следовательно, в наборе есть два равных числа, то есть  a_i = a_j + a₁,  что и требовалось.

Ответ задачи отсутствует