Problem B. 5068. (December 2019)

B. 5068. Let \(\displaystyle p\) be an at most 1998th-degree polynomial such that the values \(\displaystyle p(1), p(2),\dots,p(2000)\) form a permutation of the numbers \(\displaystyle 1,2,\dots,2000\). Does it follow that \(\displaystyle p(1)\) and \(\displaystyle p(2000)\) are \(\displaystyle 1\) and \(\displaystyle 2000\) in some order?

(6 pont)

Deadline expired on January 10, 2020.

Sorry, the solution is available only in Hungarian. Google translation

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.)

Statistics:

12 students sent a solution.
6 points:	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 points:	1 student.
0 point:	1 student.

Problems in Mathematics of KöMaL, December 2019