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