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

Question

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

yurka1973 · Answer

Рассмотрим, два числа с какими остатками от деления на 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 (принцип Дирихле).

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

Популярные вопросы