Problem B. 5012. (February 2019)
B. 5012. Let \(\displaystyle f(x)\) be a polynomial with integer coefficients. Let \(\displaystyle f^{(n)}\) denote the \(\displaystyle n\)-fold application of \(\displaystyle f\):
\(\displaystyle f^{(n)}(x)=\underbrace{f\Big(f\big(\ldots f}_{n}(x)\ldots\big)\!\Big). \)
Let \(\displaystyle k(f)\) denote the smallest positive integer \(\displaystyle k\) for which \(\displaystyle f^{(k)}(x)\equiv x\pmod{13}\) holds for all integers \(\displaystyle x\), provided that there exists such a \(\displaystyle k\), and let \(\displaystyle k(f)=0\) otherwise. Prove that there is a maximum value of \(\displaystyle k(f)\), and determine this maximum value.
(6 pont)
Deadline expired on March 11, 2019.
Sorry, the solution is available only in Hungarian. Google translation
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.
Statistics:
26 students sent a solution. 6 points: Beke Csongor, Nagy Nándor, Soós 314 Máté, Szabó 991 Kornél, Weisz Máté, Zsigri Bálint. 5 points: Tóth 827 Balázs. 4 points: 3 students. 3 points: 3 students. 2 points: 4 students. 1 point: 1 student. 0 point: 8 students.
Problems in Mathematics of KöMaL, February 2019