Cím:	A 2016. évi Kürschák József Matematikai Tanulóverseny feladatainak megoldásai
Szerző(k):	Fleiner Tamás
Füzet:	2017/február, 67 - 72. oldal	PDF  |  MathML
Témakör(ök):	Matematika, Kürschák József (korábban Eötvös Loránd), Szakmai cikkek, Oszthatóság, Polinomok, Számhalmazok

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.   1. Legyenek $1\le k\le n$ egészek. Az $\left\{\mathrm{1,2,}\text{...}\mathrm{,}n\right\}$ halmaznak legfeljebb hány $k$ elemű részhalmaza adható meg úgy, hogy közülük bármely kettő valamelyike a kettejük uniójának $k$ legkisebb eleméből álljon?   Megoldás. Legyen $\text{H}$ a feladatban leírt tulajdonságú részhalmazok egy rendszere, és legyenek $A$ és $B$ a $\text{H}$ különböző tagjai. Tegyük fel, hogy az $A\cup B$ halmaz $k$ legkisebb eleme az $A$ halmazt alkotja. Tekintettel arra, hogy $|A\cup B|>k$, az $A\cup B$ halmaz legnagyobb eleme nem tartozik $A$-hoz. Ezért ez az elem $B$-hez tartozik, ilyenformán a $\text{H}$ halmazcsalád tagjainak legnagyobb elemei páronként különbözők. A $\text{H}$ halmazcsaládhoz tehát legfeljebb annyi halmaz tartozhat, mint ahányféle az $\mathrm{1,2,}\text{...}\mathrm{,}n$ hamaz egy $k$ elemű részhalmazának a legnagyobb eleme lehet. Világos, hogy az $\mathrm{1,2,}\text{...}\mathrm{,}k-1$ számok egyike sem lehet egy ilyen $k$ elemű részhalmaz legnagyobb eleme, ezért a feladatban kérdezett részhalmazok száma legfeljebb a $\left\{k\mathrm{,}k+\mathrm{1,}\text{...}\mathrm{,}n\right\}$ halmaz számossága, azaz legfeljebb $n-\left(k-1\right)=n-k+1$ lehet. Annak igazolására, hogy ez a felső korlát elérhető, elegendő azt észrevenni, hogy az $A_i:=\left\{j\in \text{N}:i\le j\le i+k-1\right\}$ halmazok rendelkeznek a feladatban leírt tulajdonsággal, ha $i\in \left\{\mathrm{1,2,}\text{...}\mathrm{,}n-k+1\right\}$. Ezzel pedig pontosan $n-k+1$ halmazt adtunk meg, a feladat kérdésére a válasz tehát $n-k+1$. $\square$   Megjegyzés. Maximális méretű halmazcsaládra egy, a fentitől különböző példa $i\in \left\{k\mathrm{,}k+\mathrm{1,}\text{...}\mathrm{,}n\right\}$ esetén az $\left\{\mathrm{1,2,}\text{...}\mathrm{,}k-\mathrm{1,}i\right\}$ halmazok rendszere.   2. Bizonyítsuk be, hogy pozitív egész számok tetszőleges véges $A$ halmazának van olyan $B$ részhalmaza, amelyre fennáll az alábbi két feltétel. $•$ Ha $b_1$ és $b_2$ a $B$ különböző elemei, akkor sem $b_1$ és $b_2$, sem pedig $b_1+1$ és $b_2+1$ nem egymás többszörösei, továbbá $•$ az $A$ halmaz tetszőleges $a$ eleméhez van $B$-nek olyan $b$ eleme, amelyre $a$ osztója $b$-nek vagy $\left(b+1\right)$ osztója $\left(a+1\right)$-nek.   I. megoldás. A megoldás során az alábbi szóhasználattal élünk. Azt mondjuk, hogy a $b$ pozitív egész az $a$ pozitív egészet felülről dominálja, ha $a$ osztója $b$-nek, és alulról dominálja, ha $b+1$ osztója $\left(a+1\right)$-nek. (Minden pozitív egész tehát felülről és alulról is dominálja önmagát.) A $b$ egész akkor dominálja $a$-t, ha $b$ felülről vagy alulról dominálja $a$-t. Az $X$ halmaz pedig akkor dominálja az $Y$ halmazt, ha $Y$ minden $y$ eleméhez található olyan $x$ az $X$-ből, amely dominálja $y$-t. Végül, pozitív egészek egy $Z$ halmazát akkor nevezzük függetlennek, ha $Z$ egyetlen eleme sem dominálja $Z$ egy másik elemét. Az imént bevezetett terminológia segítségével a feladat állítása úgy fogalmazható meg, hogy a pozitív egészek minden véges $A$ halmazának van olyan független $B$ részhalmaza, amely dominálja $A$-t. Tekintsük az $A$ halmaz mindazon $C$ részhalmazait, melyekre $\left(a\right)$ $C$ független, másfelől $\left(b\right)$ ha $A$ valamely $x$ eleme alulról dominálja $C$ egy elemét, akkor $C$ felülről dominálja $x$-et. Létezik a fenti tulajdonságokat teljesítő $C$ halmaz, hisz az üreshalmaz például ilyen. Válasszuk a $B$ halmazt ezen $C$ halmazok közül úgy, hogy $B$ a lehető legtöbb elemét dominálja felülről az $A$ halmazban. Azt állítjuk, hogy egy eképpen választott $B$ halmaz rendelkezik a feladatban előírt tulajdonságokkal. Mivel $B$-t függetlennek választottuk, ezért csupán azt kell igazolni, hogy $B$ dominálja a teljes $A$ halmazt. Indirekt módon bizonyítunk, tegyük fel, hogy $B$ mégsem dominálja $A$-t. Legyen tehát $a$ az $A$ halmaz legkisebb olyan eleme, amit $B$ nem dominál, és legyen $B\text{'}:=B\setminus D\left(a\right)\cup \left\{a\right\}$, ahol $D\left(a\right)$ az $a$ osztóinak halmazát jelöli. Megmutatjuk, hogy $B$ választásának ellentmondva a $B\text{'}$ halmaz amellett, hogy több elemet dominál felülről, mint $B$, teljesíti az $\left(a\right)$ és $\left(b\right)$ tulajdonságokat is. A konstrukcióból adódóan $B\text{'}$ az $A$ halmaz minden olyan elemét felülről dominálja, amely elemeket $B$ felülről dominál, és ezen túl $B\text{'}$ felülről dominálja $a$-t is. Ezért $B\text{'}$ több elemet dominál felülről, mint $B$. A $B$ részhalmazaként $B\text{'}\setminus \left\{a\right\}$ független, továbbá az $a$ választásából adódóan $B\text{'}\setminus \left\{a\right\}$ nem dominálja $a$-t. Sőt, $a$ sem dominálja $B\text{'}\setminus \left\{a\right\}$ egyetlen elemét sem: alulról a $B$ halmaz $\left(b\right)$ tulajdonsága miatt, felülről pedig $B\text{'}$ definíciójából adódóan. Ezért a $B\text{'}$ halmaz csakugyan független. Végül, a $\left(b\right)$ tulajdonság igazolásához indirekt módon tegyük fel, hogy $x$ alulról dominálja $B\text{'}$ egy $y$ elemét. Ha mármost $y\in B$, akkor a $\left(b\right)$ tulajdonság miatt $B$ felülről dominálja $x$-et, így $B\text{'}$ is, tehát teljesül a $\left(b\right)$ tulajdonság. Ha pedig $y\notin B$, akkor $y=a$ és az alulról történő dominálás miatt $x<y$. Mivel $a$ az $A$ halmaz legkisebb olyan eleme, amit $B$ nem dominál, ezért $B$ dominálja $x$-et. Ha $B$ felülről dominálja $x$-et, akkor $B\text{'}$ is felülről dominálja $x$-et, a $\left(b\right)$ tulajdonság teljesül. Ha pedig $B$ egy $z$ eleme alulról dominálja $x$-et, akkor mivel $x$ alulról dominálja $a$-t, $z$ is alulról dominálja $a$-t. Ez azt jelenti, hogy $B$ mégiscsak dominálja $a$-t, ellentétben az $a$ választásával. A kapott ellentmondás pedig azt igazolja, hogy $B\text{'}$-re teljesül a $\left(b\right)$ tulajdonság, és ezzel a bizonyítást befejeztük. $\square$   II. megoldás. Az I. megoldásban bevezetett szóhasználatot tovább bővítjük. Pozitív egészek egy véges $H$ halmaza tetejének nevezzük azt a $H^{\uparrow }$ halmazt, melyet $H$ mindazon $h$ elemei alkotnak, amelyet nem dominál felülről a $H$ egyetlen $h$-tól különböző eleme sem. Hasonlóan, a $H$ halmaz $H^{\downarrow }$-val jelölt alja a $H$ azon $h$ elemeiből áll, amelyet a $H$-nak $h$-tól különböző eleme nem dominál alulról. Világos, hogy $H^{\uparrow }$ felülről, $H^{\downarrow }$ pedig alulról dominálja $H$-t, továbbá, hogy $H$ tetejének egyik eleme sem dominálja $H$ tetejének egy másik elemét felülről, illetve $H$ aljának egyetlen eleme sem dominálja $H$ aljának egy másik elemét alulról. Szükségünk lesz még az alábbi megfigyelésre. Ha egy $X$ halmaz alulról dominálja az $Y$ halmazt, továbbá az $Y$ alulról dominálja $Z$-t, akkor $X$ is alulról dominálja $Z$-t. Legyen ugyanis $z\in Z$ tetszőleges. Az $Y$ és $Z$ viszonya folytán létezik olyan $y\in Y$, amelyre $y+1$ osztója $\left(z+1\right)$-nek. Mivel $X$ alulról dominálja $Y$-t, ezért $X$-nek van olyan $x$ eleme, amelyre $x+1$ osztja $\left(y+1\right)$-et. Ám ekkor $x+1$ osztója $\left(z+1\right)$-nek is, azaz $X$ alulról dominálja $Z$ minden elemét. A továbbiakban megadunk egy véges eljárást, amely tetszőleges $A$ halmazhoz talál egy, a feladatban megkívánt tulajdonságokkal rendelkező $B$ részhalmazt. Legyen $\begin{array}{c}{\displaystyle A_0:=A\mathrm{,}{B}_0:=A_0^{\uparrow }\text{és}{X}_0:=B_0\setminus B_0^{\downarrow }\mathrm{.}}\end{array}$ Ha már meghatároztuk az $A_i$, $B_i$ és $X_i$ halmazokat, akkor legyen $\begin{array}{c}{\displaystyle A_{i+1}:=A_i\setminus X_i\mathrm{,}{B}_{i+1}:=A_{i+1}^{\uparrow }\text{és}{X}_{i+1}:=B_{i+1}\setminus B_{i+1}^{\downarrow }\mathrm{.}}\end{array}$ Figyeljük meg, hogy $B_{i+1}$ az $A_{i+1}$ teteje lévén felülről dominálja $A_{i+1}$-et és a $B_i^{\downarrow }$ alulról dominálja $B_i$-t, így $X_i$-t is. Ugyancsak a definícióból adódóan $B_i^{\downarrow }=B_i\setminus X_i\subseteq B_{i+1}$, ezért $B_{i+1}$ alulról dominálja $B_i^{\downarrow }$-t, így a $B_i^{\downarrow }$ által alulról dominált $X_i$-t is. Világos, hogy $A_0\supseteq A_1\supseteq A_2\supseteq \text{...}$, így az $A$ halmaz végessége miatt $A_k=A_{k+1}$ teljesül valamely $k$-ra. Ez azt jelenti, hogy $X_k=\varnothing$, azaz $B_k=B_k^{\downarrow }$. Mivel $B_k^{\uparrow }={\left(A_k^{\uparrow }\right)}^{\uparrow }=A_k^{\uparrow }=B_k$, ezért $B_k$ független. Megmutatjuk, hogy a $B=B_k$ halmaz megfelel a feladat feltételeinek. Láttuk, hogy $B_k$ független, így csupán azt kell bizonyítanunk, hogy $A$-t is dominálja. Korábban láttuk, hogy $B_k$ az $A_k$-t felülről dominálja. Elegendő tehát annyit bizonyítani, hogy $B_k$ alulról dominálja az $A\setminus A_k=X_0\cup X_1\cup \text{...}\cup X_{k-1}$ halmazt. Láttuk azt is, hogy $B_k$ alulról dominálja az $X_{k-1}$ halmazt. Mivel $B_{k-1}\subseteq B_k\cup X_{k-1}$, ezért $B_k$ a $B_{k-1}$-et is alulról dominálja. Hasonlóan, $B_{k-1}$ alulról dominálja $X_{k-2}$-t, így $B_{k-2}$-t is, tehát $B_k$ is alulról dominálja $B_{k-2}$-t. Ugyanez az érvelés mutatja, hogy $B_k$ alulról dominálja $X_i$-t és $B_i$-t minden $0\le i\le k$-ra. Mindezt összevetve kapjuk, hogy $B_k$ alulról dominálja az $X_0\cup X_1\cup \text{...}\cup X_{k-1}$ halmazt. Ezzel pedig beláttuk, hogy a $B=B_k$ halmaz rendelkezik a feladatban leírt tulajdonsággal. $\square$   3. Igaz-e, hogy ha $p\left(x\right)$ és $q\left(x\right)$ olyan valós együtthatós polinomok, melyekre $p\left(p\left(x\right)\right)=q{\left(x\right)}^2$ teljesül minden valós $x$-re, akkor létezik olyan valós együtthatós $r\left(x\right)$ polinom, amelyre $p\left(x\right)=r{\left(x\right)}^2$ teljesül minden valós $x$-re?   I. megoldás. Ha a $p\left(x\right)$ polinom konstans, akkor $p\left(p\left(x\right)\right)=p\left(x\right)=q{\left(x\right)}^2$, így $r\left(x\right)=q\left(x\right)$ megfelelő választás. Megmutatjuk, hogy a kérdésre igenlő a válasz akkor is, ha a $p$ polinom legalább elsőfokú, amit a továbbiakban felteszünk. A bizonyításhoz felhasználjuk a komplex számkört és az algebra alaptételét. Konkrétan azt, hogy ha $p\left(x\right)=a_0+a_{1}x+\text{...}+a_k{x}^k$, akkor léteznek olyan ${\alpha }_1\mathrm{,}{\alpha }_2\mathrm{,}\text{...}\mathrm{,}{\alpha }_k$ komplex számok, melyekre $\begin{array}{c}{\displaystyle p\left(x\right)=a_k\cdot \left(x-{\alpha }_1\right)\cdot \left(x-{\alpha }_2\right)\cdot \text{...}\cdot \left(x-{\alpha }_k\right)}\end{array}$ (1) teljesül, továbbá ez az ú.n. kanonikus alak az $\left(x-{\alpha }_i\right)$ gyöktényezők sorrendjétől eltekintve egyértelmű. Világos, hogy a fenti ${\alpha }_i$ számok a polinom gyökei, továbbá, mivel a $p\left(x\right)$ polinom valós együtthatós, ha ${\alpha }_i$ gyöke $p\left(x\right)$-nek, akkor annak $\overline{{\alpha }_i}$ is gyöke lesz, ráadásul e két gyök multiplicitása megegyezik, hiszen ha ${\alpha }_i$ nem valós, akkor $\begin{array}{c}{\displaystyle \frac{p\left(x\right)}{\left(x-{\alpha }_i\right)\left(x-\overline{{\alpha }_i}\right)}=\frac{p\left(x\right)}{\left(x^2-2\text{Re}\left({\alpha }_i\right)\cdot x+{|{\alpha }_i|}^2\right)}}\end{array}$ valós együtthatós polinomok hányadosaként maga is valós együtthatós. Ezért pontosan akkor létezik olyan valós együtthatós $r\left(x\right)$ polinom, amelyre $p\left(x\right)=r{\left(x\right)}^2$, ha az $a_k$ főegyüttható nemnegatív, valamint $p\left(x\right)$ fenti kanonikus alakjában minden $\left(x-{\alpha }_i\right)$ gyöktényező páros sokszor fordul elő. Az algebra alaptétele szerint tehát a kompozíciópolinom előáll $\begin{array}{c}{\displaystyle p\left(p\left(x\right)\right)=a_k\cdot \left(p\left(x\right)-{\alpha }_1\right)\cdot \left(p\left(x\right)-{\alpha }_2\right)\cdot \text{...}\cdot \left(p\left(x\right)-{\alpha }_k\right)}\end{array}$ (2) alakban. Mivel $p\left(p\left(x\right)\right)=q{\left(x\right)}^2$, ezért fokszámaik megegyeznek: $p\left(p\left(x\right)\right)$-é $k^2$, $q{\left(x\right)}^2$-é pedig páros. Így $deg\left(p\left(x\right)\right)=k$ is páros. Az is látszik a (2) alapján, hogy $p\left(p\left(x\right)\right)$ főegyütthatója $a_k^{k+1}$, és ez megegyezik $q{\left(x\right)}^2$ pozitív főegyütthatójával. Ezért $a_k^{k+1}>0$. Mivel $k+1$ páratlan, innen $a_k>0$ adódik. Figyeljük meg továbbá, hogy $p\left(p\left(x\right)\right)$ kanonikus alakja megkapható úgy, hogy a (2) szorzatban minden nemkonstans tényezőt helyettesítünk az adott tényezőnek a $k$ gyöktényezőt tartalmazó kanonikus alakjával, azaz $\left(p\left(x\right)-{\alpha }_i\right)$-t egy $\begin{array}{c}{\displaystyle p\left(x\right)-{\alpha }_i=a_k\cdot \left(x-{\alpha }_{i\mathrm{,1}}\right)\cdot \left(x-{\alpha }_{i\mathrm{,2}}\right)\cdot \text{...}\cdot \left(x-{\alpha }_{i\mathrm{,}k}\right)}\end{array}$ polinommal. A konstrukcióból világos, hogy $p\left({\alpha }_{i\mathrm{,}j}\right)={\alpha }_i$, ezért ${\alpha }_i\ne {\alpha }_{i\text{'}}$ esetén ${\alpha }_{i\mathrm{,}j}\ne {\alpha }_{i\text{'}\mathrm{,}j\text{'}}$ adódik. Azaz $p\left(p\left(x\right)\right)$ kanonikus alakjában egy $\left(x-{\alpha }_{i\mathrm{,}j}\right)$ gyöktényező előfordulásainak száma megegyezik az (1) kanonikus alakjában az $\left(x-{\alpha }_i\right)$ előfordulásai számának és a $p\left(x\right)-{\alpha }_i$ polinom kanonikus alakjában az $\left(x-{\alpha }_{i\mathrm{,}j}\right)$ gyöktényező előfordulásai számának szorzatával. A $p\left(p\left(x\right)\right)=q{\left(x\right)}^2$ azonosság miatt tehát minden ilyen $\left(x-{\alpha }_{i\mathrm{,}j}\right)$ gyöktényező páros sokszor fordul elő $p\left(p\left(x\right)\right)$ kanonikus alakjában. A feladat kérdésére adott igenlő válasz igazolásához elegendő megmutatni, hogy az (1) kanonikus alakban minden $\left(x-{\alpha }_i\right)$ gyöktényező páros sokszor fordul elő. Ezt indirekt módon bizonyítjuk: tegyük fel, hogy valamely $\left(x-{\alpha }_i\right)$ gyöktényező multiplicitása páratlan. Tekintettel arra, hogy a $p\left(p\left(x\right)\right)$ polinom fokszáma $k^2$, és a $p\left(p\left(x\right)\right)=q{\left(x\right)}^2$ azonosság miatt $k^2$ páros, a $p\left(x\right)$ polinom $k$ fokszámának is párosnak kell lennie. Ez viszont azt jelenti, hogy az (1) kanonikus alakban a páratlan multiplicitású gyöktényezők száma páros. Létezik tehát egy ${\alpha }_{i\text{'}}\ne {\alpha }_i$ gyök, amelyre az $\left(x-{\alpha }_{i\text{'}}\right)$ gyöktényező is páratlan sokszor fordul elő az (1) alakban. A fenti megfigyelésünk szerint tehát mind a $p\left(x\right)-{\alpha }_i$, mind a $p\left(x\right)-{\alpha }_{i\text{'}}$ polinomok kanonikus alakja olyan, hogy azokban minden gyöktényező páros sokszor fordul elő. Más szóval, léteznek olyan $r_1\left(x\right)$ és $r_2\left(x\right)$ polinomok, melyekre $\begin{array}{c}{\displaystyle p\left(x\right)-{\alpha }_i=r_1{\left(x\right)}^2\text{és}p\left(x\right)-{\alpha }_{i\text{'}}=r_2{\left(x\right)}^2\mathrm{.}}\end{array}$ (3) Ezek szerint ${\displaystyle \begin{array}{cc}\hfill {\displaystyle {\alpha }_{i\text{'}}-{\alpha }_i}& {\displaystyle =\left(p\left(x\right)-{\alpha }_i\right)-\left(p\left(x\right)-{\alpha }_{i\text{'}}\right)=r_1{\left(x\right)}^2-r_2{\left(x\right)}^2=}\hfill \\ \hfill {\displaystyle }& {\displaystyle =\left(r_1\left(x\right)+r_2\left(x\right)\right)\cdot \left(r_1\left(x\right)-r_2\left(x\right)\right)\mathrm{.}}\hfill \end{array}}$ Azt kaptuk, hogy a bal oldalon található konstans előáll két polinom szorzataként, vagyis mind $r_1\left(x\right)+r_2\left(x\right)$, mind $r_1\left(x\right)-r_2\left(x\right)$ konstans polinomok. Ekkor azonban ezek összege, $r_1\left(x\right)+r_2\left(x\right)+r_1\left(x\right)-r_2\left(x\right)=2\cdot r_1\left(x\right)$ is konstans polinom, tehát (3) alapján $p\left(x\right)=r_1{\left(x\right)}^2-{\alpha }_i$ is konstans, ami ellentmond a kezdeti feltevésünknek. Ezzel pedig kétséget kizáróan igazoltuk a feladat kérdésére adott igenlő választ.  $\square$   II. megoldás. Meg fogjuk mutatni, hogy a megadott feltételek mellett mindig létezik olyan $r$ valós együtthatós polinom, melyre $p\left(x\right)=r{\left(x\right)}^2$. Ha $p\left(p\left(x\right)\right)=q{\left(x\right)}^2$, akkor ${\left(\text{deg}p\right)}^2=2\text{deg}q$, és így a $p$ polinom foka páros. Továbbá $p$ főegyütthatója pozitív, különben a $\infty$-ben $p\left(p\left(x\right)\right)$, és így $q{\left(x\right)}^2$ határértéke is negatív lenne. Legyen tehát $p\left(x\right)=a_{2n}{x}^{2n}+a_{2n-1}{x}^{2n-1}+\text{...}+a_{1}x+a_0$, ahol $n$ nemnegatív egész szám és $a_{2n}>0$. Megmutatjuk hogy léteznek olyan $r$ és $s$ valós együtthatós polinomok, melyekre $p\left(x\right)=r{\left(x\right)}^2+s\left(x\right)$ és $\text{deg}s<n$. Mivel egy ilyen $r$ polinom foka csak $n$ lehet, keressük $r$-et $r\left(x\right)=b_n{x}^n+b_{n-1}{x}^{n-1}+\text{...}+b_{1}x+b_0$ alakban. Akkor kapunk megfelelő előállítást, ha $p\left(x\right)$-ben és $r{\left(x\right)}^2$-ben minden $n\le j\le 2n$-re megegyezik $x^j$ együtthatója. Ha $b_i$ értékét $i=n\mathrm{,}n-\mathrm{1,}\text{...}\mathrm{,0}$ sorrendben választjuk meg, akkor $b_i$ megfelelő választásával elérhető, hogy $x^{n+i}$ együtthatója egyezzen. Legyen ugyanis $b_n=\sqrt[]{a_{2n}}$, ekkor $x^{2n}$ együtthatója egyezik. Tegyük fel, hogy $b_n\mathrm{,}{b}_{n-1}\mathrm{,}\text{...}\mathrm{,}{b}_{i+1}$ értékét már rögzítettük. Mivel $r{\left(x\right)}^2$-ben $x^{n+i}$ együtthatója ${\sum }_{i\le k\le n}{b}_k{b}_{n+i-k}$, így $\begin{array}{c}{\displaystyle b_i=\frac{a_{n+i}-\sum _{i<k<n}^{}{b}_k{b}_{n+i-k}}{2b_n}}\end{array}$ választással $x^{n+i}$ együtthatója éppen $a_{n+i}$ lesz $r{\left(x\right)}^2$-ben is. Az így megválasztott $n$-edfokú $r\left(x\right)$ polinomra valóban $n$-nél kisebb fokú lesz az $s\left(x\right)=p\left(x\right)-r{\left(x\right)}^2$ polinom. Mivel $q{\left(x\right)}^2=p\left(p\left(x\right)\right)=r{\left(p\left(x\right)\right)}^2+s\left(p\left(x\right)\right)$, ezért $\begin{array}{c}{\displaystyle s\left(p\left(x\right)\right)=q{\left(x\right)}^2-r{\left(p\left(x\right)\right)}^2=\left[q\left(x\right)+r\left(p\left(x\right)\right)\right]\cdot \left[q\left(x\right)-r\left(p\left(x\right)\right)\right]\mathrm{.}}\end{array}$ Az $s\left(p\left(x\right)\right)$ polinom foka $s$ és $p$ fokának szorzata, és így kisebb, mint $2n^2$. Ha $s\not\equiv 0$, akkor ebből az is következik, hogy a $q\left(x\right)+r\left(p\left(x\right)\right)$ és $q\left(x\right)-r\left(p\left(x\right)\right)$ polinomok foka is kisebb, mint $2n^2$. Ekkor viszont $\begin{array}{c}{\displaystyle q\left(x\right)=\frac{q\left(x\right)+r\left(p\left(x\right)\right)+q\left(x\right)-r\left(p\left(x\right)\right)}{2}}\end{array}$ foka is $2n^2$-nél kisebb lenne, ami ellentmondás, hiszen $\text{deg}q=\frac{{\left(\text{deg}p\right)}^2}{2}=2n^2$. Mindez azt jelenti, hogy $s\equiv 0$, és így $p\left(x\right)=r{\left(x\right)}^2$. $\square$   Megjegyzés. Williams Kada megjegyzése nyomán könnyen látható, hogy az I. megoldás módszerével igazolható a kitűzött feladat azon általánosítása, mely szerint ha valamely valós együtthatós $p\left(x\right)$ és $q\left(x\right)$ polinomokra, illetve $k\ge 2$ prímszámra $p\left(p\left(x\right)\right)=q{\left(x\right)}^k$ teljesül, akkor van olyan valós együtthatós $r\left(x\right)$ polinom, amelyre $p\left(x\right)=r{\left(x\right)}^k$ áll fenn.