Дан многочлен $%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

изменен 18 Сен '18 23:50

10|600 символов нужно символов осталось
1

а) Из простейших свойств сравнений ясно, что из 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, большое спасибо! Как Вы считаете, красивая задача?

(19 Сен '18 0:16) Казвертеночка
2

@Казвертеночка: Вы помещаете много задач, которые я бы отнёс к числу красивых. Туда входят порой даже совсем простенькие задачи. Но эту бы я к такой категории не отнёс: мне она представляется чисто "технической". В принципе, задача неплохая, но эстетически меня она не привлекла.

(19 Сен '18 0:28) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,212
×383
×179
×17
×12

задан
18 Сен '18 23:49

показан
191 раз

обновлен
19 Сен '18 0:28

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru