Az A. 706. feladat (2017. október)

A. 706. Jelölje \(\displaystyle \mathbb{Z}^+\) a pozitív egészek halmazát. Határozzuk meg az összes olyan \(\displaystyle f\colon \mathbb{Z}^+\to\mathbb{Z}^+\) függvényt, melyre a következők teljesülnek:

\(\displaystyle \bullet\) \(\displaystyle f(mn)=f(m)f(n)\) minden \(\displaystyle m,n\in\mathbb{Z}^+\)-ra, illetve

\(\displaystyle \bullet\) \(\displaystyle f^{(n)}(n)=n\) minden \(\displaystyle n\in\mathbb{Z}^+\)-ra (azaz \(\displaystyle f\Big(f\big(\ldots\big(f(n)\big)\dots\big)\!\Big)=n\), ahol a zárójelpárok száma \(\displaystyle n\)).

Koreai feladat

(5 pont)

A beküldési határidő 2017. november 10-én LEJÁRT.

Válasz. Az egyetlen megoldás: \(\displaystyle f(n)=n\) minden \(\displaystyle n\in \mathbb{Z}^+\)-ra.

1. állítás. Ha \(\displaystyle f(p)=p\) minden \(\displaystyle p\) prímszámra, akkor \(\displaystyle f(n)=n\) minden \(\displaystyle n\) pozitív egészre.

Bizonyítás. Ez következik pusztán abból, hogy \(\displaystyle f\) totálisan multiplikatív. Ugyanis \(\displaystyle f(1\cdot 1)=f(1)\cdot f(1)\) és \(\displaystyle f(1)\neq 0\) miatt \(\displaystyle f(1)=1\), továbbá az \(\displaystyle f(mn)=f(m)f(n)\) feltétel sokszori alkalmazásából adódik, hogy ha \(\displaystyle n>1\) prímfelbontása \(\displaystyle n=p_1^{\alpha_1}p_2^{\alpha_2}\dots p_k^{\alpha_r}\), akkor

\(\displaystyle f(n)=f(p_1)^{\alpha_1}f(p_2)^{\alpha_2}\dots f(p_k)^{\alpha_k}.\)

Az állítás ezen megfigyelések azonnali következménye. \(\displaystyle \blacksquare\)

2. állítás. Minden \(\displaystyle n\in\mathbb{Z}^+\)-hoz rendeljük hozzá az orbitját:

\(\displaystyle O_n:=\{n,f(n),f(f(n)),\dots,f^{(k)}(n),\dots\}.\)

Ekkor \(\displaystyle f^{(n)}(n)=n\) esetén \(\displaystyle O_n\) véges halmaz, és \(\displaystyle |O_n|\) osztója \(\displaystyle n\)-nek.

Bizonyítás. Tekintsük az \(\displaystyle a_0=n\), \(\displaystyle a_1=f(n)\), \(\displaystyle a_2=f(f(n))\), \(\displaystyle \ldots\) sorozatot. Legyen \(\displaystyle d\) a legkisebb olyan pozitív egész, melyhez \(\displaystyle a_{k+d}=a_{k}\) valamilyen \(\displaystyle k\)-ra (ami \(\displaystyle a_n=a_0\) okán létezik). Ekkor \(\displaystyle f\)-et a két oldalra alkalmazva, \(\displaystyle a_{k+d+\ell}=a_{k+\ell}\) adódik \(\displaystyle \ell=1,2,\dots\)-ra.

Mivel \(\displaystyle f^{(n)}(n)=n\), ezért \(\displaystyle a_{nk}=n\), s így \(\displaystyle a_{nk+d}=a_{nk}\) miatt \(\displaystyle f^{(d)}(n)=n\). Ezért \(\displaystyle a_0=a_d\), és így \(\displaystyle a_1=a_{d+1}\) stb., azaz \(\displaystyle (a_k)\) sorozat \(\displaystyle d\) hosszú periódusokban ismétlődik. Továbbá \(\displaystyle d\) minimalitása miatt az ismétlődő \(\displaystyle a_0,a_1,\dots,a_{d-1}\) periódusok páronként különböző számokat tartalmaznak. Ebből \(\displaystyle d|n\) és \(\displaystyle d=|O_n|\) adódik. \(\displaystyle \blacksquare\)

3. állítás. Minden \(\displaystyle p\) prímszámra \(\displaystyle f(p)=p\).

Bizonyítás. A 2. állítás szerint \(\displaystyle |O_p|\) értéke \(\displaystyle 1\) vagy \(\displaystyle p\). Hogyha \(\displaystyle |O_p|=1\), akkor \(\displaystyle f(p)=p\). Ha azonban \(\displaystyle |O_p|=p\), akkor mivel \(\displaystyle x\in O_p\) esetén \(\displaystyle O_x=O_p\), így a 2. állítás szerint \(\displaystyle |O_x|=p\) osztja \(\displaystyle x\)-et. Multiplikativitás miatt \(\displaystyle p|x\)-ből \(\displaystyle f(p)|f(x)\) következik.

Ezek alapján felírható a \(\displaystyle p|f(p)|f\big(f^{(p-1)}(p)\big)=p\) osztólánc, amiből ismét \(\displaystyle f(p)=p\) következik. \(\displaystyle \blacksquare\)

Az 1. és 3. állításból kapjuk, hogy \(\displaystyle f(n)=n\) minden \(\displaystyle n\) pozitív egészre (ami valóban megoldás is).

Statisztika:

39 dolgozat érkezett.
5 pontot kapott:	Beke Csongor, Bukva Balázs, Bursics Balázs, Csóka Zoárd, Daróczi Sándor, Dobák Dániel, Döbröntei Dávid Bence, Füredi Erik Benjámin, Gáspár Attila, Győrffy Ágoston, Hanics Mihály, Imolay András, Janzer Orsolya Lili, Kerekes Anna, Keresztfalvi Bálint, Matolcsi Dávid, Molnár Bálint, Molnár-Sáska Zoltán, Nagy Nándor, Németh 123 Balázs, Póta Balázs, Saár Patrik, Schrettner Jakab, Simon Dániel Gábor, Sulán Ádám, Szabó 417 Dávid, Szabó Kristóf, Tiszay Ádám, Tóth 827 Balázs, Várkonyi Zsombor, Weisz Máté, Záhorský Ákos, Zólomy Kristóf.
3 pontot kapott:	2 versenyző.
0 pontot kapott:	4 versenyző.

A KöMaL 2017. októberi matematika feladatai