|
Дан многочлен $%P(x)$%, все коэффициенты которого - целые числа. а) Тамара выписывает в тетрадь суммы: $$P(1),\quad P(1)+P(2),\quad P(1)+P(2)+P(3),\quad\dots,\quad P(1)+P(2)+P(3)+\dots +P(n)+\dots$$ Докажите, что рано или поздно Тамара выпишет сумму, кратную 2018. б) А вот Шуламит, сестра Тамары, выписывает на доску другие суммы: $$P(1),\quad P(1)+P(2),\quad P(1)+P(2)+P(4),\quad\dots,\quad P(1)+P(2)+P(4)+\dots +P(2^n)+\dots$$ Докажите, что и Шуламит рано или поздно выпишет сумму, кратную 2018. задан 18 Сен '18 23:49 
Казвертеночка |
|
а) Из простейших свойств сравнений ясно, что из x=y (mod m) вытекает P(x)=P(y) (mod m) для любого многочлена с целыми коэффициентами. Поэтому числа последовательности P(1), P(2), ... будут периодически повторяться. Ясно тогда, что если взять m раз суммы P(1)+P(2)+...+P(m), что будет иметь место для P(1)+P(2)+...+P(m^2), то итог будет кратен m. б) Последовательность остатков 1, 2, 4, ... , 2^n, ... по модулю m также периодична, начиная с некоторого номера. Если m -- простое нечётное, то она периодична, начиная с начала. Пусть n -- наименьший показатель, для которого 2^n-1 делится на 1009 (по-моему, n=504, хотя здесь это несущественно). Из предыдущего мы знаем, что P(1)+...+P(2^{n-1}) дальше будет периодически повторяться, и если взять сумму с числом слагаемых, кратным n, то она будет делится на 1009. Осталось позаботиться о чётности. Для этого ту же сумму достаточно будет повторить дважды. Можно заметить, что количество слагаемых, которые здесь достаточно рассмотреть, не зависит от специфики многочлена P(x). отвечен 19 Сен '18 0:12 
falcao @falcao, большое спасибо! Как Вы считаете, красивая задача?
(19 Сен '18 0:16)
Казвертеночка
2
@Казвертеночка: Вы помещаете много задач, которые я бы отнёс к числу красивых. Туда входят порой даже совсем простенькие задачи. Но эту бы я к такой категории не отнёс: мне она представляется чисто "технической". В принципе, задача неплохая, но эстетически меня она не привлекла.
(19 Сен '18 0:28)
falcao
|