Задания
Версия для печати и копирования в MS Word
Докажите, что при n = 3002 сумма биномиальных коэффициентов с шагом 6, то есть 
дает остаток 1 при делении на 3. Где 
— количество способов выбрать из n предметов k, что составляет 
если 
и 0 в остальных случаях.
Решение.
Легко проверить, что
следовательно, 
даёт такой же остаток при делении на 3, что и 
Таким образом,
даёт такой же остаток при делении на 3, что и
(здесь отброшены два крайних слагаемых, равные 0). Обозначим эту сумму за 
Аналогично переходим к
Применив эту процедуру ещё 998 раз, получаем, что формула из условия даёт такой же остаток при делении на 3, что и
что даёт остаток 1 при делении на 3.
?
Открытая олимпиада школьников, 11 класс, 2 тур (заключительный), 2016 год