Problem
ALG-B1-M08-P024 A surjective ladder
#24
★★★★★ Level 5 of 5
Let \(f:\mathbb Z\to\mathbb Z\) be surjective and satisfy \(f(n+1)\ge f(n)+1\) for all integers \(n\). Prove that there exists an integer \(c\) such that \(f(n)=n+c\) for all \(n\).
If some step is greater than \(1\), which integer value is skipped?
The condition implies that \(f\) is strictly increasing. If for some \(n\), \(f(n+1)\ge f(n)+2\), then the integer \(f(n)+1\) cannot be a value of the function: for \(k\le n\), \(f(k)\le f(n)\), while for \(k\ge n+1\), \(f(k)\ge f(n+1)\ge f(n)+2\). This contradicts surjectivity.
Hence \(f(n+1)=f(n)+1\) for all \(n\). Then \(f(n)-n\) is constant. Denoting this constant by \(c\), we get \(f(n)=n+c\).
A strong ending to the introductory module: surjectivity forbids gaps.