Делимость

[wpoms.]

`S` - подмножество множества чисел `{1, 2, 3,..., 2008}`, которое состоит из `756` различных чисел. Покажите, что оно содержит два различных элемента `a`, `b`, такие, что `a + b` делится на `8`.

@темы: Теория чисел

Comments

[vyv2]

Если мы выберем из 2008 чисел 755 чисел , которые при делении на 8 имеют остаток из трех любых чисел из ряда 1, 2, 3 ,5, 6,7 так, чтобы сумма двух из этих остатков не равна 8(например, 1,2,3 или 1,2,7 или 2,5,7 и т.д.) (их число равно 251*3) и по одному числу с остатками 0 и 4, то сумма любых двух из них не делится на 8, а при добавлении к этим 755 числам любого из оставшихся (остались числа вида 8n,4+8n и числа, остатки которых в сумме с числом из 753 чисел дают остаток 8 ), приводит к паре , сумма которых делится на 8.