Задача
ALG-B1-M08-P024 Сюръективная лестница
#24
★★★★★ Уровень 5 из 5
Пусть \(f:\mathbb Z\to\mathbb Z\) сюръективна и \(f(n+1)\ge f(n)+1\) для всех целых \(n\). Докажите, что существует целое \(c\), такое что \(f(n)=n+c\) для всех \(n\).
Если где-то скачок больше \(1\), какое целое значение пропущено?
Из условия \(f\) строго возрастает. Если для некоторого \(n\) выполнено \(f(n+1)\ge f(n)+2\), то целое число \(f(n)+1\) не может быть значением функции: для \(k\le n\) имеем \(f(k)\le f(n)\), а для \(k\ge n+1\) имеем \(f(k)\ge f(n+1)\ge f(n)+2\). Это противоречит сюръективности.
Значит, \(f(n+1)=f(n)+1\) для всех \(n\). Тогда \(f(n)-n\) постоянно. Обозначив эту константу через \(c\), получаем \(f(n)=n+c\).
Сильное завершение вводного модуля: сюръективность запрещает пропуски.