Putnam 2014, Problem B-6

Let $f: [0, 1] \to \mathbb{R}$ be a function for which there exists a constant $K > 0$ such that $|f(x) - f(y)| \leq K|x - y|$ for all $x, y \in [0, 1]$. Suppose also that for each rational number $r \in [0, 1]$, there exist integers $a$ and $b$ such that $f(r) = a + br$. Prove that there exist finitely many intervals $I_1, \ldots, I_n$ such that $f$ is a linear function on each $I_i$ and $[0, 1] = \bigcup_{i=1}^n I_i$.


Solution:
Let \(g\) be integral if \(g(x) = a + bx\) for \(a, b \in \mathbb{Z}\), and piecewise linear \(g\) is integral if linear on each interval. For each \(n\), let \(F_n\) be the \(n\)-th Farey sequence: rationals in \([0,1]\) with denominator at most \(n\), in lowest terms, with consecutive terms \(\frac{r}{s}, \frac{r'}{s'}\) satisfying \(s + s' > n\) and \(r's - rs' = 1\). Let \(f_n: [0,1] \to \mathbb{R}\) be the piecewise linear function agreeing with \(f\) at \(F_n\) and linear between consecutive terms. Then \(sf_n\left(\frac{r}{s}\right), s'f_n\left(\frac{r'}{s'}\right) \in \mathbb{Z}\), so \(b = ss'\left( f_n\left(\frac{r'}{s'}\right) - f_n\left(\frac{r}{s}\right) \right)\) is an integer with \(|b| \leq K\). Also, \(as = sf\left(\frac{r}{s}\right) - br\) and \(as' = s'f\left(\frac{r'}{s'}\right) - br'\) are integers. If \(n > 2K\), then \(f_n = f_{n-1}\): the linear function \(a_0 + b_0 x\) matching \(f_{n-1}\) from \(\frac{r}{s}\) to \(\frac{r'}{s'}\) has slope \(b_0 + st\) with \(|b_0 - st| \leq K\). Since \(s + s' = n > 2K\), \(t = 0\), so \(f_n = f_{n-1}\). Thus \(f_n = f\) for \(n > 2K\), completing the proof.