Дан многочлен F(x)=1+2x+3x^2+...+100x^99. Можно ли, переставив коэффициенты в нём, получить многочлен G(x)=g[0]+g[1]x+g[2]x^2+...+g[99]x^99 такой, что для всех натуральных k>=2 разность F(k)-G(k) не кратна 100.
Задача была предложена 2 февраля 2020 года на Объединённой межвузовской математической олимпиаде.
Давайте сначала осознаем, почему не для всех натуральных чисел, а только для тех, что не меньше двух.
Если подставить x=1, то получим G(1)=g[0]+g[1]+g[2]+...g[99]=1+2+...99+100=F(1),
т.е. F(1)-G(1)=0. А раз разность равна нулю, то она кратна 100.
Можно ли использовать это соображение для решения задачи? Да! Надо рассмотреть какое-нибудь другое число, которое даёт остаток 1 при делении на 100, ведь
(100s+1)^m-1^m делится на 100 при всех целых неотрицательных m.
Значит, при x=100s+1 выражение
G(x)=g[0]+g[1]x+g[2]x^2+...+g[99]x^99
имеет такой же остаток, что и G(1).
И выражение F(x)=1+2x+3x^2+...+100x^99 имеет такой же остаток, что и F(1).
Значит, при k=100s+1 выражение F(k)-G(k) делится на 100.
