Многочлены на Изумруде —Каталог задач по Олимпиадной математике

Главная
Каталог задач
Каталог заданий по Олимпиады - Математика
Многочлены на Изумруде

Тема Изумруд

Многочлены на Изумруде

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела изумруд

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#73375

Максим написал на доске произвольный многочлен $P (x)$ с целыми коэффициентами. Антон, не глядя на доску, сказал, что какое бы натуральное число $n$ не назвал Максим, среди выражений $P (1),P (1)+ P(2),P(1)+ P(2)+P (3),...$ обязательно найдётся число, кратное $n.$ Прав ли Антон?

Показать ответ и решение

Заметим, что $P(x+n) ≡P (x) (mod n),$ это следует из того, что $(x +n)k ≡ xk (mod n)$ для любого $k.$ Рассмотрим сумму $2 P (1)+ P(2)+ ...+ P(n).$ Заметим, что в слагаемые в той сумме разбиваются на $n$ групп так, что в каждой группе слагаемые имеют вид $P(i+kn)$ ( $i,k ∈[0,n− 1]$ ) и дают одинаковый остаток при делении на $n.$ Но тогда сумма слагаемых в каждой группе кратна $n,$ потому что мы суммируем $n$ одинаковых остатков. Но тогда и вся рассмотренная сумма кратна $n.$