
Problem 4. A finite set $S$ of positive integers is called cardinal if $S$ contains the integer $|S|$, where $|S|$ denotes the number of distinct elements in $S$. Let $f$ be a function from the set of positive integers to itself, such that for any cardinal set $S$, the set $f(S)$ is also cardinal. Here $f(S)$ denotes the set of all integers that can be expressed as $f(a)$ for some $a$ in $S$. Find all possible values of $f(2024)$.

Note: As an example, $\{1,3,5\}$ is a cardinal set because it has exactly 3 distinct elements, and the set contains 3 .


Solution 1. The possible values are 1, 2, and 2024 .

Construction. The function $f(x)=1$ for all $x \in \mathbb{N}$ works. Also, $f(x)=1$ for all $x \neq 2024$ and $f(2024)=2$, works. Finally, $f(x)=x$ for all $x \in \mathbb{N}$ works as well.

It remains to show these are the only possible values for $f(2024)$.

Proof. Denote $\operatorname{Im}(f)=\{f(x) \mid x \in \mathbb{N}\}$. The cardinal set $\{1\}$ gives $f(1)=1$. Consider the following two cases:

- $\operatorname{Im}(f)$ is unbounded. Fix any $n \in \mathbb{N}$, with $n>1$. Pick $n-1$ distinct integers $k_{1}, \ldots, k_{n-1}$ such that $f\left(k_{i}\right) \notin\{n, f(n)\}$ and $f\left(k_{i}\right)$ are all pairwise distinct, for $1 \leq i0$.

Claim. For any integer $a$ satisfying $1 \leq a \leq M$, if there are infinitely many integers $n \in \mathbb{N}$ such that $f(n)=a$, then $a=1$.

Proof. Let $b>1$ be one of the integers with $f(b)=a$. Consider $b-1$ other integers $c_{1}, \ldots, c_{b-1}$, such that $f\left(c_{i}\right)=a$ for $1 \leq i1$ such that for all $n \geq N, f(n)=1$. Now for every $1<l<N$, consider the cardinal set $\{l, N+1, N+2, \ldots, N+l-1\}$. Then the image set consists of $\{1, f(l)\}$, which can be cardinal only when $f(l)=1$ or $f(l)=2$.

By the above reasoning, $f(2024)$ can only be 1,2 , or 2024 , each of which occurs as an example.
