IMC 1994 · Problem 6

Let $f \in C^2[0,N]$ and $|f'(x)| < 1$, $f''(x) > 0$ for every $x \in [0,N]$. Let $0 \le m_0 < m_1 < \dots < m_k \le N$ be integers such that $n_i = f(m_i)$ are also integers for $i = 0, 1, \dots, k$. Denote $b_i = n_i - n_{i-1}$ and $a_i = m_i - m_{i-1}$ for $i = 1, 2, \dots, k$.

a) Prove that

$$-1 < \frac{b_1}{a_1} < \frac{b_2}{a_2} < \dots < \frac{b_k}{a_k} < 1.$$

b) Prove that for every choice of $A > 1$ there are no more than $N/A$ indices $j$ such that $a_j > A$.

c) Prove that $k \le 3N^{2/3}$ (i.e. there are no more than $3N^{2/3}$ integer points on the curve $y = f(x)$, $x \in [0,N]$).