Let $\mathbb{N}_0$ denote the set of non-negative integers. Determine all non-negative integers $k$ for which there exists a function $f: \mathbb{N}_0 \to \mathbb{N}_0$ such that $f(2024) = k$ and $f(f(n)) \leq f(n+1) - f(n)$ for all non-negative integers $n$.
Problem
Source: MEMO 2024 I1
Tags: algebra, Sequences, functions, monotone, construction, Functional inequality, function
27.08.2024 00:41
Answer: $0\le k\le 2023$ with example $f(0)=f(1)=\dots f(2023)=0$ and $f(i)=k$ for $i\ge2024$. We can easily see that $f(n+1)\ge f(n)$, because $f(f(n))\ge 0$ meaning $f$ is non-decreasing. Lemma: $f(n)\le n$ Assume that $f(n)> n$. Then $f(f(n))\ge f(n+1)>f(n+1)-f(n)$ So it only remains to see that $k\neq 2024$. If $f(2024)=2024$ we have the inequality $f(f(2024))\le f(2025)-f(2024)$, so $f(2025)\ge 4048$ which is impossible due to the lemma. So the problem is solved
27.08.2024 01:18
Observe that $f(n+1) - f(n) \geq f(f(n)) \geq 0$, so $f$ is increasing and hence $f(n+1) \geq f(n+1) - f(n) \geq f(f(n))$ implies $f(n) \leq n+1$. The main claim is the stronger bound $f(n) \leq n - 1$ for $n\geq 2$. Indeed, if $f(n) = n+1$, then $f(n+1) - (n+1) = f(n+1) - f(n) \geq f(f(n)) = f(n+1)$, i.e. $n+1 \leq 0$, contradiction so $f(n) \leq n$; and if $f(n) = n$, then $n+1 \geq f(n+1) \geq f(n) + f(f(n)) = 2n$, i.e. $n\leq 1$, contradiction. (From this one can also obtain $f(1) = 0$, since if $f(1) = 1$, then $f(2) \geq 2$, contradiction with the main claim, but this is just a not needed bonus.) In particular, $0\leq k = f(2024) \leq 2023$ necessarily. All these work by finding a piecewise constant example e.g. as p.lazarov06: $f(i) = 0$ for $i\leq 2023$ and $f(i) = k$ for $i\geq 2024$ - it works since all summands are $0$ for $n \leq 2022$, while $f(f(2023)) = f(0) = 0 \leq k = f(2024) - f(2023)$ and $f(f(n)) = f(k) = 0 = k - k = f(n+1) - f(n)$ for $n\geq 2024$.
28.08.2024 15:05
A very related problem is IMO SL 2007 A2
11.10.2024 08:39
Basically the same as part (a) of 2009 Belarus TST .
28.01.2025 19:27
First notice that $f(n+1)-f(n) \ge f(f(n)) \ge 0$ which means that $f(n+1) \ge f(n)$ so $f$ is non-decreasing, but we also have that $f(n+1) \ge f(n+1)-f(n) \ge f(f(n))$, notice first LHS ineq is strict when $f(n)>0$ so if we ever had $f(n)>n$ this becomes a contradiction from non-decreasing, therefore $n \ge f(n)$, in addition when $n \ge 2$ if we had that $f(n)=n$ then $f(n+1) \ge 2n$ which cannot happen as it implies $1 \ge n$, therefore $n>f(n)$ for all $n \ge 2$ and thus theorically we can only achieve values from $0$ to $2023$ for $f(2024)$. To finish a construction is $f(0)=f(1)= \cdots =f(2023)=0, f(\ell)=k$ for some fixed $0 \le k \le 2023$ and where $\ell \ge 2024$, this clearly works as $f(f(n))=0$ regardless and then RHS is $k$ only once then its $0$ again. Thus done .