A B. 5068. feladat (2019. december)

B. 5068. Tegyük fel, hogy $\displaystyle p$ egy legfeljebb 1998-adfokú polinom, melyre a $\displaystyle p(1), p(2),\dots,p(2000)$ értékek az $\displaystyle 1,2,\dots,2000$ számok egy permutációja. Követ­kezik-e ebből, hogy a $\displaystyle p(1)$ és $\displaystyle p(2000)$ számok az $\displaystyle 1$ és $\displaystyle 2000$ valamelyik sorrendben?

(6 pont)

A beküldési határidő 2020. január 10-én LEJÁRT.

Megoldás. Legyen $\displaystyle a_1:=p(1),a_2:=p(2),\dots,a_{2000}:=p(2000)$.

Ekkor a feltétel szerint $\displaystyle \{a_1,a_2,\dots,a_{2000}\}=\{1,2,\dots,2000\}$. Pontosan egy olyan legfeljebb 1999-edfokú $\displaystyle p$ polinom van, amelyre $\displaystyle p(i)=a_i$ minden $\displaystyle 1\leq i\leq 2000$ esetén, méghozza a Lagrange-interpoláció alapján:

$\displaystyle p(x)=\sum\limits_{i=1}^{2000}a_ip_i(x),$

ahol $\displaystyle p_i(x)=\prod\limits_{\substack{1\leq j\leq 2000 \\ j\ne i}} \frac{x-j}{i-j}$.

(A fent megadott polinom valóban rendelkezik az előírt tulajdonságokkal: 1999-edfokú polinomok összege, így foka legfeljebb 1999, valamint, ha behelyettesítünk $\displaystyle i$-t, akkor minden $\displaystyle j\ne i$-re $\displaystyle p_j(i)=0$ – hiszen a $\displaystyle p_j$ polinomnál szerepel az $\displaystyle x-i$ gyöktényező –, és $\displaystyle p_i(i)=1$, így valóban $\displaystyle p(i)=a_ip_i(i)=a_i$. Két különböző ilyen polinom nem lehet, mert akkor a különbségük egy olyan legfeljebb 1999-edfokú polinom lenne, melynek legalább 2000 gyöke van.)

Ez tehát azt jelenti, hogy a feladatban szereplő polinom éppen $\displaystyle p(x)=\sum\limits_{i=1}^{2000}a_ip_i(x)$. Azonban a feladat feltétele szerint $\displaystyle p$ foka legfeljebb 1998, ami azt jelenti, hogy az $\displaystyle a_ip_i(x)$ polinomok 1999-edfokú tagjai kiejtik egymást:

$\displaystyle \sum\limits_{i=1}^{2000}\frac{a_i}{\prod\limits_{\substack{1\leq j\leq 2000 \\ j\ne i}} (i-j)}=0,$

azaz

hiszen

$\displaystyle \prod\limits_{\substack{1\leq j\leq 2000 \\ j\ne i}} (i-j)=(i-1)(i-2)\dots(i-(i-1))(i-(i+1))\dots(i-2000)=(i-1)!(-1)^{2000-i}(2000-i)!$

A $\displaystyle (*)$ egyenletet $\displaystyle 1999!$-sal szorozva kapjuk, hogy

$\displaystyle \sum\limits_{i=1}^{2000}\binom{1999}{i-1}(-1)^{2000-i}a_i=0,$

vagyis

$\displaystyle \sum\limits_{i=0}^{1999}\binom{1999}{i}(-1)^{1999-i}a_{i+1}=0.$

Az $\displaystyle a_1,a_2,\dots,a_{2000}$ számok egészek (hiszen az $\displaystyle 1,2,\dots,2000$ egy permutációja), továbbá, mivel az 1999 prímszám, ezért $\displaystyle 1\leq i\leq 1998$ esetén $\displaystyle \binom{1999}{i}=\frac{1999!}{i!(1999-i)!}$ osztható 1999-cel. Vagyis a $\displaystyle \sum\limits_{i=0}^{1999}\binom{1999}{i}(-1)^{1999-i}a_{i+1}$ összeg első ($\displaystyle i=0$-hoz tartozó) és utolsó ($\displaystyle i=1999$-hez tartozó) tagjának kivétel minden tag osztható 1999-cel. Így az összeg csak úgy lehet 0, ha az első és utolsó tag összege is osztható 1999-cel. Tehát $\displaystyle -a_1+a_{2000}$ osztható kell legyen 1999-cel. Azonban $\displaystyle a_1$ és $\displaystyle a_{2000}$ az $\displaystyle \{1,2,\dots,2000\}$ halmaz két különböző eleme, így ez csak akkor lehetséges, ha $\displaystyle \{a_1,a_{2000}\}=\{1,2000\}$.

Ezzel megmutattuk, hogy $\displaystyle p(1)=a_1$ és $\displaystyle p(2000)=a_{2000}$ az 1 és 2000 valamelyik sorrendben.

Megjegyzések. 1. Mindkét sorrend lehetséges, amint azt a $\displaystyle p(x)=x$ és $\displaystyle p(x)=2001-x$ polinomok mutatják. 2. Jól ismert, hogy ha $\displaystyle p$ pozitív egész és $\displaystyle f(x)$ egy $\displaystyle n$-nél alacsonyabb fokú polinom, akkor

$\displaystyle \sum_{k=0}^{n} (-1)^k\binom{n}{k}f(k) = 0,$

a fenti megoldás is ezt az azonosságot bizonyítja. (Interpoláció helyett egy másik lehetőség az értékek $\displaystyle n$-edik különbségsorozatát venni.)

Statisztika:

12 dolgozat érkezett.
6 pontot kapott:	Andó Viola, Beke Csongor, Fleiner Zsigmond, Füredi Erik Benjámin, Hámori Janka, Kocsis Anett, Mácsai Dániel, Szabó 991 Kornél, Sztranyák Gabriella, Velich Nóra.
4 pontot kapott:	1 versenyző.
0 pontot kapott:	1 versenyző.

A KöMaL 2019. decemberi matematika feladatai