veelterm

Opgave - IMO 2006 dag 2 vraag 2

Zij $P(x)$ een veelterm van graad $n>1$ met gehele coëfficiënten en $k$ is strikt natuurlijk. We beschouwen de veelterm $Q(x)=P(P( \cdots P(x)))\cdots)$ waarin $P$ k keer voorkwam. Bewijs dat er maximaal $n$ gehele getallen bestaan waarvoor geldt dat $Q(t)=t.$

Oplossing

Wat een leuke vraag! :)

Lemma. Gegeven een veelterm $P(x)$ die aan bovenstaande eisen voldoet, en bovendien $\begin{cases} P(a)=b \\ P(b)=c \\ P(c)=a \end{cases}$ met $a,b,c$ gehele getallen, dan is $a=b=c$.

Bewijs: er volgt dat $\forall x\in\mathbb{Z}$ dat $\begin{cases} x-a\mid P(x)-b \\ x-b\mid P(x)-c \\ x-c\mid P(x)-a \end{cases}$. Door enkele strategische waarden voor $x$ in te vullen zien we dat $\begin{cases} c-a\mid a-b \\ a-b\mid b-c \\ b-c\mid c-a \end{cases}$
Dus $c-a\mid a-b \mid b-c \mid c-a$, waaruit volgt dat al deze getallen een gelijke absolute waarde hebben. Omdat minstens twee van $c-a, a-b, b-c$ een gelijk teken hebben, kunnen we WLOG stellen $c-a=a-b=\pm(b-c)$. Deze twee gevallen nakijken geeft twee keer $a=b=c$. Tot zover het lemma.

In het bijzonder impliceert dit lemma dat $P(P(P(x)))=x$ aesa $P(x)=x$
(Noteer voor het gemak: $P^k(x)=P(P(P\dots P(x))\dots))$). Dit heeft twee sterke gevolgen: $P^{2m+1}(x)=x$ aesa $P(x)=x$ en voor het even geval: $P^{2m}(x)=x$ aesa $P(P(x))=x$!

voor het oneven geval zijn we dus al klaar, want een veelterm in de ring $\mathbb{Z}[x]$ hebben hoogstens $n$ nulpunten, waar $n$ de graad is van de veelterm, dus dat geldt dan ook voor de veelterm $P(x)-x$, met graad $n$, zoals gewild.

Voor $k$ even, moeten we bewijzen dat de veelterm $P(P(x)-x$ hoogstens $n$ nulpunten heeft. Merk al allereerst op dat als $t$ een nulpunt is, dan is $P(t)$ er ook ééntje: $P(P(P(t))-P(t)=P(t)-P(t)=0$.

Veronderstel nu dat we drie gehelen $a,b,c$ hebben zodat $P(P(a))=P(b)=a$, $P(c)=c$ en $a \ne b \ne c \ne a$. Dan, $\forall x \in \mathbb{Z}$: $\begin{cases} x-a\mid p(x)-b \\ x-b\mid p(x)-a \end{cases}$. Vul $x=c$ in: $c-a\mid c-b \mid c-a $ waardoor $c-a=\pm(c-b)$. Maar daar kan geen $+$ staan want anders zou $a=b$, dus $c-a=-c+b$, dus $c=\frac12(a+b)$. (*) Dit betekent dat, als er zo'n paartje $(a,b)$ bestaat, er maximaal één getal $c$ kan bestaan met de eigenschap dat $P(c)=c$. maw, maximaal één wortel van $P(P(x))-x$ is ook een wortel van $P(x)-x$. echter, alle wortels van $P(x)-x$ zijn ook wortels van $P(P(x))-x$, en dus hebben we een contradictie als $P(x)-x$ meer dan één geheel nulpunt heeft, er bestaat dan geen zo'n paartje $(a,b)$. Dit impliceert dat we gewoon weer de vergelijking $P(x)=x$ zijn aan het oplossen, die wederom maximaal $n$ gehele wortels heeft.

We hebben tenslotte het geval waar $P(x)-x$ geen of één gehele wortel heeft.
We weten dat als we $m$ paartjes $(a_1,b_1),(a_2,b_2),\dots (a_m,b_m)$ hebben zoals hierboven beschreven, dat dan $a_i+b_i=a_j+b_j$ uit (*). dan heeft de veelterm $P(x)-(a_i+b_i-x)$ $m$ wortels, zodat $n\geq m$ zoals gewild. (dit werkt ook voor als er één zo'n $c$ bestaat: zeg $c=a_{m}=b_{m}$ zodat die veelterm weeral maximaal $m$ wortels heeft, zoals gewild.)

QED