Find all valid functions $f:\mathcal{T}\to\mathcal{S}$

Question

Let $\mathcal{S} = \{0,1,\cdots, 1999\}$ and $\mathcal{T} = \{0,1,2,\cdots\}.$ Call a function $f :\mathcal{T}\to\mathcal{S}$ valid if it satisfies the following: i) $f(s) = s$ for all $s\in \mathcal{S} $ and ii) $f(m+n) = f(f(m)+f(n))$ for all $m,n\in\mathcal{T}$.

If $f(2000) < 2000$ for any valid function f, then the answer is 2000. How could one justify this if it is true? I tried using ii) repeatedly but I'm not sure how to get the result. $$

Assume $f(2000) = 2000-t$ for some $t\in \{1,\cdots, 2000\}.$ Then $f(s) = s$ for all $s\in\mathcal{S}.$ We claim that $f(n) = f(n-t)$ for all $n\ge 2000,$ and we prove this by induction. The base case holds because $f(2000 + 0) = f(f(2000) + f(0)) = f(2000-t)$ as $f(0)=0$. Now suppose inductively that $f(n) = f(n-t)$ for some $n\ge 2000.$ Then $f(n+1 - t) = f(n-t + 1) \underbrace{=}_\text{by ii)} f(f(n-t) + f(1)) \underbrace{=}_\text{by the inductive hypothesis} f(f(n) + f(1)) \underbrace{=}_\text{by ii)} = f(n+1).$ Thus $f$ is uniquely determined by $f(2000),$ since the values $f(s)$ for $s\in \mathcal{S}$ are already fixed for any valid function f by i) (one could prove this more formally by induction).

Conversely, if $t \in \{1,\cdots, 2000\}$, we can define a valid function $f$ by letting $f(2000) = 2000-t, f(s) = s\,\forall s\in \mathcal{S}$ and defining $f(n) = f(n-t)$ for all $n > 2000$. We just need to verify that ii) holds, and we do this by induction on m + n. When $m+n=0$, the result holds. Also the result holds when $m,n \in\mathcal{S}$ by the definition of f. Suppose the result holds for all $m,n$ with $m+n < k$ for some positive integer k. Now let $m,n$ satisfy $m+n = k$ and WLOG let $n\ge 2000$ (if both $m,n < 2000$ the result holds). Note that $f(m+n - t) \underbrace{=}_\text{by the inductive hypothesis} f(f(m) + f(n-t)) \underbrace{=}_\text{by the definition of f} f(f(m)+f(n)) \underbrace{=}_\text{by ii)} f(m+n)$.

Answer 1

We start with the following definitions. Let $[n]=\mathbb Z\cap[1,n]$ be the integers from $1$ to $n$. For $t\in[2000]$ let $f_t:\mathcal T\rightarrow\mathcal S$ be recursively defined by $f_t(n)=n$ for $n\in\mathcal S$ and $f_t(n)=f_t(n-t)$ for $n\in\mathbb Z_{\ge 2000}$.

Now, we proof the following claims, in this order.

1. The map $[2000]\rightarrow\mathcal F$, $t\mapsto f_t$, is a bijection, where $\mathcal F=\{f_t:t\in[2000]\}$.
2. For every valid function $f$ there exists $t\in[2000]$ such that $f=f_t$.
3. The function $f_t$ is valid for all $t\in[2000]$.

Afterwards, we derive the result and provide additional remarks.

1. The map is surjective by definition and for $t\neq t'$ we have $f_t(2000)=2000-t\neq 2000-t'=f_{t'}(2000)$, so the map is an injection and thus a bijection.
2. Let $f:\mathcal T\rightarrow\mathcal S$ be valid and $t=2000-f(2000)$. Since we have $f(2000)\in\mathcal S$, we have $0\le f(2000)\le 1999$ and hence $1\le t\le 2000$. By definition we have $f(n)=n=f_t(n)$ for $n\in\mathcal S$. Using induction we show that $f(n)=f_t(n)$ for $n\in\mathbb Z_{\ge 2000}$. Clearly, we have $f(2000)=2000-t=f_t(2000)$ and further \begin{aligned} f(n+1)&=f(f(n)+f(1))=f(f_t(n)+f(1))=f(f_t(n-t)+f(1))\\ &=f(f(n-t)+f(1))=f(n-t+1)=f_t(n+1-t)=f_t(n+1) \end{aligned} for $n\in\mathbb Z_{\ge 2000}$.
3. By definition we have $f_t(n)=n$ for $n\in\mathcal S$, so let $n,m\in\mathcal T$. For $n,m\in\mathcal S$ we have $f_t(m+n)=f_t(f_t(m)+f_t(n))$. For $m\in\mathcal S$ and $n\in\mathcal T\setminus\mathcal S$ let $k\in\mathbb Z_{\ge 0}$ be such that $n-kt\in[2000-t,2000)$ and notice that \begin{aligned} f_t(m+n)=f_t(m+n-kt)=f_t(f_t(m)+f_t(n-kt))=f_t(f_t(m)+f_t(n)). \end{aligned} The argumentation for $n\in\mathcal S$, $m\not\in\mathcal S$ is symmetric. For $n,m\in\mathcal T\setminus\mathcal S$ we take $k,k'\in\mathbb Z_{\ge 0}$ such that $m-kt,n-k't\in[2000-t,2000)$, notice that $m+n-(k+k')t\ge 2(2000-t)\ge 2000-t$ since $t\le 2000$ and thereby \begin{aligned} f_t(m+n)=f_t(m+n-(k+k')t)=f_t(f_t(m)+f_t(n)). \end{aligned}

The first claim ensures that $|\mathcal F|=2000$, the remaining two suggest that $\mathcal F$ is exactly the set of valid functions.

Aftermath: The first claim is fairly trivial. At its core, the proof of the second claim is as suggested in the question. For the proof of the third claim, it is crucial to understand the behavior of the $f_t$, in particular the periodicity and the connection to modular arithmetic, taken for granted that this is an advanced application of induction/recursion.