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

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 (принцип Дирихле).