 |
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övetkezik-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
| \(\displaystyle \sum\limits_{i=1}^{2000}\frac{(-1)^{2000-i}a_i}{\prod\limits_{\substack{1\leq j\leq 2000 \\ j\ne i}} (i-1)!(2000-i)!}=0, \) | \(\displaystyle {(*)}\) |
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