Question

Из чисел 1, 2, …, 2010 произвольным образом выбрали 673 числа. Докажите, что среди выбранных чисел есть два, сумма которых делится на 6.

Answer 1

Рассмотрим, два числа с какими остатками от деления на 6 дают число, делящееся на 6:

1. 0 + 0 ≡ 0 (mod 6)
2. 1 + 5 ≡ 0 (mod 6)
3. 2 + 4 ≡ 0 (mod 6)
4. 3 + 3 ≡ 0 (mod 6)

В связи с этим у нас может быть максимально по одному числу с остатком 0 или 3 от деления на 6 (макс. 2 числа). К тому же, если у нас есть число, дающее остаток 1 или 2 от деления на 6, то не может быть числа с остатком соответственно 5 и 4 (и наоборот) (макс. 670 чисел). Так как можно выбрать максимально 672 числа, среди которых нет дающих в сумме число, делящееся на 6, то среди 673-х чисел обязательно найдутся два, дающие в сумме число, делящееся на 6 (принцип Дирихле).

Answer 2

Для доказательства данного утверждения воспользуемся методом "Причинного следственной связи" (Принцип Дирихле). Этот принцип утверждает, что если у нас есть nn объектов и mm контейнеров, и nn > m, то как минимум один контейнер должен содержать более одного объекта.

Предположим, что ни одна из сумм двух выбранных чисел не делится на 6. Рассмотрим остатки этих чисел при делении на 6. Остатки могут быть 0, 1, 2, 3, 4 или 5.

Теперь мы знаем, что из 673 чисел 2010 возможных остатков (по модулю 6) каждый из остатков представлен хотя бы одним числом.

• Остаток 0: числа вида 6k (6, 12, 18, ...).
• Остаток 1: числа вида 6k + 1 (1, 7, 13, ...).
• Остаток 2: числа вида 6k + 2 (2, 8, 14, ...).
• Остаток 3: числа вида 6k + 3 (3, 9, 15, ...).
• Остаток 4: числа вида 6k + 4 (4, 10, 16, ...).
• Остаток 5: числа вида 6k + 5 (5, 11, 17, ...).

Теперь рассмотрим выбранные 673 числа и разделим их на эти остатки. По принципу Дирихле, как минимум один из остатков будет содержать более одного числа. Возьмем два числа из этого остатка, скажем a и b. Это могут быть два различных остатка (например, a = 6k и b = 6l + 1), или это могут быть два числа с одним и тем же остатком (например, a = 6k + 1 и b = 6l + 1).

Если a и b имеют один и тот же остаток при делении на 6, то их разность (|a - b|) будет делиться на 6, потому что она будет иметь вид (6k + 1) - (6k + 1) = 6k, что делится на 6.

Если a и b имеют разные остатки при делении на 6 (например, a = 6k и b = 6l + 1), то их сумма (a + b) будет иметь остаток 1 при делении на 6, потому что (6k + (6l + 1)) = 6(k + l) + 1, что также делится на 6.

Таким образом, в любом случае среди выбранных 673 чисел найдутся два числа, сумма которых делится на 6.