Loading [MathJax]/jax/output/SVG/jax.js

Математикадан облыстық олимпиада, 2020 жыл, 11 сынып


Коэффициенттері бүтін, дәрежесі 10-нан аспайтын P(x) көпмүшесі берілген. Әрбір k{1,2,,10} үшін P(m)=k болатындай бүтін m саны табылатыны белгілі. Егер |P(10)P(0)|<10000 болса, әрбір k{1,2,,10000} үшін P(m)=k болатындай бүтін m саны табылатынын дәлелдеңіз.
посмотреть в олимпиаде

Комментарий/решение:

  0
4 года 2 месяца назад #

На самом деле можно доказать, что для любого целого k существует целое m, что P(m)=k.

Факт 1:

Eсли коэффиценты P(x) целые, то P(a)P(b)0 (mod ab).

(Этот факт часто используется когда коэффиценты многочлена целые)

Пусть m1,m2,,m10 такие целые числа, что P(mi)=i для каждого 1i10.

Утверждение 1:

Числа {mi} последовательные.

Доказательство:

1=P(mi+1)P(mi)0(mod mi+1mi)

Поэтому mi+1=mi±1

Если m2=m1+1, то m3=m2+1,m4=m3+1 и т.д.

Если же m2=m11, то m3=m21,m4=m31 и т.д.

Утверждение 2:

P(x+1)P(x)=1, если {mi} возрастающая.

P(x1)P(x)=1, если {mi} убывающая.

Доказательство:

Разберем только первый случай, потому что второй ему аналогичен.

1. Случай: Последовательность {mi} возрастающая.

Рассмотрим многочлен Q(x)=P(x+1)P(x), тогда степень Q не больше n19 и коэффиценты Q целые.

Мы знаем, что Q(mi)=1 при всех i=1,2,,9, значит

Q(x)=a(xm1)(xm11)...(xm18)+1 для какого-то целого числа a.

Тогда |P(10)P(0)|=|Q(9)+Q(8)+...+Q(0)|=|9i=0a(im1)(im11)...(im18)+10|=|9i=0a(m1i)(m1+1i)...(m1+8i)10|.

Обозначим S=|9i=0(m1i)(m1+1i)...(m1+8i)|, тогда по условию |aS10|<1000010000+10<aS<10000+10

Докажем, что при a0 это условие не выполняется.

Заметим, что если m110, то каждое слагаемое в S делится 9! и не равно нулю, поэтому |aS||S|>9!>10010

Аналогично, при m110, каждое слагаемое в S делится на 9! и не равно 0, поэтому |aS||S|>9!>10010

Если же 10<m1<10, то абсолютно все слагаемые будут либо не отрицательными, либо не положительными и среди них обязательно найдется хотя бы одно не равное нулю. Также все слагаемые делятся на 9!, поэтому |aS||S|>9!>10010

Значит, при a0 мы получаем противоречие, тогда a=0, а P(x+1)P(x)=1()

Примечание: Из этого можно вывести, что P - многочлен первой степени

Завершение:

Из (*) легко получить, что:

P(m+k1)=P(m)+k1=k для любого целого k.