Feladat: B.3609 Korcsoport: 16-17 Nehézségi fok: átlagos
Megoldó(k):  Backhausz Ágnes ,  Baráth Géza ,  Bartha Emőke ,  Bednay Dezső ,  Bérczi Kristóf ,  Birkus Róbert ,  Csajbók Bence ,  Czank Tamás ,  Farkas Balázs ,  Fehér Gábor ,  Hartmann Zoltán ,  Hubai Tamás ,  Jankó Zsuzsanna ,  Kiss-Tóth Christián ,  Korotij Ágnes ,  Kovács Dóra Judit ,  Kovács Péter ,  Kurgyis Zsuzsanna ,  Pálinkás Csaba ,  Pongrácz András ,  Salát Máté ,  Sándor Ágnes ,  Sándor Nóra Katalin ,  Simon Balázs ,  Szilvási Tibor ,  Tábor Áron ,  Torma Róbert ,  Vaskó Richárd 
Füzet: 2004/február, 84 - 85. oldal  PDF file
Témakör(ök): Polinomok oszthatósága, Teljes indukció módszere, Feladat
Hivatkozás(ok):Feladatok: 2003/január: B.3609

Van-e olyan f(x) egész együtthatós 2003-ad fokú polinom, amelyre bármely n egész szám esetén az
f(n),f(f(n)),f(f(f(n))),...
értékek páronként relatív prímek?

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.

I. megoldás. Megmutatjuk, hogy létezik a megfelelő tulajdonságú polinom. Adott f(x) polinomra jelölje a k-szorosan összetett f(f(...f(x)...)) polinomot fk(x). Ekkor elegendő, ha tetszőleges k-ra m és fk(m) minden m egészre relatív prímek, hiszen a feladat sorozatának bármely két tagja ilyen alakú.
Ha m=f(0), a polinom konstans tagja, akkor f(m) többszöröse m-nek. Ha a konstans tagot 1-nek választjuk, akkor ezzel annyit legalábbis elérünk, hogy (m;f(m))=1 teljesüljön minden m egészre, mégpedig úgy, hogy f(m)=qm+1, ahol q egész szám.
Nézzük meg, mit kapunk, ha az M=qm+1 értéket helyettesítjük, azaz f(f(m))=f(M) értékét számoljuk ki. Ha i>0, akkor a binomiális tétel szerint (qm+1)i=q'm+1, ahol q' is egész szám. Tetszőleges egész együtthatós f(x)=anxn+an-1xn-1+...+a0 polinomra tehát f(M)=Qm+an+an-1+...+a1+a0, ahol Q egész szám. Ha tehát a polinom együtthatóinak az összegét, az f(1) értéket is 1-nek választjuk, akkor M=qm+1-ből f(M)=mQ+1 következik. Innen pedig indukcióval nyomban adódik, hogy minden k-ra fk(m)=mQk+1, ahol Qk egész szám.
Ilyenkor pedig m és fk(m) valóban relatív prímek.
Feltételünk tehát f(0)=f(1)=1, ez pedig nyilván minden legalább másodfokú polinomra teljesíthető, egy 2003-adfokú megoldás f(x)=x2003-x+1.

 
II. megoldás. Használjuk az előző megoldás jelöléseit. Ismeretes, hogy ha f(x) egész együtthatós polinom, m és n pedig tetszőleges egész számok, akkor m-nf(m)-f(n), azaz mf(m)-f(0) és m-1f(m)-f(1). Ha f(0)=f(1)=1, akkor innen
mf(m)-1,illetve(1)m-1f(m)-1(2)
adódik.
Ha most (2)-ben m helyére f(m)-et írunk, akkor f(m)-1f(f(m))-1, amit (1)-gyel összevetve mf(f(m))-1, ahonnan teljes indukcióval mfk(m)-1 adódik minden pozitív egész k-ra. Ez pedig azt jelenti, hogy m és fk(m) minden k-ra relatív prímek, amiből az első megoldás bevezetőjében mondottak szerint következik a megkövetelt tulajdonság.
f(0)=f(1)=1 pontosan akkor teljesül, ha x(x-1)f(x)-1, azaz f(x)=g(x)x(x-1)+1, ahol g(x) tetszőleges egész együtthatós polinom.
A keresett polinom fokszámára vonatkozó feltétel pedig nyilván teljesül, ha g(x) tetszőleges 2001-edfokú polinom. Az is látszik, hogy a legalább másodfokú polinomok között mindig található a megadott tulajdonságú.