Let $\mathbb N$ denote the set of positive integers, and for a function $f$, let $f^k(n)$ denote the function $f$ applied $k$ times. Call a function $f : \mathbb N \to \mathbb N$ saturated if \[ f^{f^{f(n)}(n)}(n) = n \] for every positive integer $n$. Find all positive integers $m$ for which the following holds: every saturated function $f$ satisfies $f^{2014}(m) = m$. Proposed by Evan Chen
Problem
Source: ELMO 2014 Shortlist N4, by Evan Chen
Tags: function, number theory proposed, number theory
26.07.2014 11:12
I really like this problem! We will prove that $f^{2014}(m) = m$ if and only if $m|2014$. Firstly, note that $f$ is surjective as the right hand side of the equation is simply $n$ which can be any positive integer. Now assume that there exist positive integers $a,b,c$ such that $f(a)=f(b)=c$. Then we can show that $f^{f^{f(a)}(a)}(a) = f^{f^{f(b)}(b)}(b) = f^{f^{c-1}(c)-1}(c) \implies a=b$ so $f$ is injective. Thus $f$ is bijective. Let $f(k)=l$ for some positive integers $k,l$ and let $n=k$ in the given equation. \[ f^{f^{f(k)}(k)}(k) = k \implies f^{f^{l}(k)}(k) = k \implies f^{f^{l-1}(l)}(k) = k \implies f^{f^{l-1}(l)}(l) = l. \] (at the last equality we did $f$ of both sides) Now assume that for some positive integer $a$, $f^{f^{a}(l)}(l)=l$ (*). By letting $n=f^{a-1}(l)$, we obtain \[ f^{f^{f^{a}(l)}(f^{a-1}(l))}(f^{a-1}(l)) \implies f^{f^{a-1}(l)}(f^{a-1}(l))=f^{a-1}(l) \implies f^{f^{a-1}(l)}(l)=l. \] (we used injectivity at the last step). We can continue this process of reducing $a$ until $a=0$. Thus $f^{l}(l)=l$ (1) for all positive integers $l$. Now if $l=1$ in (1) then $f(1)=1$ so (*) must hold for all $a$. Assume that $l>1$. Then from earlier work we have that (*) holds for $a=l-1 \geq 1$. In all cases, (*) holds for some $a\geq 1$ so when we repeatedly perform the reducing $a$ operation, we we will eventually pass by $a=1$. So $f^{f(l)}(l)=l$. (2) It is easy to show that (1) and (2) combined are equivalent to the original equation. If $m|2014$ then by letting $l=m$ in (1) we can obtain $f^{2014}(m)=m$. If $m$ is not a factor of $2014$, let $f(n)=n$ for $n \in \mathbb{N}$ but not in $\{m, 2m, \cdots, m^2\}$, $f(im)=im$ for $i \in \{1,2, \cdots, m-1\}$, and $f(m^2)=m$. Then we easily verify that $f$ satisfies both (1) and (2) but $f^{2014}(m) \neq m$.
26.07.2014 19:18
leminscate wrote: I really like this problem! Thanks and yes, that's basically my solution too. This ended up losing to N5 in the vote-count, but N5 is nice enough that I have no hard feelings
31.07.2014 10:43
Very nice! It is clear from the question that we can split the natural numbers into cycles, and each element only appear once (can use bijective argument from leminscate). Now suppose we have a cycle $a_i$ of length $m$ such that $f(a_i)=a_{i+1}$ for $i=1$ to $m$ (where $a_k=a_l$ iff $k\equiv l(mod m)$). Hence we get $a_i= f^{f^{f(a_i)}(a_i)}(a_i)=a_{i+f^{f(a_i)}(a_i)=}$${a_{i+a_{i+a_{i+1}}}\Rightarrow m|a_{i+a_{i+1}}}$ for all $i$. WLOG $m|a_m$. Then note that $m|a_{i+1}\Rightarrow m|a_i$, so $m|a_i$ for all $i$. Now we get that divisors of $2014$ must belong to a cycle of length divisible by themselves, and so they work. For any number other than the divisors (for example $m$ which does not divide $2014$). Define $f$ as follow: Let $f(im)=(i+1)m$ for $i=1$ to $m-1$, and $f(m^2)=m$. For any other number $n$, $f(n)=n$. It is easy to check that this works, and hence we are done.
13.04.2015 08:30
$f$ is clearly a bijection. Let $ n $ be in a cycle of length $m$, then $m|f^{f(n)}(n)$. Let $f(n)=x$ then $m|f^{x-1}(x)$, and clearly this is true for all $x$ in a cycle of length $m$. Let $y=f^{x-1}(x)$, then the length of the cycle of $y$ ($m$) divides $y$. But $m|f^{y-1}(y)=f^{-1}(y)$ and inductively we see $m$ divides all the numbers in the cycle. Similarly, if we have a bijection $f$ where every cycle-length divides every number in the cycle, then a number $n$ in a cycle of length $m$ satisfies $m|f(n),n \Rightarrow f^{f(n)}(n)=n$ and so $m|f^{f(n)}(n)$ and so the original equation is satisfied. Therefore, a function is saturated iff every cycle-length divides every number in the cycle. Now clearly if $m|2014$ then $m$ works by what we just proved. If $m$ doesn't divide $2014$ then place $m$ in an $m$-cycle, say $m,2m,...,m^2$, and all other number in a $1$-cycle to find an $f$ that contradicts.
01.09.2015 20:38
Congratulations for such a great problem v_Enhance! I was wondering, this problem was N6 on the 2013 ELMO shortlist (so harder than ELMO #3 2013) and N4 on the 2014 ELMO shortlist (so easier than ELMO #2 2014). Is the ELMO shortlist based on difficulty? How difficult is this problem? Thanks!
02.09.2015 01:50
Also, what is the motivation for the function $f$ when $m$ does not divide 2014? Thanks again for all your help!
04.09.2015 01:05
MathPanda1 wrote: Is the ELMO shortlist based on difficulty? How difficult is this problem? Thanks! Only very loosely. It's not unusual for the difficulty of shortlist numbers to be off by 1 or 2 positions. MathPanda1 wrote: Also, what is the motivation for the function $f$ when $m$ does not divide 2014? Thanks again for all your help! In the proof that $f^{2014}(m) = m$ for all $m \mid 2014$, you basically show that the only restriction on $f$ is that each element divides the length of its cycle. So tons of constructions work for the other guys.
04.09.2015 01:40
So what would be its difficulty?
01.05.2019 03:31
We claim that the set of $m$ is the set of divisors of $2014$. Let $P(n)$ denote the given assertion. Obviously $f$ is bijective. Let $n$ be an integer. Let $g(n)$ be the smallest positive integer $k$ such that $f^k(n) = n$. Since $g(n) \leq f^{f(n)}(n)$, it is necessarily finite. Now, fix a positive integer $n$. Let $\ell = f(n)$. From $P(n)$, we have \begin{align*} f^{f^\ell(n)}(n) &= n. \end{align*}From $P\left(f^{\ell - 1}(n)\right)$, we have \begin{align*} f^{f^{f\left(f^{\ell - 1}(n)\right)}\left(f^{\ell - 1}(n)\right)}\left(f^{\ell - 1}(n)\right) &= f^{\ell - 1}(n) \\ f^{f^{f^\ell(n)}\left(f^{\ell - 1}(n)\right)}\left(f^{\ell - 1}(n)\right) &= f^{\ell - 1}(n). \end{align*}Then, \begin{align*} f^{f^\ell(n)}(n) &= n \\ f^{\ell - 1}\left(f^{f^\ell(n)}(n)\right) &= f^{\ell - 1}(n) \\ f^{f^\ell(n)}\left(f^{\ell - 1}(n)\right) &= f^{\ell - 1}(n). \end{align*}Hence, \begin{align*} f^{f^{f^\ell(n)}\left(f^{\ell - 1}(n)\right)}\left(f^{\ell - 1}(n)\right) &= f^{\ell - 1}(n) \\ f^{f^{\ell - 1}(n)}\left(f^{\ell - 1}(n)\right) &= f^{\ell - 1}(n). \end{align*}By injectivity, \begin{align*} f^{f^{\ell - 1}(n)}(n) &= n. \end{align*}Repeating this argument $\ell - 1$ more times (with $P\left(f^{\ell - 2}(n)\right), \ldots, P\left(n\right)$), we find that \begin{align*} f^{f^{0}(n)}(n) &= n \\ f^n(n) &= n. \end{align*}Therefore, $g(n) \mid n$. This is enough to imply that for $m \mid 2014$, $f^{2014}(m) = m$. It is not hard to find a function $f$ that shows these are all such $m$. $\Box$
14.06.2020 09:35
let $a_n$ be the smallest integer such that $f^{a_n}(n)=n$ claim: $a_n | n$ proof: note that $a_n=a_{f(n)}=a_{f^r(n)}$ since $a_n | f^{f(n)}(n)$ so we have $a_n=a_{f^{f(n-1)}(n)} | f^{f(n)+f^{f(n)}(n)}(n) \implies a_n | f^{f^{f(n)}(n)}(n)=n$ $\blacksquare$ so $m | 2014$
10.09.2020 15:11
JuanOrtiz wrote: $f$ is clearly a bijection. Let $ n $ be in a cycle of length $m$, then $m|f^{f(n)}(n)$. Let $f(n)=x$ then $m|f^{x-1}(x)$, and clearly this is true for all $x$ in a cycle of length $m$. Let $y=f^{x-1}(x)$, then the length of the cycle of $y$ ($m$) divides $y$. But $m|f^{y-1}(y)=f^{-1}(y)$ and inductively we see $m$ divides all the numbers in the cycle. Similarly, if we have a bijection $f$ where every cycle-length divides every number in the cycle, then a number $n$ in a cycle of length $m$ satisfies $m|f(n),n \Rightarrow f^{f(n)}(n)=n$ and so $m|f^{f(n)}(n)$ and so the original equation is satisfied. Therefore, a function is saturated iff every cycle-length divides every number in the cycle. Now clearly if $m|2014$ then $m$ works by what we just proved. If $m$ doesn't divide $2014$ then place $m$ in an $m$-cycle, say $m,2m,...,m^2$, and all other number in a $1$-cycle to find an $f$ that contradicts. Why does $f^{y-1}(y)=f^{-1}(y)$?
19.12.2020 07:41
Surprisingly simple! Let $G$ be the directed graph induced by $f.$ Since there exists $i$ such that $f^{i}(n)=n$ for all $n,$ all vertices are contained in cycles, and thus all cycles are disjoint. Consider a cycle of length $m$ in $G.$ Label the vertices of the cycle $a_1,a_2,\dots,a_m$ in clockwise order. The FE is equivalent to the system $$a_{1+a_2}\equiv 0\pmod{m},$$$$a_{2+a_{3}}\equiv 0\pmod{m}$$$$\vdots$$$$a_{m+a_{1}}\equiv 0\pmod{m}.$$Obviously, these equations imply that there exists $k$ such that $a_k\equiv 0\pmod{m}.$ But then it is easy to see (by, say, induction) that all $a_i$ must be $0$ modulo $m.$ This clearly satisfies the equation, so we have characterized all saturated $f.$ Now it follows that the answer is $\boxed{\text{all factors of }2014}.$
28.12.2020 21:45
Nice problem! The answer is factors of $2014$, namely \[1,2,19,53,38,106,1007,2014\]First, we will show that nonfactors of $2014$ fails. If $m$ wasn't a factor of $2014$, then let $f(m) = 2m, f(2m) = 3m, \ldots f(m^{2} - m) = m^{2}, f(m^{2}) = m$. Let $S$ be the set $\{m, 2m, \ldots m^{2}\}$ For all other integers $x$ that is not in $S$, just let $f(x) = x$. For all integers not in $S$, $f$ satisfies the condition. To show that it satisfies the conditions for integers in $S$, we have \[f^{f^{f(km)}(km)}(km) = f^{f^{(k+1)m}(km)}(km) = f^{km}(km) = km\]for $k\neq m$, where the intermediate steps follow because $f^{rm}(km) = km$ since $f^{m}(km) = km$. For $k = m$, we have \[f^{f^{f(m^{2})}(m^{2})}(m^{2}) = f^{f^{m}(m^{2})}(m^{2}) = f^{m^{2}}(m^{2}) = m^{2}\]which implies $f$ satisfies the condition for all integers in $S$ as well, and it thus satisfies for all integers. However, since $m$ is not a factor of $2014$, this means \[f^{2014}(m) = f^{2014\mod m}(m) \neq m\] Now we will prove all factors of $2014$ will result in $f^{2014}(m) = m$. For such an $m$, let $k$ be the smallest integer such that $f^{k}(m) = m$. This must exist since $k\leq f^{f(m)}(m)$. Now, I claim $f$ is bijective. To prove injectivity, if $f(a) = f(b)$, then \[a = f^{f^{f(a)}(a)}(a) = f^{f^{f(b)-1}(f(a))}(a) = f^{f^{f(b)}(b) - 1}(f(b)) = f^{f^{f(b)}(b)}(b) = b\]To prove surjectivity, we have for every $n$, take $x = f^{f^{f(n)}-1}(n)$, then $f(x) = n$. Thus, $f$ is a bijective function. Now, consider a graph of the natural numbers, and draw an arrow going from $x$ to $f(x)$. This means $k$ is the length of the cycle containing $m$. Since $k$ is the length of this cycle, by our condition, we must have \[k | f^{f(m)}(m)\]This is some number in our cycle. Denote $n = f^{f(m)}(m)$, so $k | n$. Next, I claim $k | f^{-1}(n)$. This is because \[k | f^{f(f^{-1}(n))}(f^{-1}(n)) = f^{n}(f^{-1}(n)) = f^{k\cdot \frac{n}{k}}(f^{-1}(n)) = f^{-1}(n)\]Now we can prove $k | f^{-1}(f^{-1}(n)) = f^{-2}(n)$. In general, we can show that if $k | f^{-i}(n)$, then $k | f^{-i+1}(n)$, so by induction, $k$ divides all the numbers in this cycle. Thus, $k | m$ as well. Since $m$ is a factor of $2014$, it means $k$ is also a factor of $2014$, so $k | 2014$. Thus, after $2014$ iterations, we must be back at $m$, so $f^{2014}(m) = m$ for all factors of $2014$.
04.03.2021 09:45
ELMO SL 2013 wrote: Let $\mathbb{N}$ denote the set of positive integers, and for a function $f$, let $f^k(n)$ denote the function $f$ applied $k$ times. Call a function $f: \mathbb{N} \to \mathbb{N}$ $\textit{saturated}$ if \[ f^{f^{f(n)}(n)}(n) = n \]for every positive integer $n$. Find all positive integers $m$ for which the following holds: every saturated function $f$ satisfies $f^{2014}(m) = m$. Fabulous problem! The answer is any $\boxed{m \mid 2014}$. Let $P(n)$ be the assertion of $n$ to the given functional equation. Claim 01. $f$ is bijective. Proof. $f$ is obviously surjective. Now notice that if $f(a) = f(b)$, then $f^{f(a)}(a) \ge 1$ and $f^{f(b)}(b) \ge 1$. Furthermore, they are the same value by assumption since $f(a) = f(b)$. Therefore, this forces $a = b$. Claim 02. $f^{f^{n - 1}(n)}(n) = n$ for any $n \in \mathbb{N}$. Proof. Since $f$ is bijective, $f^{-1}(n)$ exists for all $n \in \mathbb{N}$. $P(f^{-1}(n))$ gives the desired claim. Now, let $G$ be the directed graph (loop is allowed) representation of the problem, where all natural numbers are denoted as vertices and connect $a \mapsto f(a)$ for every $a \in \mathbb{N}$. Claim 03. Every vertices in $G$ has exactly one inner edge, and one outer edge. Proof. By the definition of a function, every vertices has exactly one outer edge. By injectivity, every vertices has exactly one inner edge. Furthermore, this implies that every vertices in $G$ is a part of a cycle of length $\ell \ge 1$, that is, divide the infinite graph $G$ into its connected components: $C_1, C_2, \dots$ Then all of $C_i$s are circuit graph. Now, take any $C_i$ for some $i \in \mathbb{N}$. Claim 04. Every element $v$ in a circuit $C_i$ where $\ell$ is the length of the circuit must satisfies $\ell \mid v$. Proof. For our purposes, let $\ell \ge 2$ and let the vertices on the circuit be $v_1, \dots, v_{\ell}$, such that $f(v_n) = v_{n + 1}$ for all $1 \le n \le \ell$ and indices are considered modulo $\ell$. We know that from Claim 02 that \[ f^{f^{v_i - 1}(v_i)}(v_i) = v_i \]By our definition of $\ell$, this must satisfies $\ell \mid f^{v_i - 1}(v_i)$. Since $f^{v_i - 1}(v_i) = v_j$ for some $1 \le j \le \ell$. Then, we conclude that there exists a vertex in the circuit which is divisible by $\ell$. Let it be $v_w$. Using Claim 02 again, we have \[ f^{f^{-1}(v_w)}(v_w) = v_w \Rightarrow \ell \mid f^{-1}(v_w) = v_{w - 1} \]Continuing this process, we conclude that $\ell \mid v_i$ for all $1 \le i \le \ell$. From Claim 04, then if $v_i$ is in a circuit of length $\ell$, then $\ell \mid v_i$. The problem asks us to identify all natural numbers $m$ such that whatever $G$ (or $f$) is, then $m$ must have a circuit of length $\ell \mid 2014$. Necessity. First of all, we prove that any $m \mid 2014$ satisfies our requirement. Indeed, suppose $m$ lies on a circuit of length $\ell$, then we have \[ \ell \mid m \mid 2014 \]which is what we wanted. Sufficiency. Now, we'll construct a graph $G$ such that $f^{2014}(m) = m$ if and only if $m \mid 2014$. Consider the following algorithm starting from the set $A_0 = \mathbb{N}$. Starting from the set $A_i$, take the minimal element of $A_i$ (let it be $a_i$) which must exists due to Well-Ordering Principle. Construct a cycle of length $a_i$, with its vertices being $a_i$ multiples of $a_i$ that are still in the set $A_i$. Let $A_{i + 1} = A_i \setminus V_i$, where $V_i$ is the set of all numbers that has been taken by this process. First of all, this function satisfies the problem condition, as if we suppose that $\ell_n$ is the length of cycle that contains $n$, we have $\ell_n \mid f^{f(n)}(n)$ by our algorithm, and therefore \[ f^{f^{f(n)}(n)}(n) = n, \ \forall n \in \mathbb{N} \]From here, notice that $i$ must lie on cycle of length $i$ by definition for $i = 1, 2, 1007$ and $2014$ could lie on cycle $2, 1007$ or $2014$, and we have proven the "if" direction. For the other direction, notice that if the length of the cycle is $\ell$, then $\ell \mid 2014$. However, this means $a_i$(or $\ell$) has to be $2, 1007$ or $2014$. We could just take: \[ (2,4), (1007, 1007 \cdot 2, 1007 \cdot 3, \dots, 1007^2) \ \text{and} \ (2,8), (1007,1007 \cdot 2, 1007^2 \cdot 3, 1007^2 \cdot 4, \dots, 1007^3) \]for the cycle of length $2$ and $1007$ and we are hence done.
05.06.2021 22:04
Let $f^0(n)=n$, and $f^k(n)=f\left(f^{k-1}(n)\right)$ $(\{k,n\}\subset\mathbb N)$. Let $P(n)$ be the assertion $f^{f^{f(n)}(n)}(n)=n$. Easily, $f$ is bijective, so let $Q(n)=P\left(f^{-1}(n)\right):f^{f^{n-1}(n)}(n)=n$. We will now prove by induction that $f^{f^k(n)}(n)=n$ for all $k\in\mathbb N_0,n\in\mathbb N$ and $k<n$. The base case is $Q(n)$, now assume that $f^{f^k(n)}(n)=n$ for some $k\in\mathbb N$. We will show that $f^{f^{k-1}(n)}(n)=n$. Indeed, we have: \begin{align*} P\left(f^{k-1}(n)\right)&\Rightarrow f^{f^{f\left(f^{k-1}(n)\right)}\left(f^{k-1}(n)\right)}\left(f^{k-1}(n)\right)=f^{k-1}(n)\\ &\Rightarrow f^{k-1}\left(f^{f^{f^k(n)}\left(f^{k-1}(n)\right)}(n)\right)=f^{k-1}(n)\\ &\Rightarrow f^{f^{k-1}\left(f^{f^k(n)}(n)\right)}(n)=n\\ &\Rightarrow f^{f^{k-1}(n)}(n)=n \end{align*}So inductively, $f^{f^0(n)}(n)=n$, that is, $f^n(n)=n$. If $m\mid2014$ denote $mk=2014$, then $f^m(m)=m$, simple induction gives $f^{km}(m)=f^{2014}(m)=m$. A construction that works here is the identity function. If $m\nmid2014$, then $m\ne1$. Then the construction $f(n)=(m,2m,\ldots,m^2)$ in cycle notation, where $f(m)=2m$, $f(2m)=3m$, $\ldots$, $f(m^2-m)=m^2$, $f(m^2)=m$, and $f(n)=n$ otherwise, satisfies the FE, but has $f^{2014}(m)\ne m$.
14.01.2022 10:06
We define $g(m)$ to be the order of $m$ such that $g(m)$ is the smallest positive integer such that $f^{g(m)} (m) =m$. Now, $$g(m) \mid 2014$$$$g(m) \mid f^{f(m)}(m)$$ Claim: All saturated functions are bijective. Proof: First, we prove that $f$ is injective so suppose $f(a)=f(b)=x$, we see that $f^{f^{f(a)} (a)} (a)=a \Rightarrow f^{f^{x-1} (x) - 1} (x) =a$ and similarly $f^{f^{f(b)} (b)} (b)=b \Rightarrow f^{f^{x-1} (x) - 1} (x) =b$ and therefore $a=b$. Therefore $f$ is bijective too since it is clearly surjective. $\blacksquare$ Now, we prove that we must have $m | 2014$. Note that all these iterations can be taken $\pmod{g(m)}$. Taking $m = g(m)-1$, we get that $f^{f^{m-1} (m)} (m) = m $ and $f^{m-1} (m)$ is divisible by $g(m)$ and is also in the cycle. Next we have that the vertex that maps to $f^{m-1} (m)$ is also divisible by $g(m)$ since $g(m) |f^{m-1} (m) = f^{f^{g(m)-1} (f^{m-1} (m))} (f^{m-1} (m))$ and inductively every element in the cycle is, so $g(m) | m$ and therefore $m |2014$. $\blacksquare$ Now if $m$ doesnt divide $2014$, $f(m)=2m, f(2m)=3m, \cdots f(m^2-m)=m^2, f(m^2)=m$ and all others being identity gives us a contradiction. $\blacksquare$
11.04.2022 22:39
The answer is all $m \mid 2014$. If $m \nmid 2014$, then let $f(m)=f(2m),f(2m)=f(3m),\ldots,f(m^2-m)=f(m^2),f(m^2)=m$, and $f(n)=$ for $n \not \in \{m,\ldots,m^2\}$. It is easy to check that this works. It thus remains to show that $m \mid 2014 \implies f^{2014}(m)=m$. Evidently $f$ can be partitioned into disjoint (finite) cycles. Let $a_1 \to \cdots \to a_k \to a_1$ be one such cycle, which has length $k$. Evidently we must have $k \mid f^{f(a_i)}(a_i)$ for all $i$, so at least one member of the cycle is divisible by $k$. The key claim is now the following: Claim: If $k \mid a_i$, then $k \mid a_{i-1}$. Proof: We have $k \mid f^{f(a_{i-1})}(a_{i-1})=f^{a_i}(a_{i-1})$. This equals $a_{i-1}$ as $k \mid a_i$, hence $k \mid a_{i-1}$ as desired. From the above claim, $k$ divides all elements of the cycle. Thus if $m \mid 2014$, the length of the cycle containing $m$ must divide $m$ and thus divides $2014$ as well, hence $f^{2014}(m)=m$ as desired. $\blacksquare$
16.09.2023 18:08
The answer is all $m \mid 2014$. Note that $f$ is obviously bijective; therefore, it suffices to show that for any cycle in the directed graph of $f$, the length of the cycle divides every element in the cycle. Take any such cycle of length $k$. Then, by the condition, for any $r$ an element in the cycle, we have $k \mid f^{f(r)}(r)$. This implies that there exists an $a$ in the cycle such that $k \mid a$. On the other hand, set $r = f^{-1}(a)$; then, the result implies $k \mid r$ too. Working inductively, we have $k \mid r$ for any $r$ in the cycle, thus done.
24.01.2024 04:47
We claim the answer is $m\mid 2014$. The main idea of the problem is to rigidly characterize all saturated functions. Clearly, the condition tells us that $f$ is composed of only cycles. Claim: A function is saturated if and only if all cycles have the property that all elements in the cycle are divisible by the length. The if direction is trivial, as the number of iteration is a multiple of the length so it will end back at its original position. Consider a cycle $c_1,c_2,c_3\dots c_k$. From now on, take indices modulo $k$. We have $$k\mid f^{f(c_i)}(c_i)$$$$k\mid c_{i+f(c_i)}$$$$k\mid c_{i+c_{i+1}}.$$Clearly, this means that $k\mid c_m$ for some $m$. However, plugging in $i=m-1$, we have $$k\mid c_{m-1+c_m}$$$$k\mid c_{m-1},$$so $c_m$ divisible by $k$ implies $c_{m-1}$ divisible by $k$. Thus, all elements are divisible by $k$, showing the claim. For $m\mid 2014$, the length of the cycle containing $m$ must divide $m$ (and thus divide $2014$), so $f^{2014}(m)=m$. Otherwise, we can construct a cycle containing $m$, $2m$, $3m$, and so on until $m^2$, and have everything else be a fixed point. Everything in this cycle is divisible by its length, but $f^{2014}(m)$ is not equal to $m$ if $m\nmid 2014$.
05.02.2024 13:49
Answer: All $m$ satisfying $m \mid 2014$. Firstly, we'll prove that if $n \mid 2014$, then $f^{2014}(n) = n$. Since $f^{f^{f(n)}(n)}(n) = n$, thus there exists minimal $k$ such that $f^k(n) = n$. We'll prove that $k \mid n$, immediately yielding the result. Note that $k \mid f^{f^{i+1}(n)}(f^i(n))$ for all $0 \le i \le k-1$, hence there exists $l$ such that $k \mid f^l(n)$. Let $0 \le a_1, a_2, \dots, a_s \le k-1$ be the all integers such that for $1 \le i \le s$ we have $k \mid f^{a_i}(n)$. Then we have $k \mid f^{f^{a_i+1}(n)}(f^{a_i}(n))$ for all $i$, therefore $\{a_1, a_2, \dots, a_s\} \equiv \{a_1 - 1, a_2 - 1, \dots, a_s-1\} (k)$, which means $k \mid s$. Since $s \le k$, we get $s = k$, meaning $k \mid n, f(n), \dots, f^{k-1}(n)$. Therefore $f^{2014}(n) = n$. Now if $n \nmid 2014$, we can construct cycle that contains $n$ and its length not divides 2014. Thus we're done. $\blacksquare$
28.02.2024 17:13
We claim that all divisors of $2014$ work. Claim: $f$ is bijective. Proof. We have $f\left(f^{f^{f\left(n\right)}\left(n\right)-1}\left(n\right)\right)=n$, hence $f$ is surjective. Suppose $f\left(n_1\right)=f\left(n_2\right)$. Then, $f^{f\left(n_1\right)}\left(n_1\right)=f^{f\left(n_2\right)}\left(n_2\right)$ as $f\left(n_1\right)>0$. Similarly, $f^{f^{f\left(n_1\right)}\left(n_1\right)}\left(n_1\right)=f^{f^{f\left(n_2\right)}\left(n_2\right)}\left(n_2\right)\Longrightarrow n_1=n_2,$ hence $f$ is injective as well. So, $f$ is bijective. $\blacksquare$ Consider the infinite directed graph $G$ with each vertex representing a positive integer such that $u\rightarrow v$ exists if and only if $v=f(u)$. Then, $G$ consists of disjoint directed cycles. For some positive integer $n$, let $k$ denote the smallest integer satisfying $f^k(n)=n$. For $f^m(n)=n$ to hold, we need to $k\mid m$. Claim: For each positive integer $n$, we have $k\mid n$ and $k\mid f(n)$. Proof. From the equation given, we have $k\mid f^{f(n)}(n)$. Consider the cycle $\mathcal{C}$ of $G$ to which $n$ belongs. Then, for each $m$, $f^m(n)$ is a member of this cycle. So, $f^{f(n)}(n)$ is a member of this cycle. We claim if one element of the cycle is divisible then all elements are. Let $k\mid v=f^{f(n)}(n)=f(u)$. Note that \[k\mid f^{f(u)}(u)\Longrightarrow k\mid f^v(u)\Longrightarrow k\mid u,\]as $f^{x+k}(u)=f^x(u)$. So, $v$ is divisible then so is it's pre-image. By a simple induction, all members of the cycle are divisible by $k$. Hence, $k\mid n$, and $k\mid f(n)$ as both of them are members of the cycle. $\blacksquare$ Note, from the above claim it follows that $f^{f(n)}(n)=n$ and $f^n(n)=n$, which both are combined are equivalent to the original equation. In fact we just need all the terms in every cycle to be divisible by the length of the cycle and we'd be done! Suppose $n\mid2014$. Since $k\mid n$, we have $k\mid2014$, which gives $f^{2014}(n)=n$, as required. We give a construction for non-divisors of $2014$. Consider a cycle of $n\rightarrow2n\rightarrow3n\cdots\rightarrow n^2\rightarrow n$. For every other number $x$, we conveniently fixed $f(x)=x$. This works because the length of cycle is $n$ and each terms is divisible by $n$ as well. So, if $f^{2014}(n)=n$ then $n\mid2014$, which is a contradiction. The proof is complete.
18.10.2024 12:00
If $m\mid 2014$ than we must have $f^{2014}(m)=m$ and if $m\nmid 2014$, that result does not hold. Let $g(n)$ denote the length of the cycle $n, f(n), f(f(n)), \dots$ suppose $g(n)\nmid n$ for some $n$, we can note that $g(n)\mid f^{f(n)}(n)$, thus this implies there exists some value in the cycle such that it is divisible by $g(n)$, now consider a value $m$ in the cycle such that $g(n)\mid f(m)$ and $g(n)\nmid m$, thus we get that $g(n)\mid f^{f(m)}(m)=m$ which is a contradicition thus this implies all the values in a cycle with length $k$ must be divisible by $k$, this implies the result.
12.11.2024 14:04
Cool Cool Cool. Enjoyed this problem a lot! We claim that the answer is all $m\mid 2014$. We say a positive integer $m$ is sparkly if $f^{2014}(m)=m$. We start off by showing that all $m$ which are not factors of 2014 cannot be sparkly. We consider the function, \[f(m)=2m \text{ } , \text{ } f(2m)=3m \text{ } , \dots , \text{ } f(m^2-m)=m^2 \text{ } , \text{ } f(m^2)=m\]and $f(n)=n$ for all $n\not \in \{m,2m,\dots , m^2\}$. Quite clearly for all $n\not \in \{m,2m,\dots , m^2\}$, $f^{f^{f(n)}(n)}(n)=n$ as desired. For integers of the form $mk$ ($1\le k \le m$) first note that $f^{mr}(mk)=mk$ for all positive integers $r$ since $f^m(mk)=mk$ (cycle length is $m$). Thus, \[f^{f^{f(mk)}(mk)}(mk)=f^{f^{mk+m}}(mk)=f^{mk}(mk)=mk\]So, this function is indeed saturated. But, $f^{2014}(m)\ne m$ since $m\nmid 2014$ (cycle size is $m$). Thus, $m$ is not sparkly as claimed. Consider $m\mid 2014$. Look at the cycle containing $m$. That is the sequence of integers $a_1=m , a_2 , \dots , a_k$ such that $f(a_1)=a_2 , \dots , f(a_{k-1})=a_k$ and $f(a_k)=a_1$. This sequence is clearly finite as $f^{f^{f(m)}(m)}(m)=m$. Further, the cycle size, $k\mid f^{f(m)}(m)$. Since $ f^{f(m)}(m)$ is also an element of this sequence, there exists some integer $a_i$ in this sequence which is divisible by $k$. We consider the smallest-indexed such integer to be $a_i$. Now, if $i>1$ note that, \[a_{i-1}=f^{f^{f(a_{i-1})}(a_{i-1})}(a_{i-1})=f^{f^{a_i}(a_{i-1})}(a_{i-1})=f^{a_{i-1}}(a_{i-1})\]which implies that $k\mid a_{i-1}$. But this is a clear contradiction since $1\le i-1 <i$ and thus, we must have $k\mid m$. But then, $k\mid m \mid 2014$, so $f^{2014}(m)=m$ for any saturated function $f$. This implies that $m$ is indeed sparkly, and we are done.
15.11.2024 00:41
The answer is when $m\mid 2014$ (that is, $m=1,2,19,38,53,106,1007,2014$). Obviously $f$ is bijective and everything eventually gets back to itself. So $f$ is just a collection of cycles. Let a cycle $C$ have length $\ell$. Then for all $n\in C$, \[\ell\mid f^{f(n)}(n).\]So some value $a\in C$ is divisible by $\ell$. But if $b\to a$, we get that \[\ell\mid f^{f(b)}(b)=f^a(b)=b.\]If we keep doing this, we get that every value in $C$ is divisible by $\ell$. This is sufficient because then $f^{f(n)}(n)\in C$ so it is divisible by $\ell$. To constuct a function to show that other $m$ don't work, map everything not mentioned to itself, and let \[m\to 2m\to 3m\to\dots\to m^2\to m.\]But if $m\mid 2014$, then $\ell\mid m\mid 2014$, as desired. $\blacksquare$
17.01.2025 10:13
Firstly since we have $n$ free on the RHS, this motivates us to show bijectivity, so we have $f$ is obviously surjective, now for injectivity. Assume $f(a)=f(b)=c$, then we have that. \[f^{f^{f(a)}(a)}(a) = f^{f^{f(b)}(b)}(b) = f^{f^{c-1}(c)-1}(c) \implies a=b\]Proving bijectivity. Now we have that as $f^{f^{f(n)}(n)}(n)=n$, hence for each number $n$, there is a cycle, call it $C_n$, these cycles are disjoint due to $f$ being bijective, and let $k_n$ denote the length of that cycle. By the problem condition we have that $k_n|f^{f(n)}(n)$, for all $n \in C_n$. We know that $f^{f(n)}(n) \in C_n$, so now we try to use that, to help us get information about other elements of the cycle, let $f^{f(n)}(n)=u$ then we have that $k_n|u$, let $u=f(v)$ and so we have $k_n\mid f(v)$. which means that we have. \[k_n\mid f^{f(v)}(v)= f^{u}(v) \implies k_n\mid v\] Now we can by repeating same argument get that $k_n \mid i$ for all $i \in C_n$. From this we get that $k_n\mid f(n)$ and $k_n\mid n$. So now suppose that $n \mid 2014 $ then we get that $k_n\mid n\mid2014$ so $f^{2014}(n)=n$, now assume that $n$ does not divide $2014$, consider the following cycle. \[n\rightarrow2n\rightarrow3n\cdots\rightarrow n^2\rightarrow n\]Its length is $n$, so if $n$ does not divide $2014$, then we cant have $f^{2014}(n)=n$. So we are done.
17.01.2025 14:29
Using the arrows philosophy, notice that the graph of $f$ is fully composed of cycles. Letting $l(n)$ denote the length of the cycle containing $n$, the key claim is that $n \mid l(n)$, from where it's obvious the answer is $n \mid 2014$.