Problem 1795

We will show the contrapositive of the statement. In particular, we will show that if there are no ultra-disobedient positive integers, then there exists a nonnegative integer $\alpha$ with $f(n) = n^\alpha$ for any $n \in \mathbb{N}$.

We first show that $f(1) = 1$. Since $1$ is not ultra-disobedient, there exists $n \in \mathbb{N}$ with $f(n) = f(n)f(1)$, showing that $f(1) = 1$.

Now let $a, b$ be two arbitrary positive integers greater than $1$. We will show that $\log f(a)/\log a = \log f(b)/\log b$. Since none of them is ultra-disobedient, there exist non-negative integers $N, M$ such that for any $n > M$, some of $(a, n), \dots, (a, n + N)$ and some of $(b, n), \dots, (b, n + N)$ are obedient.

By symmetry, it suffices to show that $\log f(a)/\log a \ge \log f(b)/\log b$. Assume for the sake of contradiction that $\log f(a)/\log a < \log f(b)/\log b$. Then $\log a/\log b > \log f(a)/\log f(b)$, and by the density of rationals we can find $p, q \in \mathbb{N}$ such that $\log a/\log b > p/q > \log f(a)/\log f(b)$.

$$x_q \geq a^q k - (a^{q-1} + \dots + 1)N, \quad y_p \leq b^p k + (b^{q-1} + \dots + 1)N.$$
Since $a^q > b^q$, we can choose $k$ large enough so that $x_q > y_p$. This then gives that $f(a)^q \geq f(b)^p$, or $\log f(a)/\log(b) > p/q$. This is a contradiction. Therefore $\log f(a)/\log a \geq \log f(b)/\log b$, and thus $\log f(a)/\log a = \log f(b)/\log b$ by symmetry. We can now let $\alpha = \log f(2)/\log 2$ and complete the proof.