A B. 5012. feladat (2019. február)

B. 5012. Legyen \(\displaystyle f(x)\) egész együtthatós polinom. Jelölje \(\displaystyle f^{(n)}\) az \(\displaystyle f\) függvény \(\displaystyle n\)-szeri alkalmazását:

\(\displaystyle f^{(n)}(x)=\underbrace{f\Big(f\big(\ldots f}_{n}(x)\ldots\big)\!\Big). \)

Jelölje \(\displaystyle k(f)\) a legkisebb olyan \(\displaystyle k\) pozitív egészt, melyre \(\displaystyle f^{(k)}(x)\equiv x\pmod{13}\) teljesül minden \(\displaystyle x\) egész számra, ha létezik ilyen \(\displaystyle k\), és legyen \(\displaystyle k(f)=0\) egyébként. Mutassuk meg, hogy a \(\displaystyle k(f)\) értékek között létezik legnagyobb, és határozzuk meg a maximumot.

(6 pont)

A beküldési határidő 2019. március 11-én LEJÁRT.

Megoldás. Először is, megjegyezzük, hogy ha \(\displaystyle x\) egész szám, akkor az \(\displaystyle f(x)\) szám 13-as maradékát meghatározza az \(\displaystyle x\) szám 13-as maradéka. Továbbá, ha \(\displaystyle k(f)\ne 0\), akkor az \(\displaystyle f(x)\) szám 13-as maradéka bármi lehet, hiszen ha valamelyik maradék nem állna elő, akkor egy ilyen maradékot adó számból indulva nem juthatnánk vissza \(\displaystyle f\) ismételt alkalmazásával ugyanehhez a maradékhoz. Vagyis, ha \(\displaystyle k(f)>0\), akkor \(\displaystyle f\) meghatározza a moduló 13 maradékok egy permutációját: az \(\displaystyle i\) maradék képe az \(\displaystyle f(i)\) szám 13-as maradéka.

A \(\displaystyle k(f)\) szám értéke azt mondja meg, hogy ezt a permutációt hányszor kell alkalmazni, hogy visszajussunk az identikus permutációhoz (aminél minden saját magába képződik). Ezt az értéket a permutáció rendjének nevezzük.

Határozzuk meg tehát, legfeljebb mekkora lehet 13 elem egy permutációjának rendje. Egy permutáció felbontható diszjunkt ciklusok szorzatára (lásd például a B. 4491. feladat megoldását), és könnyen látható, hogy a permutáció rendje éppen a ciklushosszak legkisebb közös többszöröse. (Ugyanis egy \(\displaystyle r\) hosszú ciklus a permutáció minden \(\displaystyle r\)-edik alkalmazása után viszi vissza a helyére a benne szereplő \(\displaystyle r\) elemet). A kérdés tehát az, hogy legfeljebb mekkora lehet néhány pozitív egész szám legkisebb közös többszöröse, ha tudjuk, hogy az összegük 13. Megmutatjuk, hogy a válasz 60, amennyi valóban lehet: \(\displaystyle [1,3,4,5]=60\).

Tegyük fel, hogy a számok \(\displaystyle a_1,a_2,\dots,a_n\), ezek tehát olyan pozitív egészek, melyek összege 13. Megmutatjuk, hogy feltehető, hogy az \(\displaystyle a_1,a_2,\dots,a_n\) számok mindegyike prímhatvány vagy 1. Ehhez elég megmutatni, hogy ha valamely \(\displaystyle a_i\) előáll \(\displaystyle a_i=bc\) alakban, ahol \(\displaystyle b\) és \(\displaystyle c\) relatív prímek (és 1-nél nagyobbak), akkor \(\displaystyle a_i\) lecserélhető \(\displaystyle b\)-re, \(\displaystyle c\)-re és még néhány 1-esre. Először is, \(\displaystyle 0<(b-1)(c-1)\) miatt \(\displaystyle a=bc>b+c\), vagyis \(\displaystyle a_i\)-t 1 darab \(\displaystyle b\)-re, 1 darab \(\displaystyle c\)-re, és \(\displaystyle a-b-c\) darab 1-esre cserélve a számok továbbra is pozitív egészek, és az összeg is változatlan. Ugyanakkor \(\displaystyle (b,c)=1\) alapján azon számok legkisebb közös többszöröse, amikre \(\displaystyle a\)-t lecseréltük továbbra is \(\displaystyle [b,c]=bc=a\), így az összes szám legkisebb közös többszöröse is változatlan.

Ezt a lépést ismételten elvégezve a nem prímhatvány \(\displaystyle a_i\)-kről egyesével leválaszthatjuk a kanonikus felbontásukban szereplő prímhatványokat. (Ha \(\displaystyle a_i=p_1^{\alpha_1}\dots p_r^{\alpha_r}\), akkor először \(\displaystyle p_r^{\alpha_r}\)-et választjuk le, majd \(\displaystyle p_{r-1}^{\alpha_{r-1}}\)-et, és így tovább, az eljárás során 1-esek is keletkeznek.)

Tehát feltehető, hogy mindegyik szám prímhatvány (vagy 1). A szóba jövő prímhatványok: \(\displaystyle 2,3,4,5,7,8,9,11,13\). A legkisebb közös többszöröst jelölje \(\displaystyle m\).

Ha szerepel a 13, akkor más szám nem szerepelhet és \(\displaystyle m=13\).

Ha szerepel a 11, akkor ezen kívül már csak 2-es szerepelhet, így \(\displaystyle m\leq 22\).

Ha szerepel a 9, akkor a többi szám összege 4, így \(\displaystyle m\leq 4\cdot 9=36\).

Ha szerepel a 7, akkor a többi szám összege 6, így \(\displaystyle m\leq \max(7\cdot 5, 7\cdot 4,7\cdot 3\cdot 2)=42\).

Mostantól tegyük fel, hogy \(\displaystyle 7,8,9,11,13\) egyike sem szerepel. Ekkor csak a \(\displaystyle 2,3,5\) prímek hatványai jönnek szóba, méghozza legfeljebb a következő kitevőkkel: \(\displaystyle 2^2,3^1,5^1\), ami meg is valósítható (hiszen \(\displaystyle 1+3+4+5=13\)) és \(\displaystyle m=60\)-at ad.

Tehát 13 elem egy permutációjának rendje legfeljebb 60. Megmutatjuk, hogy bármely permutáció meg is kapható alkalmas \(\displaystyle f\) polinommal, ebből már következik, hogy a feladat kérdésére is 60 a válasz.

Tegyük fel, hogy egy olyan egész együtthatós polinomot keresünk, amelyre \(\displaystyle 0\leq i\leq 12\) esetén a \(\displaystyle p(i)\) szám 13-as maradéka \(\displaystyle a_i\). (Ha ilyen polinomot mindig találunk, akkor speciálisan a permutációknak megfelelő függvényeket is elő tudjuk állítani polinommal.)

Tekintsük először a \(\displaystyle p_0(x)=-(x+1)(x+2)\dots (x+12)\) egész együtthatós polinomot. Ha ebbe 13-mal nem osztható számot helyettesítünk, akkor az eredmény 0, hiszen a \(\displaystyle -1,-2, \dots,-12\) számok minden nemnulla maradékot reprezentálnak. Továbbá a \(\displaystyle p_0(0)\) szám 13-as maradéka 1 a Wilson-tétel alapján (vagy \(\displaystyle 12!=479001600=13\cdot36846277 -1\) szerint). Legyen most \(\displaystyle 1\leq i\leq 12\) és \(\displaystyle p_i(x)=p_0(x-i)\), ez olyan egész együtthatós polinom, amibe \(\displaystyle i\)-t helyettesítve 1 maradékot adó számot kapunk, nem \(\displaystyle i\) maradékot adót helyettesítve pedig 0-t. Vegyük végül a \(\displaystyle p(x)=\sum\limits_{i=0}^{12} a_ip_i(x)\) polinomot, ez egész együtthatós, és a korábbiak alapján \(\displaystyle p(i)\) éppen \(\displaystyle a_i\) maradékot ad 13-mal osztva.

Tehát minden permutáció megvalósítható valamely egész együtthatós polinom segítségével, így speciálisan az is, ahol a ciklusok hossza \(\displaystyle 1,3,4,5\), tehát a \(\displaystyle k(f)\) értékek maximuma 60.

Statisztika:

26 dolgozat érkezett.
6 pontot kapott:	Beke Csongor, Nagy Nándor, Soós 314 Máté, Szabó 991 Kornél, Weisz Máté, Zsigri Bálint.
5 pontot kapott:	Tóth 827 Balázs.
4 pontot kapott:	3 versenyző.
3 pontot kapott:	3 versenyző.
2 pontot kapott:	4 versenyző.
1 pontot kapott:	1 versenyző.
0 pontot kapott:	8 versenyző.

A KöMaL 2019. februári matematika feladatai