WisFaq!

Bewijs met polynoom

Hoi, kunnen jullie me een tip geven bij deze vraag?

Zij P(x) een polynoom van graad n 1 met gehele coëfficiënten
en zij k een positief geheel getal (k 0). Beschouw het polynoom
Q(x) = P(P(. . . P(P(x)) . . .)),
waarin P precies k keer voorkomt.
Bewijs dat er ten hoogste n gehele getallen t zijn zodanig dat Q(t) = t.

Alvast bedankt.

Kevin
26-10-2007

Antwoord

Beste Kevin,
Als ik het goed begrijp gaat het om een recursieve functie.
De recursie vergelijking is dan:
u(t)=P(u(t-1))
Je zou hiervan een web-grafiek kunnen tekenen.
Na k stappen moet je dan op de lijn u(t)=u(t-1) uitkomen.
Als de grafiek van de polynoom de lijn y=x snijdt zal de uitkomst van u(n) niet meer veranderen.
Als P(t)=t geldt dan ook Q(t)=t en zijn er precies evenveel oplossingen als snijpunten van het polynoom met de lijn y=x. We weten dat dat er maximaal n zijn.

Ik had de vraag niet goed gelezen. Dankzij collega cl heb ik verder gezocht wat er gebeurt als als P(t) niet gelijk is aan t:

Je kan bewijzen dat van een polynoom met gehele coefficienten geldt:P(a)-P(b) is deelbaar door a-b.
Als we beginnen met x=x₀, en P(x₀)=x₁, P(x₁)=P(P(x₀)=x₂, enz., dan krijg je de rij:
x₀,x₁,x₂,....xk=x₀
Bekijk ook de rij
x₀-x₁, x₁-x₂, ....,xk-x(k+1) =x₀-P(x₀),P(x₀)-P(x₁),...
Elke term is een deler van de daar op volgende term:
c1·c2·c3·..·(x₀-x₁)=xk-x(k+1)=x₀-x₁
De laatste term is weer gelijk aan de eerste, zodat volgt dat c1·c2·c3·....=1. Al die factoren zijn dus 1 of -1.
In de rij x₀,x₁,x₂,....,x(m-1),xm,x(m+1),....
is xm de kleinste van de rij.
Dan geldt: x(m-1)-x(m)>0 en x(m)-x(m+1)<0 . Dan volgt:
x(m-1)-x(m)=-(x(m)-x(m+1)), zodat x(m-1)=x(m+1)
Het blijkt nu dat de rij x₀,x₁,x₂,... een alternerende rij is: a,b,a,b,a,b,.... of: c,d,c,d,...
Nu geldt:
c-a=P(d)-P(b)=c1·(d-b)
d-b=P(c)-P(a)=c2·(c-a)
c-b=P(d)-P(a)=c3·(d-a)
d-a=P(c)-P(b)=c4·(c-b)
Net als bij de rij van de verschillen van de x-waarden geldt hier ook dat c1·c2·c3·c4=1, dus alle factoren zij 1 of -1.
Dus c-b=d-a of a-d en c-a=d-b of b-d.
Dit combineren geeft a=b, maar dan geldt P(a)=a, of a+b=c+d.
Dan geldt: a+b-c-c=0, of a+b-c-P(c)=0
P(c) is een polynoom van graad n, dus a+b-c-P(c) ook.
Die vergelijking heeft dus maximaal n oplossingen voor c.
En dat wilden we toch bewijzen!

Almet al niet zo eenvoudig!
Zie ook:
http://imo2006.dmfa.si/imo2006-solutions.pdf

ldr
28-10-2007