Question

Докажите, что из пяти натур. чисел найдется три, сумма которых делится на три.

Answer 1

Либо хотя бы одно число делится на 3, либо найдутся три такие числа, что их остатки равны. Действительно, ведь все числа можно представить как 3n, 3n - 1 и 3n - 2 (n - натуральное). Остатки их могут быть равны 0, 1 и 2. Ещё, их у нас 5, что не позволит нам их представить иначе. В первом случае (когда хотя бы одно число делится на 3), мы можем сложить числа с остатками 0, 1 и 2. Тогда, (a + b + c) mod 3 = (a mod 3 + b mod 3 + c mod 3) mod 3 = 0. Во втором случае, если найдутся три числа с равными остатками, то аналогично (a mod 3 + b mod 3 + c mod 3) mod 3 = 0.

Answer 2

Давайте докажем это утверждение методом математической индукции. Исходное утверждение звучит следующим образом:

"Из пяти натуральных чисел найдется три, сумма которых делится на три."

Шаг 1: Базовый случай (n = 5) Для случая, когда у нас есть 5 чисел, докажем утверждение напрямую:

Рассмотрим возможные комбинации из пяти чисел:

1. (1, 1, 1, 1, 1) - сумма = 5, не делится на 3.
2. (1, 1, 1, 1, 2) - сумма = 6, делится на 3.
3. (1, 1, 1, 2, 2) - сумма = 7, не делится на 3.
4. (1, 1, 2, 2, 2) - сумма = 8, не делится на 3.
5. (1, 2, 2, 2, 2) - сумма = 9, делится на 3.

Мы нашли комбинацию (1, 1, 1, 1, 2), где сумма равна 6 и делится на 3.

Шаг 2: Предположение индукции Предположим, что утверждение верно для некоторого k, то есть из k натуральных чисел найдется три, сумма которых делится на 3.

Шаг 3: Индукционный переход (k → k + 1) Теперь докажем, что если утверждение верно для k, то оно также верно и для k + 1.

Рассмотрим k + 1 натуральное число. Добавим его к предыдущим k числам. Возможны два случая: а) Если это новое число само по себе делится на 3, то мы нашли комбинацию из k + 1 числа, сумма которых делится на 3 (так как сумма k чисел уже делится на 3, и прибавление числа, которое делится на 3, не изменит этот факт). б) Если новое число не делится на 3, тогда рассмотрим предыдущие k чисел. По предположению индукции, среди этих чисел найдутся три, сумма которых делится на 3. Тогда, добавив новое число к этой комбинации, получим сумму, которая делится на 3.

Таким образом, утверждение верно для k + 1.

По принципу математической индукции мы показали, что для пяти натуральных чисел найдется три, сумма которых делится на 3.