Let $f: \mathbb{N} \rightarrow \mathbb{N}$ be a bijection and let $k$ be a positive integer such that $|f(x+1)-f(x)| \leq k$ for all positive integers $x$. Show that there exists an integer $d$, such that $f(x)=x+d$ for infinitely many positive integers $x$.
Problem
Source: Serbia TST 2024, P4
Tags: algebra
18.05.2024 22:39
Solved with $\textbf{erkosfobiladol}\in \textbf{sdninajanlari}$. Assume contrary. Let the expression $|f(x)-x|$ go to infinity. $\textbf{Claim:}$ There exist $f(x)\leq x$ in every $[n,\infty)$ since $f$ is surjective. Assume contrary. Let $f(x)\geq x+1$ for all $x\geq M$. The set $\{f(1),...,f(x-1)\}$ takes $x-1$ values hence at least one value in $\{1,2,...,x\}$ is not taken. Also $f(x),f(x+1),...>x$ but this contradicts with surjectivity. Let $|f(x)-x|\geq k+1$ for all $x\geq N$. Because of the claim, there exists $a\geq N$ which holds $a\geq f(a)$. We have $a-f(a)=|a-f(a)|\geq k+1>k\geq |f(a+1)-f(a)|\geq f(a+1)-f(a)$ which gives that $a>f(a+1)$. Applying the same procedure. for $a+1,a+2,...$ gives that $m-1>f(m)$ for all $m\geq a$. $max\{f(1),f(2),...,f(m)\}=A$. By injectivity, we have $A\geq m$. Also $A+1\leq max\{f(1),f(2),...,f(m),...,f(A+1)\}=max\{max\{f(1),f(2),...,f(m)\},f(m+1),...,f(A+1)\}\leq A$ since $f(m+t)\leq m+t-1\leq A$ for $t=1,2,...,A-m+1$ which gives a contradiction as desired.$\blacksquare$