Maths Olympiad Prep

Library / /4 of 4

Algebra Difficulty 8.9 Shortlist Prove it Taiwan

Find all functions f:NNf : \mathbb{N} \to \mathbb{N} such that, for any set AA containing exactly 2024 distinct positive integers, the set
SA:={f(k)(x)1k2024, xA} S_A := \{f^{(k)}(x) \mid 1 \le k \le 2024,\ x \in A\}
is also a set containing exactly 2024 distinct positive integers.

Remark: f(k)f^{(k)} denotes the kk-th iteration of ff. In other words, f(1)(x):=f(x)f^{(1)}(x) := f(x) and for all n1n \ge 1, f(n+1)(x):=f(f(n)(x))f^{(n+1)}(x) := f(f^{(n)}(x)).

Find all functions f:NNf: \mathbb{N} \rightarrow \mathbb{N} such that for all sets AA consisting of 2024 distinct positive integers,
SA:={f(k)(x)1k2024, xA} S_A := \{f^{(k)}(x) \mid 1 \le k \le 2024,\ x \in A\}
is also a set consisting of 2024 distinct positive integers.

Remark: f(k)f^{(k)} denotes the kk-th iteration of ff. In other words, f(1)(x):=f(x)f^{(1)}(x) := f(x) and for all n1n \ge 1, f(n+1)(x):=f(f(n)(x))f^{(n+1)}(x) := f(f^{(n)}(x)).

Solution

Clearly f(x)=xf(x) = x is one solution. Furthermore, for any set A={a1,a2,,a2024}A = \{a_1, a_2, \dots, a_{2024}\} consisting of 2024 distinct positive integers, any function ff satisfying
{f(ai)=ai1,where a0=a2024,f(x)A,for all xA, \begin{cases} f(a_i) = a_{i-1}, & \text{where } a_0 = a_{2024}, \\ f(x) \in A, & \text{for all } x \notin A, \end{cases}
also satisfies the condition of the problem. Let us prove that the above are all the solutions.

Using all positive integers as points, and connecting xx to f(x)f(x), we form a directed graph GG (self-loops allowed). Note that if xx can reach 2025 points, then any AA containing xx and f(x)f(x) would have SA2025|S_A| \ge 2025, a contradiction. This means that starting from xx, we must enter a cycle within 2024 steps, and the size of this cycle is at most 2024.

Now, consider all points in GG that lie on cycles. Let us consider the size of CC.

Case 1. C>2024|C| > 2024:
Note that in this case there cannot be any xCx \in C such that f(x)xf(x) \ne x; otherwise, take any ACA \subset C containing xx but not f(x)f(x), then ASAA \subset S_A (note that all elements of AA lie on cycles) and f(x)SAf(x) \in S_A, so that A{f(x)}SASAA+1>2024A \cup \{f(x)\} \subset S_A \Rightarrow |S_A| \ge |A| + 1 > 2024, a contradiction.

Hence we have f(x)=xf(x) = x for all xCx \in C. Now, if there is any yCy \notin C, since yy must reach CC within 2024 steps, there exists zCz \notin C such that f(z)Cf(z) \in C. If we take A={z,f(z),b1,,b2022}A = \{z, f(z), b_1, \dots, b_{2022}\}, where bib_i are 2022 elements of CC different from f(z)f(z), then SA=A{z}S_A = A - \{z\}, so that SA=A1<2024|S_A| = |A| - 1 < 2024, a contradiction. Hence C=NC = \mathbb{N}, that is, f(x)=xf(x) = x.

Case 2. C2024|C| \le 2024:
Since all xNx \in \mathbb{N} must reach CC within 2024 steps, and CC is a finite set, there exists yNy \in \mathbb{N} such that f1(y):={x:f(x)=y}f^{-1}(y) := \{x : f(x) = y\} is an infinite set. Now taking Af1(y)A \subset f^{-1}(y), we know that Y:={y,f(y),,f(2023)(y)}Y := \{y, f(y), \dots, f^{(2023)}(y)\} has Y=2024|Y| = 2024; in other words, yy lies on a cycle YY of size exactly 2024.

Now, for any xNx \in \mathbb{N}, take AA satisfying xAx \in A and Af1(y)A \cap f^{-1}(y) \neq \emptyset. Note that in this case YSAY \subset S_A, forcing Y=SAY = S_A (otherwise SA>Y=2024|S_A| > |Y| = 2024), and hence also f(x)Yf(x) \in Y. This means that all points not on YY must reach YY in one step, which is the second possible ff.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from zh; metadata (topic, difficulty) added by this project.