Problem A. 706. (October 2017)

A. 706. Let \(\displaystyle \mathbb{Z}^+\) denote the set of positive integers. Find all functions \(\displaystyle f\colon \mathbb{Z}^+\to\mathbb{Z}^+\) which satisfy the following:

\(\displaystyle \bullet\) \(\displaystyle f(mn)=f(m)f(n)\) for all \(\displaystyle m,n\in\mathbb{Z}^+\), and

\(\displaystyle \bullet\) \(\displaystyle f^{(n)}(n)=n\) for all \(\displaystyle n\in\mathbb{Z}^+\) (in other words, \(\displaystyle f\Big(f\big(\dots \big(f(n)\big)\dots\big)\!\Big)=n\), where there are \(\displaystyle n\) pairs of brackets on the left-hand side).

Korean problem

(5 pont)

Deadline expired on November 10, 2017.

Answer. The only solution is \(\displaystyle f(n)=n\) for all \(\displaystyle n\in\mathbb{Z}^+\).

Claim 1. If \(\displaystyle f(p)=p\) for all primes \(\displaystyle p\), then \(\displaystyle f(n)=n\) for all positive integers \(\displaystyle n\).

Proof. This follows purely from the fact that \(\displaystyle f\) is totally multiplicative. Indeed, \(\displaystyle f(1\cdot 1)=f(1)\cdot f(1)\) and \(\displaystyle f(1)\neq 0\) imply \(\displaystyle f(1)=1\), moreover repeated application of \(\displaystyle f(mn)=f(m)f(n)\) shows that if \(\displaystyle n>1\) has prime factorization \(\displaystyle n=p_1^{\alpha_1}p_2^{\alpha_2}\dots p_k^{\alpha_r}\), then

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

Claim 1 is a direct corollary of these observations. \(\displaystyle \blacksquare\)

Claim 2. Assign to every \(\displaystyle n\in\mathbb{Z}^+\) its orbit:

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

Then if \(\displaystyle f^{(n)}(n)=n\), \(\displaystyle O_n\) is a finite set, and \(\displaystyle |O_n|\) divides \(\displaystyle n\).

Proof. Consider the sequence \(\displaystyle a_0=n\), \(\displaystyle a_1=f(n)\), \(\displaystyle a_2=f(f(n))\), \(\displaystyle \ldots\). Let \(\displaystyle d\) be the minimal positive integer for which there exists a \(\displaystyle k\) with \(\displaystyle a_k=a_{k+d}\) (it exists because \(\displaystyle a_0=a_n\)). Then \(\displaystyle a_{k+1}=a_{k+d+1}\), \(\displaystyle a_{k+2}=a_{k+d+2}\), \(\displaystyle \dots\), \(\displaystyle a_{nk}=a_{nk+d}\).

Since \(\displaystyle f^{(n)}(n)=n\), we get \(\displaystyle n=a_{nk}=a_{nk+d}\), i.e. \(\displaystyle f^{(d)}(n)=n\). This means that \(\displaystyle a_0=a_d\), and so \(\displaystyle a_1=a_{d+1}\) etc., i.e. \(\displaystyle (a_k)\) repeats in periods of length \(\displaystyle d\). Moreover, the minimality of \(\displaystyle d\) shows that the periods \(\displaystyle a_0,a_1,\dots,a_{d-1}\) contain pairwise distinct numbers. All this readily implies \(\displaystyle d|n\) and \(\displaystyle d=|O_n|\). \(\displaystyle \blacksquare\)

Claim 3. For all primes \(\displaystyle p\), \(\displaystyle f(p)=p\).

Proof. By Claim 2, \(\displaystyle |O_p|\) equals \(\displaystyle 1\) or \(\displaystyle p\). If \(\displaystyle |O_p|=1\), then \(\displaystyle f(p)=p\). If \(\displaystyle |O_p|=p\), then for all \(\displaystyle x\in O_p\), we have \(\displaystyle O_x=O_p\), and thus Claim 2 tells us that \(\displaystyle |O_x|=p\) divides \(\displaystyle x\). By multiplicativity, \(\displaystyle p|x\) implies \(\displaystyle f(p)|f(x)\).

Based on these observations, we have the chain of divisors \(\displaystyle p|f(p)|f\big(f^{(p-1)}(p)\big)=p\), which again implies \(\displaystyle f(p)=p\). \(\displaystyle \blacksquare\)

From Claim 1 and Claim 3, \(\displaystyle f(n)=n\) for all \(\displaystyle n\in\mathbb{Z}^+\) (which is indeed a solution).

Statistics:

39 students sent a solution.
5 points:	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 points:	2 students.
0 point:	4 students.

Problems in Mathematics of KöMaL, October 2017