Feladat:	B.4589	Korcsoport: 16-17	Nehézségi fok: nehéz
Megoldó(k):	Gyulay-Nagy Szuzina ,  Herczeg József ,  Maga Balázs ,  Williams Kada
Füzet:	2014/május, 283 - 285. oldal		PDF  |  MathML
Témakör(ök):	Feladat, Hatványösszeg, Maradékosztályok
Hivatkozás(ok):	Feladatok: 2013/december: B.4589

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.   Megoldás. A feladat kérdésére a válasz igenlő. (1) Legyen $k$ pozitív egész szám. Először azt mutatjuk meg, hogy az első $n$ pozitív egész $k$-adik hatványának összegét $n$-nek egy $k+1$-ed fokú polinomja adja meg. Indukcióval bizonyítunk; $k=1$-re ez ismert. Tegyük fel, hogy $k-1$-ig igaz az állítás. Írjuk fel a következő egyenleteket: ${\displaystyle \begin{array}{cc}\hfill {\displaystyle {\left(0+1\right)}^{k+1}}& {\displaystyle =1^{k+1}\mathrm{,}}\hfill \\ \hfill {\displaystyle {\left(1+1\right)}^{k+1}}& {\displaystyle =2^{k+1}\mathrm{,}}\hfill \\ \hfill {\displaystyle {\left(\left(n-1\right)+1\right)}^{k+1}}& {\displaystyle =n^{k+1}\mathrm{,}}\hfill \\ \hfill {\displaystyle {\left(n+1\right)}^{k+1}}& {\displaystyle ={\left(n+1\right)}^{k+1}\mathrm{.}}\hfill \end{array}}$ Mindegyik egyenlőség bal oldalát kifejthetjük a binomiális tétel szerint. Ha utána ezeket összeadjuk, a $k+1$-edik hatványok a rendezés során egy tag $\left({\left(n+1\right)}^{k+1}\right)$ kivételével kiesnek. Jelölje (minden $t$-re) a $\text{<span style="font-size:16px;"><math xmlns="http://www.w3.org/1998/Math/MathML"><munderover><mrow><mo>∑</mo></mrow><mrow><mi>i</mi><mo stretchy="false">=</mo><mn>1</mn></mrow><mrow><mi>n</mi></mrow></munderover><mrow><msup><mrow><mi>i</mi></mrow><mrow><mi>t</mi></mrow></msup></mrow></math></span>}$ összeget $S_t$, ekkor $\begin{array}{c}{\displaystyle \left(\genfrac{}{}{0ex}{}{k+1}{1}\right)S_k+\left(\genfrac{}{}{0ex}{}{k+1}{2}\right)S_{k-1}+\text{...}+\left(\genfrac{}{}{0ex}{}{k+1}{k}\right)S_1+\left(\genfrac{}{}{0ex}{}{k+1}{k+1}\right)n={\left(n+1\right)}^{k+1}\mathrm{,}}\end{array}$ azaz $\begin{array}{c}{\displaystyle S_k=\frac{1}{k+1}\left({\left(n+1\right)}^{k+1}-\left\{\left(\genfrac{}{}{0ex}{}{k+1}{2}\right)S_{k-1}+\text{...}+\left(\genfrac{}{}{0ex}{}{k+1}{k}\right)S_1+\left(\genfrac{}{}{0ex}{}{k+1}{k+1}\right)n\right\}\right)\mathrm{.}}\end{array}$ A jobb oldalon a kapcsos zárójelben szereplő összeg minden tagja az indukciós feltevés szerint előáll az $n$ egy legfeljebb $k$-ad fokú polinomjaként. Ezzel (1)-et beláttuk.   (2) Legyen $k$ pozitív egész. Belátjuk, hogy a $\left[0;1\right]$ intervallum felbontható véges sok racionális végpontú szakaszra, és e szakaszok tíz színnel kiszínezhetők úgy, hogy minden, legfeljebb $k$-ad fokú $f$ polinomra, ha vesszük mindegyik $\left[a;b\right]$ szakasznál az $f\left(b\right)-f\left(a\right)$ különbségeket, és az azonos színű szakaszokhoz tartozókat összeadjuk, a kapott tíz összeg egyenlő. Ha $c$ tetszőleges nemnulla konstans, akkor az $f\left(cx\right)$ és $f\left(x+c\right)$ polinomok foka is annyi, mint az $f$ polinomé; így elég az állításunkat $\left[0;1\right]$ helyett valamely alkalmas zárt intervallumra belátnunk; ezt a $k$ szerinti indukcióval tesszük. Nyilvánvalóan $k=1$-re jó felbontás az, hogy a tizedelő pontok által meghatározott szakaszokat vesszük. Tegyük fel ezután, hogy (2) teljesül $k=t$-re. Tekintsük a $\left[0;1\right]$ intervallum egy ennek megfelelő felosztását és színezését; jelölje a színeket $s_0$, $s_1$, $\text{...}$, $s_9$. Másoljuk át a felosztást rendre az $\left[1;2\right]$, $\text{...}$, $\left[9;10\right]$ intervallumokra, viszont változtassuk meg ezeken a színezést úgy, hogy az $\left[i;i+1\right]$-en $s_v$ helyébe $s_{v+i}$ lépjen (minden $0\le i\mathrm{,}v\le 9$-re; itt $v+i$ természetesen modulo 10 értendő). Ha ezután $f$ egy $t+1$-ed fokú polinom (aminek a főegyütthatója $c$), akkor minden $0\le i\le 9$-re felírható $f=c{\left(x-i\right)}^{t+1}+g_i\left(x\right)$ alakban, ahol a $g_i$ polinomok legfeljebb $t$-ed fokúak. Ekkor $f\left(x\right)=m\left(x\right)+r\left(x\right)$, ahol $\begin{array}{c}{\displaystyle m\left(x\right)=c{\left(x-i\right)}^{t+1}\mathrm{,}\text{és}r\left(x\right)=g_i\left(x\right)\mathrm{,}\text{ha}x\in \left[i;i+1\right]\mathrm{.}}\end{array}$ A $\left[0;10\right]$ intervallumnak az így kapott felosztása és színezése mind az $m\left(x\right)$, mind pedig az $r\left(x\right)$ függvény számára megfelelő: $r\left(x\right)$-nek azért, mert az indukciós feltevés miatt mindegyik $\left[i;i+1\right]$ szakaszon is ugyanannyi az egyes színekhez tartozó különbségek összege. A konstrukció miatt pedig a $\left[0;10\right]$ szakaszon az $m\left(x\right)$ függvény szerinti különbségek összege bármelyik színben egyenlő a $c{x}^{t+1}$ függvény $c\left(1^{t+1}-0^{t+1}\right)=c$ ,,megváltozásával'' a $\left[0;1\right]$-en, mivel (az egységszakaszokon a színek ciklikus változtatása miatt) minden, a $\left[0;1\right]$ felosztásában szereplő szakasz tíz eltoltja tíz különböző színnel van kifestve (és $m\left(x\right)$ periodikus 1 szerint). Ezzel a (2) állítást beláttuk. Vegyük a $\left[0;1\right]$ szakasznak (2) alapján egy jó felosztását és színezését $k=11$-re. Az osztópontok racionálisak ‐ nagyítsuk fel az elrendezést úgy, hogy egészek legyenek. Tekintsük azt a $11$-ed fokú $f$ polinomot, amely (1) szerint az első $n$ pozitív egész szám 10-edik hatványának összegképletét adja meg. Az $f$ két egész helyen felvett értékének az eltérése egymást követő tizedik hatványok összege. Így bebizonyítottuk az állítást.