Determine all functions $f\colon\mathbb{Z}_{>0}\to\mathbb{Z}_{>0}$ such that, for all positive integers $a$ and $b$, \[ f^{bf(a)}(a+1)=(a+1)f(b). \]
Problem
Source: ISL 2023 N8
Tags: functional equation, IMO Shortlist, Integers
MarkBcc168
17.07.2024 15:08
Not NT . Also not that hard for N8.
The answer is $f(x)\equiv x+1$ only. It clearly works. Now I show it is the only solution.
Claim. $f$ does not cycle: there exists no positive integer $k$ and $x$ such that $f^k(x)=x$.
Proof. Since $(a+1)f(b)$ is unbounded, we can see that $f(\mathbb Z_{>0})$ is unbounded. Hence, for a fixed $a$, we have that $\{(a+1)f(b) : b\in\mathbb Z_{>0}\}$ is infinite, so $f$ does not cycle through $a+1$ for all $a\in\mathbb Z_{>0}$.
It then suffices to show that $f$ does not cycle at $1$. If $f(1)>1$, we are clearly done. Otherwise, $f(1)=1$, so $f^{f(a)}(a+1) = a+1$ for all positive integers $a$, which also leads to a contradiction. $\blacksquare$
Claim. $1\notin f(\mathbb Z_{>0})$.
Proof. Assume $f(t)=1$ for some $t$. Then plugging in $b=t$ into the problem gives contradiction to the previous claim. $\blacksquare$
Claim. $f$ is injective.
Proof. Assume $f(r)=f(s)$ but $r>s$. Then,
$$f^{rf(a)}(a+1) = af(r) = af(s) = f^{sf(a)}(a+1),$$so $f$ cycles, which is a contradiction. $\blacksquare$
The previous three claims show that the directed graph $G$ of $f$ must be a disjoint union of directed paths, note we have not ruled out the case that some of which may be neverending in both directions.
Claim. The directed graph $G$ of $f$ is connected, so it is a single path with an endpoint. In particular, $f(\mathbb Z_{>0}) = \{2,3,\dots\}.$
Proof. For any $a,b\in\mathbb Z_{>0}$, we have $f(a)>1$ by the second claim, so
$$f^{bf(f(a)-1) + 1}(a) = f^{bf(f(a)-1)}\left(f(a)\right)
= f(a)f(b) = f^{af(f(b)-1)+1}(b) \quad (\spadesuit),$$so $a$ and $b$ are in the same connected component. This implies that the graph is indeed connected. Hence, $f(\mathbb Z_{>0})$ omits exactly one number, which must be $1$. $\blacksquare$
We now provide the main argument.
Claim. $f(a-1)$ is divisible by $a$ for all $a\geq 2$.
Proof. From $(\spadesuit)$ in the proof of previous claim, we deduce that in $G$, the distance between $a$ and $b$ is $bf(f(a)-1) - af(f(b)-1)$, which is a multiple of $\gcd(a,b)$. In particular, the distance between $a$ and $f(1)a$, which is $f(a-1)$, must be a multiple of $a$. This deduces the claim. $\blacksquare$
Thus, for all $a\geq 1$, we have $f(a)\geq a+1$. Combining this with the claim that $\operatorname{Im} f$ omits only $1$ gives $f(a)=a+1$ for all $a\in\mathbb Z_{>0}$.
Anzoteh
17.07.2024 15:17
Lemma 1: $f$ is injective.
Denote $N = \{f(n): n = 1, 2, \cdots, \}$.
Note that for all $a, b$,
$(a + 1)f(b)\in N$,
so $N$ is unbounded since $f(b) > 0$.
Next, consider the sequence
$\{a_n\}$ given by $a_n = f^{nf(1)}(2) = 2f(n)$.
Note that $a_{m_1}=a_{m_2}$ for some $m_1<m_2$ implies that $a_{k} = a_{k + (m_2-m_1)}$ for all $k\ge m_1$,
i.e. $a_k$ is eventually periodic (hence bounded).
This would then mean that $\{2f(n)\}$ is also bounded,
which contradicts $N$ is unbounded.
Lemma 2. $N = \{2, 3, 4, \cdots\}$, and that for all $k\ge 1$ we have $k = f^m(1)$ for some $m\ge 0$.
Proof: Next, we show that $1\not\in N$. If $f(n)=1$ for some $n$ then $f^{nf(1)}(2)=2$, i.e. $f^{knf(1)}(2)=2$, and $\{a_n\}$ is periodic, contradiction.
To show the other part,
Consider the relation $\sim$ given by $a\sim b$ if and only if there exists a $k\ge 0$ such that either $f^k(a)=b$ or $f^k(b) = a$;
it's clear that this $\sim$ is reflective and symmetric,
i.e. $a\sim a$, and also $a\sim b\to b\sim a$.
We now claim that $\sim$ is also transitive.
If there is $k, m\ge 0$ such that $f^k(a)=b, f^m(b)=c$,
then $f^{k+m}(a)=c$;
if $f^k(a)=f^m(c)=b$,
w.l.o.g. suppose $k\le m$.
Then by transitivity, $b = f^m(c)=f^{k}(f^{m-k}(c))$,
so by injectivity, $f^{m-k}(c) = a$.
Thus $\sim$ does partition things into equivalene relations.
With this, we note that $k\in N\to \exists b: k=f(b)
\to \forall a: (a+1)f(b)=(a+1)k\in N$.
Let $a_1, a_2\ge 1$ be arbitrary, and let $c_1, c_2$ be such that
$f(c_1)=(a_1+1)f(1)$ and $f(c_2)=(a_2+1)f(1)$.
Then:
\[
f^{c_2f(a_1)}(a_1+1) = (a_1+1)f(c_2)=(a_1+1)(a_2+1)f(1)
=(a_2+1)f(c_1)=f^{c_1f(a_2)}(a_2+1)
\]showing that either there exists $k := k(a_1, a_2)$ such that either $f^k(a_1+1)=a_2+1$ or $f^k(a_2+1)=a_1+1$.
Thus $2, 3, 4, \cdots$ are all in the same group w.r.t. $\sim$.
Now $1, f(1), f(f(1)), \cdots$ are also in the same group w.r.t. $\sim$,
but with $f(1) > 1$,
we see that there is only one equivalence class under $\sim$ here.
Since 1 is not a value of $f$,
it follows that each $k > 1$ can be written as $k = f^m(1)$ for some $m$.
Lemma 3. $f(1) = 2$.
Proof: We claim that there exists a function $g(k)$ such that for all $a\ge 2$ we have $f(ak - 1) = g(k)f(a - 1)$.
Now consider any $a\ge 2, c\ge 1$, we have
\[
f^{bf(af(c) - 1)}(af(c))
=af(c)f(b)
\]Since $f(b)f(c)\ge 4$,
there exists $d$ with $f(d)=f(b)f(c)$,
and satisfies
$f^{df(a - 1)}(a) = af(d)=af(b)f(c)$.
Comparing this with $f^{cf(a-1)}(a)=af(c)$,
and the injectivity of $f$, we have
\[
df(a - 1) = cf(a - 1) + bf(af(c) - 1)
\]i.e. $f(af(c) - 1) = \frac{(d - c)f(a - 1)}{b}$.
If $k=1$ there's nothing to prove (and $g(1)=1$),
otherwise if $k > 1$,
choose $c$ with $f(c)=k$,
Choose $b = 1$ and $d$ such that $f(d) = f(1)k$,
get $f(ak - 1) = (d - c)f(a - 1)$,
so this $g(k) = d - c$ (which is also valid since $d, c$ depends only on $k$ in this case since $f(c)=k$ and $f(d) = f(1)k$).
On the other side, we show that $f(1) = 2$.
Given that each number $n\ge 2$ can be written as $f^k(1)=n$, let $c(n)$ be the number such that $f^{c(n)}(1)=n$,
then $c(f(1))=1$, and by the equation given, $c((a+1)f(b)) - c(a + 1) = bf(a) > 0$ for all $a, b\ge 1$.
Thus $f(1)$ cannot be written in the form $(a+1)f(b)$.
Since $f(b)$ and $a + 1$ each takes all integer values of $\ge 2$,
$(a+1)f(b)$ takes all composite values, $f(1)$ will then have to be a prime.
If $f(1) = p$ is odd,
then we from $f(2k-1) = g(k)f(1)$ we have $f(p)=f^2(1)$ divisible by $p$.
Now take $a = p - 1$, and $b$ such that $p f(b) = f(p)$ (such $p$ exists since $f(p) \neq p$),
and we have $(a + 1)f(b) = f(p) = f^{bf(p - 1)}(p)$,
so $bf(p-1)=1$. This means $b=f(p-1)=1$,
contradicting that $1\not\in N$.
It then follows that $f(1)$ is even and prime, so $f(1) = 2$.
With this, setting $a=b=1$ gives $f^2(2)=2f(1)=4$.
Let $p = f(2)$ with $f(p) = 4$.
Note that $p$ is odd;
otherwise, given that $p\neq 2$ we can find $b$ with $f(b) = \frac{p}{2}$ and setting $a=1$, get $f^{2b}(2)=2f(b) = p$,
which contradicts that $f^n(2)$ is different for each $n\ge 0$
(we note that $2b\neq 1$).
We also have $4 = f(p) = g(2)f(\frac{p - 1}{2})$,
and since $\frac{p-1}{2} < p$ and $f(\frac{p - 1}{2}) > 1$,
we must have $f(\frac{p - 1}{2}) = 2$.
Thus by injectivity of $f$,
$\frac{p - 1}{2} = 1$, giving $p=3$.
Thus in summary we have shown $f(n) = n + 1$ for $n = 1, 2, 3$.
We can now finish off the solution.
Recall that $f(ak-1)=g(k)f(a-1)$; setting $a=k=2$ gives $4=f(3)=g(2)f(1)=2g(2)$,
so $g(2)=2$ and $f(2a-1) = 2f(a - 1)$.
Thus, if, for some $k\ge 2$, we have
$f(n) = n + 1$ for $n=1, \cdots, 2k-1$, then:
\[
f(2k + 1) = 2f(k) = 2(k + 1)\qquad
a = 1; b = k: f^{2k}(2) = f^{kf(1)}(2) = 2f(k) = 2(k + 1)
\]and given our premise, $f^{2k - 2}(2) = 2 + 2k - 2 = 2k$,
so $f^2(2k) = f(2k + 1) = 2(k + 1)$.
It then follows by injectivity of $f$ that $f(2k) = 2k + 1$ and $f(2k + 1) = 2(k + 1)$.
Thus by doing this induction on $k$, we do have $f(n) = n + 1$ for all $n \ge 1$.
math_comb01
17.07.2024 15:22
Easy for its position imo
We claim that $f \equiv x+1$ which works as $\text{LHS}=ab+a+b+1=\text{RHS}$.
Claim 1: $1 \not\in Im(f)$
Proof: Assume $f(c)=1$; $f^{cf(a)}(a+1)=(a+1)$ so $f^{bf(a)+kcf(a)}(a+1)=(a+1)f(b)$ setting $k=1$ gives $f^{bf(a)+cf(a)}(a+1)=(a+1)f(b)$ now set $b \rightarrow b+c$ in orignal eqn to get $f(b)=f(b+c)$ therefore $f$ is periodic with period dividing $c$, but now $a \rightarrow a+c$ yields a contradiction.
Claim 2: There does not exist $k$ $\forall$ $x$ so that $f^k(x)=x$
Proof: Assume that there is an $x,k$ so that $f^k(x)=x$ then by Claim 1, $x > 1$, setting $x \rightarrow x-1$ and $y \rightarrow k$ in the orignal equation yields $f(k)=1$, contradicting Claim 1.
Claim 3: $f$ is injective.
Proof: Assume $f(i)=f(j)$, then $b \rightarrow i,j$ contradicts Claim 2.
Claim 4: All natural numbers occur in the orbit of $1$.
Proof: Consider $a \rightarrow f(1)-1, b \rightarrow b$ and $a \rightarrow f(b)-1, b \rightarrow 1$ to get $f^{bf(f(1)-1)+1}(1) = f^{f(f(b)-1)+1}(b)$ this implies all numbers lie in orbit of $1$ by Claim 1.
As a corollary of the above proof we have, $f^{bf(f(1)-1)-f(f(b)-1)}(1)=b$, call this equation $(1)$.
Claim 5: The orbit of $1$ forms an arithmetic progression.
Proof: Consider the orbit of $1$; $\{1,f(1),f^2(1) \cdots f^k(1) \cdots\}$, subbing $b = f^k(1)$ in $(1)$ yields $$f^k(1)f(f(1)-1)-f(f^{k+1}(1)-1)=k\quad ...(2)$$by injectivity.
Consider $a \rightarrow f(f(b))-1, b \rightarrow b$ and $a \rightarrow f(b)-1, b \rightarrow f(b)$ in the orignal equation to get $$f^{bf(f^2(b)-1)+2}(b) = f^{f(b)f(f(b)-1)+1}(b)$$$$\rightarrow bf(f^2(b)-1)+1 = f(b)f(f(b)-1)$$by injectivity
Subbing $b = f^k(1)$ yields $$f^k(1)f(f^{k+2}(1)-1)+1 = f^{k+1}(1)f(f^{k+1}(1)-1) \quad ... (3)$$, now we use $(2),(3)$ to prove $2f^k(1)=f^{k-1}(1)+f^{k+1}(1)$.
$k=1$
We have $$f(1)f^2(1)f(f(1)-1)-f(1)f(f^3(1)-1)=2f(1)$$$$f(1)f(f^3(1)-1)-f^2(1)f(f^2(1)-1)=-1$$$$\therefore f(1)f^2(1)f(f(1)-1)-f^2(1)f(f^2(1)-1)=2f(1)-1$$$$\therefore f(1)f^2(1)f(f(1)-1)-f^2(1)(f(1)f(f(1)-1)-1) = 2f(1)-1$$$$\therefore f^2(1)+1=2f(1)$$$k \geq 2$
$$f^k(1)f(f^{k+2}(1)-1)+1 = f^{k+1}(1)(f^{k+1}(1)-1)$$$$f^k(1)f^{k+1}(1)f(f(1)-1)-f^k(1)f(f^{k+2}(1)-1)=f^k(1)(k+1)$$by $(3)$ and $(2)$ respectively.
$$\therefore f^k(1)f^{k+1}(1)f(f(1)-1)+1=f^{k+1}(1)(f^{k+1}(1)-1)+f^k(1)(k+1)$$$$ = f^{k+1}(1) (f^k(1)f(f(1)-1)-k)+f^k(1)(k+1)$$$$\therefore 1 =(k+1)f^k(1)- kf^{k+1}(1)$$$$\therefore 1 = (k+2)f^{k+1}(1)-(k+1)f^{k+2}(1)$$Subtracting the above equations yield $f^{k}(1)+f^{k+2}(1) = 2f^{k+1}(1)$, hence the claim follows.
Now, by Claim 4 and Claim 5, we conclude that $f^k(1)=k+1$ or $f(k) = k+1$ and therefore $f(x)=x+1$ $\forall x \in \mathbb{N}.$
EthanWYX2009
17.07.2024 15:26
I don't see any reason it is number theory, and I also don't think this have N8 difficulty, every step is natural.
FEcreater
17.07.2024 15:28
My problem, but I have no idea why it's marked as NT Fact. Though this one was proposed in 2020, it was submitted for IMO 2023. That's because the FE was inspired when I was enjoying my ramen, one of most famous Japanese food ...
megarnie
17.07.2024 15:44
The answer is $\boxed{f(n) = n + 1}$. To see this works, note the LHS becomes $a + 1 + b f(a) = a + 1 + b(a+1) = (a+1)(b+1)$ and the RHS becomes $(a+1)(b+1)$ also. Now we prove it's the only solution. Let $P(a,b)$ be the given assertion. Claim: $f$ has no cycles (as in there exists no $a,b$ with $b > 0$ and $f^b(a) = a$) Proof: Suppose otherwise. First we prove that there exists some $a > 1$ in a cycle of $f$. If not, then $1$ must be in a cycle of $f$. However, for no other numbers to be in this cycle we must have $f(1) = 1$. But then setting $b = 1$ gives $f^{f(a)}(a + 1) = a + 1$, so some number greater than $1$ is in a cycle. Now that we know some $x > 1$ is in a cycle of $f$, let $d$ be the length of this cycle. Comparing $P(a,b)$ and $P(a, b + d)$ gives that $(a+1) f(b) = (a+1) f(b+d)$ (since the LHS stays the same), so $f(b) = f(b + d)$ for any positive integer $b$. Now comparing $P(a, b)$ and $P(a+d, b)$ gives that the LHS stays the same in both assertions, so $(a+1) f(b) = (a + d + 1) f(b)$, absurd. $\square$ Claim: $f$ is injective Proof: If $f(x) = f(y)$, then $f^{x f(a)}(a+1) = f^{y f(a)}(a+1)$ by comparing $P(a,x)$ with $P(a,y)$, and since $f$ has no cycles, $b + x$ must equal $b + y$, so $x = y$. $\square$ Now notice that if $f(b) = 1$ for some $b$, then $P(a,b)$ yields a cycle of $f$, absurd. Hence $f(x) > 1$ for all positive integers $x$. $P(f(a) - 1, b): f^{b f(f(a) - 1) + 1 } (a) = f(a) f(b)$. $P(f(b) - 1, a): f^{af(f(b) - 1) + 1}(b) = f(a)f(b)$. Comparing the two equations gives us \[ f^{b f(f(a) - 1) + 1 } (a) = f^{af(f(b) - 1) + 1}(b) \ \ \ \ \ \ \ \ \ \ (1) \] Claim: Every positive integer greater than $1$ can be written as $f^n(1)$ for some positive integer $n$. Proof: Fix some $a > 1$. We prove that there exists a positive integer $n$ with $f^n(1) = a$. Notice that setting $b = 1$ in $(1)$ gives that \[ f^{ f(f(a) - 1) + 1}(a) = f^{a f(f(1) - 1) + 1} (1) \] Now since $f$ is injective, if we had $f^x(a) = f^y(b)$ for $x \ge y$, we could subtract the "exponents" by $y$ and get $f^{x-y} (a) = f^0(b) = b$. Thus, we have two cases. If $f(f(a) - 1) + 1 \ge a f(f(1) - 1) + 1$, then we have $f^{f(f(a) - 1) - a f(f(1) - 1) }(a) = 1$. If the LHS becomes $f^0(a)$, then we must have $a = 1$. Otherwise, $1$ is in the image of $f$, which is not possible. If $f(f(a) - 1) + 1 < a f(f(1) - 1) + 1$, then we have $f^{af(f(1) - 1) - f(f(a) - 1) } (1) = a$, so choosing $n = af(f(1) - 1) - f(f(a) - 1) $ gives the desired result. $\square$ Now set $b = f^k(a)$ in $(1)$ for some positive integer $k$. We get that \[f^{f^k (a) f(f(a) - 1) + 1} (a) = f^{a f(f^{k + 1}(a) - 1) + 1 + k}(a) \]and since $f$ has no cycles, the "exponents" on both sides must be equal, so \[f^k(a) f(f(a) - 1) = a f(f^{k+1} (a) - 1) + k\] Setting $k = 1$ here gives that $f(f(a) - 1)$ is relatively prime to $a$. Claim: $f^n(a)$ is periodic modulo $a$ with period equal to $a$. Proof: The above equation implies that $f^k(a) f(f(a) - 1) \equiv k \pmod a$. Clearly if $f^x (a) = f^y(a) \pmod a$, then $x \equiv y \pmod a$ by comparing $k = x$ and $k = y$ in the congruence, and if $x\equiv y \pmod a$, then $f^x(a) f(f(a) - 1) = f^y(a) f(f(a) - 1) \pmod a $ so $f^x(a) \equiv f^y(a) \pmod a$ since $\gcd(a, f(f(a) - 1)) = 1$. $\square$ Now consider $P(b, a-1)$ with $P(b + 1, a -1 )$ for any positive integer $a \ge 2$. We see that $f^{b f(a-1) }(a)$ and $f^{(b+1) f(a-1)}(a) $ are multiples of $a$. However, our earlier claim implies that $(b+1) f(a-1) - b f(a-1) = f(a-1)$ is a multiple of $a$, so $a \mid f(a-1)$, and therefore $x + 1 \mid f(x)$ for any positive integer $x$. Claim: $f(x) = x + 1$ for all positive integers $x$ Proof: We prove this by induction on $x$. First we show the base case that $f(1) = 2$. Suppose otherwise. Then since $2 = f^n(1)$ for some positive integer $n$, $2$ is in the image of $f$. If $f(k) = 2$, then $k + 1 \mid f(k) = 2$, so $k = 1$. Now since $3$ is also in the image of $f$, $f(k) = 3$ implies that $k + 1 \mid 3$ and $k \ne 1$, so $f(2) = 3$. Now we suppose it was true for $1, 2, \ldots, t - 1$, so $f(1) = 2, f(2) = 3, \ldots f(t-1) = t$. If $f(c) = t + 1$ ($c$ must exist since $t + 1 = f^n(1)$ for some $n \in \mathbb{N}$), then $c + 1 \mid f(c) = t + 1$, so $c \le t$. However, $f(1), f(2), \ldots, f(t- 1)$ are not equal to $t + 1$, so $f(t) = t + 1$ must hold. Therefore, the induction is complete. $\square$
BarisKoyuncu
17.07.2024 16:04
Firstly, it is easy to see that $f$ is unbounded. Then, since $f(b)$ can be arbitrarily large, the orbit of any integer greater than $1$ is unbounded. Hence, if $t>1$ and $f^x(t)=f^y(t)$, we must have $x=y$. Take any $c$ such that $f(c)=1$. $P(1,c)$ gives us that $f^{…}(2)=2$ so the orbit of $f(2)$ is bounded, contradiction. Clearly, $a+1|f^{f(a)}(a+1)$. Now, comparing $P(f(a)-1, b)$ and $P(f(b)-1, a)$ gives us that $f^{bf(f(a)-1)+1}(a)=f(a)f(b)= f^{af(f(b)-1)+1}(b)$. Put $a=f^c(b)$ to get $bf(f^{c+1}(b)-1)+c=f^c(b)f(f(b)-1)$ for any $b>1$. Choosing $b=a+1$ and $c=f(a)$ yields $a+1|f(a)$. Let $f(a)=(a+1)g(a)$. In particular, $f(x)\ge x+1$. We have $(a+1)f(b)\ge a+1+f(b)\Rightarrow (a+1)(f(b)-1)\ge bf(a)\Rightarrow bg(b)+b-1\ge bg(a)\Rightarrow g(b)\ge g(a)$ for any $a$ and $b$. Thus, $g$ is constant and $f(x)=(x+1)k$. Now, $P(1,1)$ gives us $k=1$ and $f(x)=x+1$.
Marinchoo
17.07.2024 16:24
The only solution is $f(n) = n+1$ for all $n\geq 1$, which can easily be checked to work. From hereon, we'll denote by $P(a,b)$ the assertion of $(a,b)$ into the functional equation. We begin a series of claims: Claim 1. $1\not\in\text{Im}(f)$. Proof: Assume otherwise and let $f(c) = 1$. Plugging in $a=c$, we have that $f^{b}(c+1) = (c+1)f(b)$ and plugging $b=1, 2, \ldots$ consecutively: \begin{align*} f(c+1) &= (c+1)f(1)\\ f^2(c+1) = f((c+1)f(1)) &= (c+1)f(2)\\ f^3(c+1) = f((c+1)f(2)) &= (c+1)f(3)\\ &\vdots \\ f^{c+1} (c+1) = f((c+1)f(c)) &= (c+1)f(c+1). \end{align*}Therefore $(c+1)f(1) = f(c+1) = f((c+1)f(c)) = (c+1)f(c+1)$, and continuing onward, $f(c+2)=f(2)$, and so on, i.e. $f$ is periodic modulo $c$. However, this implies $f$ is bounded from above by some constant $s_0 = \max_{i\leq c} f(i)$, but at the same time if $a>s_0$: \[a<(a+1)f(b)=f^{bf(a)}(a+1) < s_0\]which is a contradiction. Hence, $1\not\in\text{Im}(f)$, as desired. Claim 2. $f$ is injective. Proof: Suppose that there exist $x < y \in\mathbb{N}$ such that $f(x) = f(y)$. Then, comparing $P(1,x)$ and $P(1,y)$ gives: \[f^{xf(1)}(2) = 2f(x) = 2f(y) = f^{yf(1)}(2).\]Therefore, if $N = f^{xf(1)}(2)$, we have $f^{(y-x)f(1)}(N) = N$. As $1\not\in\text{Im}(f)$ we have $N\neq 1$, and we can plug in $a=N-1, b=(y-x)f(1)$: \[f^{(y-x)f(1)f(N-1)}(N) = Nf((y-x)f(1))\Longrightarrow N = Nf((y-x)f(1)) \Longrightarrow f((y-x)f(1)) = 1.\]However, $1\not\in\text{Im}(f)$, so the claim is proved. Claim 3. $f$ is surjective over $\mathbb{N}\backslash\{1\}$, i.e. $\text{Im}(f) = \mathbb{N}\backslash\{1\}$ due to the first claim. Proof: Comparing $P(f(1)-1,b)$ and $P(f(b)-1,1)$ (recall that $f(x) \geq 2$ for all $x\in\mathbb{N}$) for any $b>1$ yields: \[f^{bf(f(1)-1)}(f(1)) = f(1)f(b) = f(b)f(1) = f^{f(b)-1}(f(b))\Longrightarrow f^{bf(f(1)-1)+1}(1) = f^{f(f(b)-1)+1}(b).\]Due to the injectivity of $f$, we can remove iterations of $f$ from both sides $\min(bf(f(1)-1)+1, f(f(b)-1)+1)$ times. However, as $1\not\in\text{Im}(f)$, we must have $bf(f(1)-1) > f(f(b)-1)$ and $f^{bf(f(1)-1)-f(f(b)-1)}(1) = b$. Hence, $b \in \text{Im}(f)$ and moreover, for any $b>1$, there exists a positive integer \[g(b) = bf(f(1)-1) - f(f(b)-1)\]such that $f^{g(b)}(1) = b$. Hence, if we consider the arrow graph of $f$, it's a single path rooted at $1$. Working with the $g(i)$ rather than the $f(i)$ is now logical as we get a nicer structure. For that reason, we define the distance in the arrow graph between $x$ and $y$ as \[d(x,y) = |g(x) - g(y)|.\]With this definition, the original FE is just \[d((a+1)f(b), a+1) = bf(a).\]What follows is something like black magic. We plug and chug: \begin{align*} P(a,b):&\quad g((a+1)f(b)) - g(a+1) = bf(a)\\ P((a+1)f(b)-1, c):&\quad g((a+1)f(b)f(c)) - g((a+1)f(b)) = cf((a+1)f(b)-1). \end{align*}To calculate $g((a+1)f(b)f(c))-g(a+1)$ in another way, we pick $t \in \mathbb{N}$ such that $f(t) = f(b)f(c)$ which exists due to the surjectivity of $f$. We get: \[P(a, t):\quad g((a+1)f(b)f(c)) - g(a+1) = tf(a).\]Therefore, we express $d((a+1)f(b)f(c), a+1)$ in two ways to finally get: \[bf(a) + cf((a+1)f(b)-1) = tf(a).\]Taking $c=1$, we have that $f(a) \mid f((a+1)f(b)-1)$ for all $a$ and $b$. However, note that after dividing by $f(a)$ in the previous equation, we get: \[b+c\cdot\frac{f((a+1)f(b)-1)}{f(a)} = t.\]As $t$ depends only on $b$ and $c$, we get that the ratio \[r_b = \frac{f((a+1)f(b)-1)}{f(a)}\]doesn't depend on $a$. From here, we have: \[b+cr_b=t\Longrightarrow f(b+cr_b) = f(t) = f(b)f(c) = f(c+br_c).\]As $f$ is injective, this is the same as $b+cr_b = c+br_c$, or $r_x = xL+1$ for all $x$ where $L$ is some integer constant. Going back to the definition of $r_x$, we retrieve \[f((a+1)f(b)-1) = (bL+1)f(a)\]Due to the surjectivity, we can plug $a+1=f(z)$ for all $a$, and respectively all $z$, so: \[(zL+1)f(f(b)-1) = f(f(z)f(b)-1) = (bL+1)f(f(z)-1).\]From here, $f(f(x)-1) = k(xL+1)$ for some constant $k$ for all $x\in\mathbb{N}$. As $f(x)-1$ covers all positive integers and $f$ is surjective, we must have $k=1$, and then due to modulo $L$ reasons, $L=1$ as well. Hence, we reach the final form $f(f(x)-1) = x+1$. From here, plugging in $a = f(x) - 1$ into the original functional equation yields: \[f^{b(x+1)+1}(x) = f^{bf(f(x)-1)}(f(x)) \overset{P(f(x)-1,b)}{=} f(x)f(b) = f^{x(b+1)+1}(b).\]Picking $x = b+1$ finishes as: \[f^{b^2+2b+1}(b+1) = f^{b^2+2b+2}(b) \Longrightarrow f(b) = b+1\]due to the injectivity of $f$. With this, we've shown that $f(x) = x+1$ for all $x\in\mathbb{N}$, which works, so the solution is complete.
beepbeep
18.07.2024 17:35
This solution demonstrates the power of $2$. Here is an outline of the key claims: 1.$f$ is injective. 2. All positive integers are in the same chain, starting at $1$. 3. $f(1)=2$. 4. $f(a)=a+1$. Proof: The only solution is $f(a)=a+1$. This can be checked to work. For positive integers $a,b$, call the set $\{f^{na}(b) \mid n\in \mathbb Z_{\ge0}\}$ the $a$-orbit of $b$. First note $f$ is unbounded. Simply take a large value of $a$. Next, note that for any $a\ge 2$, $f^n(a)$ is unbounded as $n$ ranges over $\mathbb N$. Simply take a large $f(b)$, and $(a+1)f(b)$ is in the orbit of $a+1$. Claim: There does not exist $c$ with $f(c)=1$. Now if there was a $c$ with $f(c)=1$, subbing $b=c$ gives $f^{cf(a)}(a+1)=a+1$, producing a cycle. Since there are finitely many values in this cycle, $f$ is bounded in this cycle. Contradiction! Key Claim 1: $f$ is injective. If $f(x)=f(y)$, $$f^{xf(a)}(a+1)=(a+1)f(x)=(a+1)f(y)=f^{yf(a)}(a+1)$$If $x\neq y$ there is a cycle in $f$. Contradiction! Key Claim 2: All positive integers are in a chain, starting from $1$. For $a\neq b$, $P\left(f(a)-1,b\right):$ $f^{bf\left(f(a)-1\right)}(f(a))=f(a)f(b)$ By symmetry, $f^{bf\left(f(a)-1\right)+1}(a)=f^{af\left(f(b)-1\right)+1}(b)$. In particular there exist natural $k,l$ such that $f^{k}(a)=f^{l}(b)$. WLOG $k>l$, then $f^{k-l}(a)=b$. Corollary 2.1: $f$ takes on all positive integers except 1. Corollary 2.2: For any $a\in \mathbb N$, the $f(a)$-orbit of $a+1$ is the set of all multiples of $a+1$. This follows since the $f(a)$-orbit of $a+1$ is precisely all numbers of the form $(a+1)f(b)$, which by surjectivity is all multiples of $a+1$. Key Claim 3: $f(1)=2$. Consider the $k$ such that $f(k)=2$. Note that $k$ must be odd, since if it were even, it would be in the $f(1)$-orbit of $2$ (and so only appear past 2 in the chain). Then $k+1$ is even. Then $f^2(k+1)=f(1)(k+1)$. Since $k+1$ and $f(1)(k+1)$ are both even, they must both appear in the $f(1)$-orbit of $2$. So $f(1)\mid 2$. Since $f(1)>2, f(1)=2. \hfill\Box$ $P(1,b):$ $f^{2b}(2)=2f(b)$ $P\left((f(a)-1,1\right):$ $f^{f(f(a)-1)+1}(a)=2f(a)$ So $f^{f(f(a)-1)+1}(a)=f^{2a}(2)=f^{2a+1}(1)$. Since $1$ is the first in the chain, we have that \[f^{2a-f(f(a)-1)}(1)=a \quad (\clubsuit)\] Key Claim 4: $f(a)=a+1$ for all positive integers $a$. We strong induct on the statement, with the base case $a=1$ already settled. Suppose $f(k-1)=k$ for all $2\le k\le a-1$. Note this also implies $f^{k-1}(1)=k$ for these $k$. Now consider $f(f(a)-1)$. By injectivity, $f(a)\ge a$, so $f(a)-1\ge a-1$, and so $f(f(a)-1)\ge a$ again, by injectivity. But from ($\clubsuit$) note now that $f(f(a)-1)\le a+1$ by injectivity, since $f^k(1)=k+1$ for $0\le k\le a-2$. So $f(f(a)-1)=a$ or $a+1$. Therefore, from ($\clubsuit$), either $f^a(1)=a$ or $f^{a-1}(1)=a$. Suppose $f^a(1)=a$. Then since $f^{a-2}(1)=a-1$, $f^2(a-1)=a$. Then either both, or neither of $a-1$ and $a$ are in the $2$-orbit of $2$. But they have different parity! Therefore, $f^{a-1}(1)=a$, completing the induction.
BlazingMuddy
18.07.2024 22:53
I found an NT-ish solution, but it's very long. Answer. $f(n) = n + 1$ for all $n \in \mathbb{N}$. For convenience, denote $\mathbb{N}_{>1} = \{2, 3, 4, 5, \ldots\}$ and $\mathbb{N}_0 = \{0, 1, 2, \ldots\}$. Claim 1. The orbit $\mathcal{O}_k = \{f^n(k) : n \in \mathbb{N}_0\}$ is infinite for any $k \geq 2$.
Since it contains $f^{b f(k - 1)}(k) = k f(b)$ for any $b \in \mathbb{N}$, it suffices to show that $f$ is bounded. This is clear from the FE, as the image contains $k f(2)$ for any $k > 1$.
In particular, $f^n(k) \neq k$ for any $k \in \mathbb{N}$ and $n > 0$. Claim 2. $f$ is injective.
Suppose that $f(c) = f(d)$ for some $c, d \in \mathbb{N}$. Then
\[ f^{c f(1)}(2) = 2 f(c) = 2 f(d) = f^{d f(1)}(2), \]so either $c = d$ or $f^{k + m}(2) = f^k(2)$ for some $k, m > 0$. But then the sequence $(f^n(2))_{n \geq 0}$ is eventually periodic, and so the orbit $\mathcal{O}_2$ is finite. A contradiction!
From now on, we write $a \to b$ if $f^k(a) = b$ for some $k \in \mathbb{N}_0$. Claim 3. $f(\mathbb{N}) = \mathbb{N}_{>1}$, and for any $b, c \in \mathbb{N}$, we have $b \to c$ or $c \to b$.
First, if $1 \in f(\mathbb{N})$, then $f^{b f(1)}(2) = 2 f(b) = 2$ for some $b \in \mathbb{N}$; a contradiction by Claim 1 again. Thus, for any $c \in \mathbb{N}$, we have $f(c) > 1$.
Now, for any $b, c \in \mathbb{N}$,
\[ f^{b f(f(c) - 1)}(f(c)) = f(b) f(c) = f^{c f(f(b) - 1)}(f(b)), \]so $f(b) \to f(b) f(c)$ and $f(c) \to f(b) f(c)$. By injectivity, $b f(f(c) - 1) > c f(f(b) - 1)$, then $f(c) \to f(b)$; otherwise $f(b) \to f(c)$. By injectivity again, either $b \to c$ or $c \to b$.
Finally, since $1 \notin f(\mathbb{N})$, $b \to 1$ is impossible for any $b \in \mathbb{N}_{>1}$, so $1 \to b$ and thus $b = f^k(1) \in f(\mathbb{N})$ for some $k \in \mathbb{N}$.
Claim 3 can be interpreted as follows: the graph $G = (V = \mathbb{N}, E = \{x \to f(x) : x \in V\})$ is of form \[ 1 \to f(1) \to f^2(1) \to f^3(1) \to \cdots, \]where all the numbers are present exactly once. Define $g : \mathbb{N}_{>1} \to \mathbb{N}_{>1}$ by $g(n) = f(n - 1)$ for all $n \in \mathbb{N}_{>1}$. Combining Claim 2 and Claim 3 implies that $g$ is bijective. This function is central in this solution. Claim 4. For any $x, y \in \mathbb{N}_{>1}$, we have $x \mid y$ if and only if $y = f^b(x)$ for some $b \in \mathbb{N}_0$ with $g(x) \mid b$. In particular, $x \mid f^b(x) \iff g(x) \mid b$, and $x \mid y \implies x \to y$.
By Claim 3, $\{f^{b f(x - 1)}(x) : b \in \mathbb{N}\}$ is precisely the set of multiples of $x$ other than $x$ itself. Thus, $\{f^{b f(x - 1)}(x) : b \in \mathbb{N}_0\}$ is the set of all multiples of $x$, including $x$. Since $f(x - 1) = g(x)$, Claim 4 follows.
Claim 5. For any $x, y \in \mathbb{N}_{>1}$, we have $x \mid y \iff g(x) \mid g(y)$.
If $x \mid y$, by Claim 4, we have $y = f^D(x)$ with $g(x) \mid D$. WLOG assume $y > x$ and $D > 0$. Now for any $b > 0$,
\[ g(y) \mid b \iff y \mid f^b(y) \implies x \mid f^{b + D}(x) \iff g(x) \mid D + b \iff g(x) \mid b. \]Taking $b = g(y)$ implies $g(x) \mid g(y)$.
Now suppose that $g(x) \mid g(y)$. By Claim 4, for any $x \in \mathbb{N}_{>1}$, the non-negative integers $b$ such that $x \mid f^b(1)$ forms an arithmetic progression of difference $g(x)$. Similarly, the non-negative integers $b$ such that $y \mid f^b(1)$ forms an arithmetic progression of difference $g(y)$. Since $g(x) \mid g(y)$ and the two sequences must have a common term (namely, $f^b(1) = xy$ for some $b$), the first progression contains the second one. As $y = f^b(1)$ for some $b$, we get $x \mid y$.
Claim 6. $g$ is completely multiplicative (at least if we extend it to $\mathbb{N}$ by defining $g(1) = 1$.)
Instead of proving by definition, we just bash out $g(n)$ by looking at the factorization of $n$. The proof should only rely on Claim 5 and the fact that $g$ is bijective.
First, for any prime $p$ and $x \in \mathbb{N}_{>1}$, we have
\[ x = g(p) \iff g^{-1}(x) = p \iff g^{-1}(x) \mid p \iff x \mid g(p), \]so $g(p)$ is prime.
Next, we prove that $g(p^k) = g(p)^k$ for any $p$ prime and $k \geq 1$, by induction on $k$. The base case $k = 1$ is trivial. For the induction step, fix $k \geq 2$ and suppose that $g(p^m) = g(p)^m$ for all $m < k$. Then for any $x \in \mathbb{N}_{>1}$,
\[ x \mid g(p^k) \iff g^{-1}(x) \mid p^k \iff (\exists m \leq k, g^{-1}(x) = p^m) \iff (x = g(p^k) \; \lor \; \exists m < k, x = g(p)^m). \]So the proper divisors of $g(p^k)$ are exactly $1, g(p), \ldots, g(p)^{k - 1}$. As $k \geq 2$, any prime divisor of $g(p^k)$ other than $g(p)$ gives too many ($> 1$) extra divisors, so $g(p^k)$ is a power of $g(p)$ and it is easy to see that it has to be $g(p)^k$.
Finally, consider an arbitrary $n \in \mathbb{N}_{>1}$, and factorize it as $n = \prod_i p_i^{k_i}$. We claim that
\[ g(n) = \prod_i g(p_i)^{k_i}. \]Proceed by strong induction on $n$, and assume that $n$ has at least $2$ prime factors. Then for any $x \in \mathbb{N}_{>1}$,
\[ x \mid g(n) \iff g^{-1}(x) \mid n \iff \exists (m_i \leq k_i \forall i) \text{ s.t. } x = g\left(\prod_i p_i^{m_i}\right). \]By induction hypothesis, the proper divisors of $g(n)$ (including $1$) are all of form $\prod_i g(p_i)^{m_i}$, where $m_i \leq k_i$ for all $i$ and one of the inequality is strict. Since $n$ has at least $2$ prime factors, the least common multiple of these proper divisors is $\prod_i g(p_i)^{k_i}$, which is distinct from all of the proper divisors, and thus is equal to $g(n)$.
Recall that the original equality yields $f^{(y - 1) g(x)}(x) = x g(y)$ for all $x, y \in \mathbb{N}_{>1}$. Claim 7. $g \circ g = \text{id}$.
For any $x, y, z > 1$ with $z \geq y$, we have
\[ x g(z) = f^{(z - 1) g(x)}(x) = f^{(z - y) g(x)}(f^{(y - 1) g(x)}(x)) = f^{(z - y) g(x)}(x g(y)). \]Thus, by Claim 5 and Claim 4,
\[ y \mid z \iff x g(y) \mid x g(z) = f^{(z - y) g(x)}(x g(y)) \iff g(x g(y)) \mid (z - y) g(x). \]But $g$ is multiplicative, so this holds iff $g(g(y)) \mid z - y$. Replacing $z$ with $y + z$, we get that $y \mid z \iff g(g(y)) \mid z$, implying $g(g(y)) = y$ for any $y > 1$, as desired.
Now the FE can be changed to $f^{(y - 1) x}(g(x)) = g(x) g(y)$. By symmetry, we get \[ f^{xy - x}(g(x)) = f^{xy - y}(g(y)) \iff f^y(g(x)) = f^x(g(y)) \iff f^{y - x}(g(x)) = g(y) \]for any $y \geq x > 1$. Thus $g(x) \to g(y)$ whenever $x \leq y$; that is, we have \[ g(2) \to g(3) \to g(4) \to \ldots \iff f(1) \to f(2) \to f(3) \to \ldots. \]By injectivity, we get $1 \to 2 \to 3 \to \ldots$; in other words, $f(n) = n + 1$ for any $n \in \mathbb{N}$.
gghx
20.07.2024 09:26
Another way to finish after $f^{bf(f(a)-1)}(a)=f^{af(f(b)-1)}(b)$. Let $d(a,b)$ be the number of $f$s to get from $a$ to $b$ (possibly negative), and let $g(a)=f(f(a)-1)$. Then, $d(a,b)=ag(b)-bg(a)$. Thus, $d(1,a)=d(1,2)+d(2,a)\implies g(a)-ag(1)=g(2)-2g(1)+2g(a)-ag(2)$, so there exists integer constants $S,T$ for which $g(a)=aS+T$. This means that $d(a,b)=ag(b)-bg(a)=(a-b)T$. However, $d(a,b)$ can take any positive integer, hence $T=1$, or $d(a,b)=a-b$. This forces $f(a)=a+1$.
Seungjun_Lee
09.08.2024 19:20
Easy for its position imho. I haven't seen all the solutions carefully, but I think that this solution is somehow different. Maybe my solution shows why this problem is N, but not enough though. Let $P(a,b)$ be the given assertion $f^{bf(a)}(a+1)=(a+1)f(b)$. We will prove that the only possible solution is $f(a) = a+1$ for all positive integers $a$. It is easy to see that $f(a) = a+1$ satisfies the assertion. We will prove that this is the unique solution in series of claims. Claim 1. $f(k) > 1$ for all $k \in \mathbb{Z}_{>0}$. Also, $f$ is unbounded. Assume that there exists a positive integer $t$ that $f(t) = 1$. From $P(t,b)$, we can obtain that $$f^b(t+1) = (t+1)f(b)$$Now, when $b = t$, we have that $f^t(t+1) = t+1$, and this means that the orbit $$\mathcal{O} : t+1, f(t+1), f(f(t+1)), \cdots$$is periodic. Therefore, since $f^b(t+1)$ is $b$th term of a periodic sequence $\mathcal{O}$, we obtain that $(t+1)f(b)$ is periodic for $b > 0$. Therefore, $f$ is periodic, and this implies that $f$ is bounded above. However, from $P(a,t)$, we get that $$f^{tf(a)}(a+1) = a+1 \implies \mathbb{Z}_{>1} \subset f(\mathbb{Z}_{>0})$$which is a clear contradiction. Hence, $f(k) > 1$ for all $k > 0$ and $f$ is unbounded. Claim 2. $f^k(a) \neq f^{\ell}(a)$ for any $k \neq \ell$ for $k, \ell \in \mathbb{Z}_{>0}$ Assume that $f^k(a) = f^{\ell}(a)$ for some positive integers $a,k, \ell$. We consider the orbit $$\mathcal{O}_a : a, f(a), f(f(a)), \cdots$$which is eventually periodic since it copies itself until $k$th term to $\ell - 1$th term. (Here, we consider $a$ to be the zeroth term, and we assume without loss of generality that $\ell > k$.) Then, since the $f(a)$th, $2f(a)$th, .... terms also form an eventually periodic sequence, $f$ is bounded above, and this is absurd. Hence, there exists no $a,k,\ell$ that $f^k(a) = f^{\ell}(a)$ except $k = \ell$. Claim 3. $\gcd(a,f^k(a)) \mid \gcd(a,k)$ Since $f(a) > 1$ for any $a > 0$ from Claim 1, we can see that $f(a) - 1 \in \mathbb{Z}_{>0}$. From $P(f(a)-1,b)$, we can get that $$f^{bf(f(a)-1) + 1}(a) = f^{bf(f(a)-1)}(f(a)) = f(a)f(b) \qquad \cdots (\star)$$Since the right hand side is symmetric with respect to $a$ and $b$, we can see the following equality. $$f^{bf(f(a)-1) + 1}(a) = f^{af(f(b)-1) + 1}(b) \qquad \cdots (*)$$Now, plug in $b = f^k(a)$ on $(*)$ to get $$f^{f^k(a)f(f(a)-1) + 1}(a) = f^{af(f^{k+1}(a)-1) + 1+k}(a)$$From Claim 2, we directly get that $$f^k(a)f(f(a)-1) = af(f^{k+1}(a)-1) +k$$Here, we can see that $\gcd(f^k(a),a) \mid \gcd(a,k)$ right away. Claim 4. $a+1 \mid f(a)$ for all positive integers $a$. Since $a+1 \mid f^{bf(a)}(a+1)$, from Claim 3, we get that $$a+1 = \gcd(a+1, f^{bf(a)}(a+1)) \mid \gcd(a+1, bf(a))$$for any positive integer $b$. Now, from $b = 1$, we can easily get that $a+1 \mid f(a)$. Claim 5. $f(a) = a+1$ for all positive integers $a$. Now, we will use the equation $(\star)$ above, which is $$f^{bf(f(a)-1) + 1}(a) = f(a)f(b)$$Assume that $a \ge 2$. Here, from Claim 4, we obtain that $\gcd(a,f(a)) = \gcd(a,1) = 1$. Then, $$\gcd(a,f^{bf(f(a)-1) + 1}(a)) = \gcd(a,f(a)f(b)) = \gcd(a,f(b))$$From Claim 3, one can see that $$\gcd(a,f(b)) \mid \gcd(a,bf(f(a)-1) + 1)$$Plug in $b = a-1 \in \mathbb{Z}_{>0}$ to get $$a = \gcd(a,f(a-1)) \mid \gcd(a,(a-1)f(f(a)-1) + 1)$$From Claim 4. Then, $a \mid (a-1)f(f(a)-1) + 1$ which means that $a \mid f(f(a) - 1) - 1$ for all $a > 1$. This obviously also holds for $a = 1$. Now $\gcd(a,bf(f(a)-1) + 1) = \gcd(a,b+1)$ for any positive integers $a,b$. Using this result, we obtain that $$\gcd(a,f(b)) \mid \gcd(a,b+1)$$Substitute $a = (b+1)f(b)$ to get $f(b) \mid b+1$ for any $b \in \mathbb{Z}_{>0}$. Combining this with Claim 4, we finally get that $f(a) = a+1$ for all $a \in \mathbb{Z}_{>0}$.
PHSH
11.08.2024 19:16
We claim $f(n) = n+1$ is the only solution. A simple computation show it works. We now show it is unique. Call problem condition $P(a,b)$. We start with some simple observations Let $a$ be a positive integer and define the orbit of $a$ as $O_a = \{a,f(a),f(f(a)), \dots \}$. We claim the following Claim 1: $O_a$ is infinite for $a \ge 2$
Assume for the sake of contradiction otherwise, then $f^n(a)$ is bounded and then so is the image of $f$ as
$$f(b) = \dfrac{f^{bf(a-1)}(a)}{a} $$by $P(a-1,b).$ But this is an absurd since by $P(n,b)$ we have
$$ f^{bf(n)}(n+1) = (n+1)f(b)$$and as we can take arbritrary $n$ it follows that the image of $f$ is unbounded.
By Claim 1 we have then two corollaries.
Indeed, if $f(b)=f(c)$ with $ b \ne c$ then by $P(a,b), P(a,c)$ we have that $O_{a+1}$ would eventually have period $(b-c)f(a)$ which contradicts Claim 1.
If $\exists b \in {\mathbb{Z}}_{>0}$ with $f(b)= 1$ then $P(a,b)$ contradicts Claim 1 (as $a+1$ would appear again in the orbit of $a+1$).
We now prove the following key step Claim 2: $O_1= {\mathbb{Z}}_{>0}.$
Let $d= f(1)$. We start by observing that by our condition, if $t$ is on the image of $f$ then so is $nt$ for all $n \in {\mathbb{Z}}_{>0}.$ Now let $v \in {\mathbb{Z}}_{>0};$ We will show that $v \in O_1 .$ If $v=1,d$ we are done, else note that by our previous observation we have that $d^2,dv$ are both on the image of $f.$
So let $p,q$ with $f(p)= dv$ and $f(q)=d^2.$ Then by $P(d-1,p), P(v-1,q)$ we have that
$$ f^{pf(d-1)}(d) = d^2v = f^{qf(v-1)}(v)
$$and so as $f$ is injective, either $v\in O_d$ or $d \in O_v$. Where the former is impossible as $v \ne 1,d$ and $ 1 $ is not on the image of $f$ by corollary 2. So $v \in O_d \subset O_1$.
We know introduce the following notation, let $f^{-1}(n)$ as usual for $n \ge 2$ (Which exists by Claim 2). Also, for $n \in {\mathbb{Z}}_{>0}$ denote by $g(n)$ the unique positive integer such that $f^{g(n)}(1) = n$ which is well defined for all $n \ge 2$ by Claim 2. We now read $P(a,b)$ in terms of $g$. That is $$ g((a+1)f(b)) = bf(a) +g(a+1) $$equivalently, for all $b \ge 2$ $$ g((a+1)b) = f^{-1}(b)f(a) +g(a+1) ~~(*) $$We shall use the latter to prove the following Claim 3: Given a fixed positive integer $p$, the ratio $\dfrac{f(np -1)}{f(n-1)}$ is constant for all $n \ge 2$.
Let $u=f^{-1}(rp), v = f^{-1}(p) $ for some arbitrary positive integer r.
Let $n\ge 2$ be a positive integer then by $P(n-1,p)$ we have
$$ f^{uf(n-1)}(n)=rpn $$similarly by $P(n-1),v$ we have that
$$ f^{vf(n-1)}(n) =pn $$
this implies that
$$(u-v)f(n-1) = g(rpn)-g(pn) $$but note that by $(*)$ the RHS equals to $f^{-1}(r)f(np -1)$;plugging that on the above equation implies That
$$ \dfrac{f(np -1 )}{f(n-1)} = \dfrac{u-v}{f^{-1}(r)} = \dfrac{f^{-1}(rp) - f^{-1}(p)}{f^{-1}(r)}$$
desired result as $p,r$ are inrelated to $n.$
Therefore, for all $p \ge 2$ there exists some integer constant $C_p$ such that $ f(np-1) = C_p f(n-1)$ for all $n \ge 2.$ We now compute $C_p.$ First note that as $f$ is surjective on the integers greater than 2, $C_p$ must be an integer. We now are going to apply, $P$ two times, first $P(a, n-1_)$ implies $$ f^{(n-1)f(a)} = (a+1)f(n-1)$$secondly, $P(a,np-1)$ we have $$ f^{(np-1)f(a)} = (a+1)f(np-1)$$it then follows that $$ g((a+1)f(np-1)) - g((a+1)f(n-1))= f(a)n(p-1) $$On the other hand, by Claim 3, we have that $f(np-1):f(n-1) =C_p$ and as $C_p$ is an integer it follows by $(*)$ that the LHS equals $$ f^{-1}(C_p)f((a+1)f(n-1)-1) $$comparing both means $$ f^{-1}(C_p)f((a+1)f(n-1)-1) = f(a)n(p-1) \iff$$$$ f^{-1}(C_p) \cdot C_{f(n-1)}= n(p-1)~~(**)$$As $n$ and $p$ are unrelated, the later implies that there is a fixed constant $k$ such that $f^{-1}(C_p)= k(p-1) $; as $p$ can be any positve integer, it follows $k$ should be an integer. On the other hand, by $(**) $ it follows that $k \mid n, ~\forall n \ge 2$ and so $k =1.$ This than means $C_p =f(p-1).$ But by $(*)$ we also have that $$n = C_{f(n-1)} \Rightarrow n = f(f(n-1)-1), ~ \forall n \ge 2 ~~(***)$$We are now able to finish; by $P(a,f(b)-1)$ it follows by $(***)$ that $$ f^{f(a)f(b) -f(a)}(a+1)= (a+1)(b+1)$$and then as the RHS is symmetric in $a,b$ $$ g(a+1) - g(b+1) = f(a) - f(b)$$Now let $m\ge 2$ be a positive integer then by definiton $$g(f(m)) - g(m) = 1 $$and then by the above relation we have that this means $$f(f(m)-1) - f(m-1) = 1 $$but by $(***)$ this is equivalent to $$ m+1 - f(m-1) = 1 \iff f(m-1) = m , ~\forall m\ge 2$$and we are done.
The first thing you do are the observations that $f$ should be injective and it can't assume value $1$, then you observe that if some number is on the image then any multiple of this number is as well. Then if you try to play with that you happen to be able to make any two distinct numbers have a common term in their orbits. So all elements should be in the same orbit.
This means $f$ is almost surjective, and it also induces the definition of functions $f^{-1}$ and $g$. Then you try to play with $g$ and multiples, and you magically happen to fall into Claim 3, after that you are basically done.
I found this one good. Of course, it does not have any NT flavor. I wish there were some nice real nt problems in this years ISL
motannoir
26.08.2024 11:04
Very nice problem,and also my first N8! The answer is $\boxed{f(x)=x+1}$ for every $x\in \mathbb{Z}_{>0}$ The proof goes as follows: Claim 1:$f$ is injective Proof:Suppose $f(b)=f(c)$.Then we have: $$f^{bf(a)}(a+1)=f^{cf(a)}(a+1)$$But if WLOG $b<c$ then $f^{x}(a+1)$ loops meaning is bounded.But his image contains $(a+1)f(z)$ with $z\in \mathbb{Z}_{>0}$ meaning $f$ is bounded.But of course this is contradiction since his image contains $f(1)\cdot c$ where $c$ is any positive integer and so $f$ is unbounded $\blacksquare$ Claim 2: for any positive integer $x$;$f(x)\ge 2$ Proof:Suppose that for some $x$ $f(x)=1$.Then by $P(a,x+1)$ and $P(a,x)$ we have: $$f^{(x+1)f(a)}(a+1)=(a+1)f(x+1)$$and $$f^{xf(a)}(a+1)=(a+1)$$Meaning $f^{f(a)}(a+1)=(a+1)f(1)=(a+1)f(x+1)$ and by injectivity we have $x=0$,false $\blacksquare$ Claim 3:for every $a\ge 2$ we have $a=f^{af(f(1)-1)-f(f(a)-1)}(1)$ in particular $Im f=\{2,3,4,...\}$. Proof:plug $a\to f(a)-1$ and swap $a,b$.We have : $$f^{bf(f(a)-1)+1}(a)=f^{af(f(b)-1)+1}(b)$$.(*) Plug in this $b=1$ and $a\ge 2$.Since $1$ is not in the image of $f$ and $a\neq 1$ the conlcusion follows $\blacksquare$ Claim 4:There exist constant $c_1,c_2$ such that $f(f(a)-1)=c_1a+c_2$ Proof:In the relation (*) plug the formula for $a$ and $b$ from claim 3 and we have : $$bf(f(a)-1)+af(f(1)-1)-f(f(a)-1)=af(f(b)-1)+bf(f(1)-1)-f(f(b)-1)$$.Plug in this $b=2$ and the conclusion follows.$\blacksquare$ Claim 5:$f(x)=x+1$ for every $x$ Proof:as a corolary from claims 3,4 we get that : $a=f^{c_3a+c_4}(1)$.Plugging in the hyphothesis: $$ f^{bf(a)+c_3(a+1)+c_4}(1)=f^{c_3(a+1)f(b)+c_4}(1)$$so we get that $c_3(a+1)(f(b)-1)=bf(a)$ by plugging $b=10$ we get $f(x)=(x+1)\lambda$ and comparing coefficients we get $\lambda=c_3=1$ meaning $f(x)=x+1$ for every positive integer $x$ We are done !
Cali.Math
17.11.2024 22:40
We uploaded our solution https://calimath.org/pdf/ISL2023-N8.pdf on youtube https://youtu.be/Bl0ycdJLoT0.
ihategeo_1969
03.12.2024 12:13
Nice problem but I have two problems with it as Mark also mentioned. $\bullet$ Not really NT (actually not at all). $\bullet$ Pretty standard for an X$8$. So all in all, it should be like A$5$ or something. We will change the variables because why not. Quote: Determine all functions $f\colon\mathbb{Z}_{>0}\to\mathbb{Z}_{>0}$ such that, for all positive integers $m$ and $n$, \[ f^{nf(m)}(m+1)=(m+1)f(n). \] Let $P(m,n)$ denote the assertion and also let $G_f$ denote the digraph of this function $f$. Claim: $f$ is unbounded. Proof: Obvious. $\square$ Claim: $f(n) \geq 2$. Proof: Say $f(c)=1$. Then $P(c,n)$ gives us \[f^n(c+1)=(c+1)f(n) \implies f((c+1)f(n))=f^{n+1}(c+1)=(c+1)f(n+1)\]Put $n=c$ and we get $c=0$, contradiction. $\square$ Claim: $G_f$ has no cycles. Proof: Say $f^k(d)=d$. Now obviously $d \geq 2$ and hence $P(d-1,k)$ gives us \[d=f^{kf(d-1)}(d)=df(k) \implies f(k)=1\]which is a contradiction to our second claim. $\square$ Claim: $f$ is injective. Proof: Say $f(a)=f(b)$ with $b>a$. Now $P(m,a)$, $P(m,b)$ and some simple induction gives us \[f^{af(m)}(m+1)=f^{bf(m)}(m+1)=f^{[K(b-a)+a]f(m)}(m+1)\]for any $K \geq 0$. This means that $G_f$ has a cycle and we are contraducting the third claim. $\square$ Hence $G_f$ is just a disjoint union of chain(s). Claim: $G_f$ has only one chain which contains all natural numbers, starting with $1$. Proof: By $P(f(1)-1,n)$ and $P(f(n)-1,1)$ gives us \[f^{f(f(n)-1)}(n)=f^{nf(f(1)-1)}(1) \iff f^{nf(f(1)-1)-f(f(n)-1)}(1)=n\]This shows $\text{Im}(f)=\{2,3,\dots\}$ and that $G_f$ is connected (so it has one chain). The fact that it starts with $1$ is obvious as $f^{-1}(1)$ does not exist. $\square$ Let $g(m,n)$ be the unique number for which $f^{g(m,n)}(m)=n$. Claim: $\gcd(m,n) \mid g(m,n)$. Proof: $P(f(m)-1,n)$ and $P(f(n)-1,m)$ gives us \[f^{nf(f(m)-1)}(m)=f^{mf(f(n)-1)}(n) \iff f^{nf(f(m)-1)-mf(f(n)-1)}(m)=n\]And hence we get that $g(m,n)=nf(f(m)-1)-mf(f(n)-1)$ and the result follows. $\square$ Claim: $n+1 \mid f(n)$ and in particular we have $f(n) \geq n+1$. Proof: $P(n,1)$ gives us \[f^{f(n)}(n+1)=(n+1)f(1) \implies g(n+1,(n+1)f(1))=f(n)\]and hence $n+1 \mid f(n)$. $\square$ So simple induction gives us $\boxed{f(n) \equiv n+1 \text{ } \forall \text{ } n \in \mathbb{N}}$. This obviously works.