Олимпиадная задача: Барон Мюнхгаузен и восстановление многочлена по значениям P(2) и P(P(2))
Задача
Барон Мюнхгаузен попросил задумать непостоянный многочлен P(x) с целыми неотрицательными коэффициентами и сообщить ему только значения P(2) и P(P(2)). Барон утверждает, что он только по этим данным всегда может восстановить задуманный многочлен. Не ошибается ли барон?
Решение
Пусть P(x) = anxn + ... + a1x + a0 и P(2) = b. Тогда b = 2nan + ... + 2a1 + a0 > an + ... + a1 + a0, следовательно, b больше каждого из коэффициентов ak.
Обозначим p0 = P(P(2)) = P(b) = anbn + ... + a1b + a0. Поделив p0 на b c остатком, получим в остатке a0, а в частном – p1 = anbn–1 + ... + a2b + a1. Аналогично, поделив p1 на b c остатком, получим в остатке a1, а в частном – p2 = anbn–2 + ... + a3b + a2, и т. д.
Ответ
Барон всегда прав.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь