Find all functions $f:\mathbb{N}\to\mathbb{N}$ s.t. for all $A\subset \mathbb{N}$ with 2024 elements, the set $$S_A:=\{f^{(k)}(x)\mid k=1,...,2024,x\in A\}$$also has 2024 elements. ($f^{(k)}=f\circ f\circ...\circ f$ is the $k$-th iteration of $f$.)
Problem
Source: 2024 Taiwan TST Round 2 Independent Study I-C
Tags: combinatorics
16.08.2024 22:32
The function $f(x)=x$ is an answer as well as functions of the following forms. Let $B\subset \mathbb{N}$ be a set with $2024$ elements say $x_1,x_2,\dots, x_{2024}$. Then $f$ maps all $x\notin B$ to an element in $B$ and $f(x_i)=x_{i+1}$ for all $1\leq i \leq 2024$ where $x_{2025}=x_{1}$. We could also have $f$ map all $x\notin B$ to $x_1$ and have $f(x_i)=x_{i+1}$ for all $1\leq i\leq 2023$ and have $f(x_{2024})=x_i$ for some $i$, $2\leq i \leq 2024$. All these functions clearly work. Case: There exists an $x$ such that $f^k(x)$ for $1\leq k\leq 2024$ are all distinct Then for all $y\neq x$ we must have that $f(y)=f^l(x)$ for some $l$, $1\leq l\leq 2024$ by considering $x,y\in A$. If $f^{2025}(x)=f(x)$ then we have the second type of function so assume otherwise. Then if for some $y\neq f^k(x)$ for $1\leq k \leq 2024$ we have that $y\neq f(x)$ then letting $A$ be $y,f^2(x),f^3(x),\dots , f^{2024}(x)$ gives a contradiction so we must only have functions of the third form. Now for every $x$ either $x$ is a fixed point or $f(x)$ is part of a cycle with size at most $2023$. If we have no cycles then we are left with the first characterization. If the number of cycles is finite then there must exist a cycle with infinitely many values leading into it so we could chose in $A$ that would gives us a contradiction. Otherwise we could choose $A$ to contain elements from all different cycles, giving a contradiction.