Putnam 2009, Problem B-2

A game involves jumping to the right on the real number line. If $a$ and $b$ are real numbers and $b > a$, the cost of jumping from $a$ to $b$ is $b^3 - ab^2$. For what real numbers $c$ can one travel from $0$ to $1$ in a finite number of jumps with total cost exactly $c$?

Solution:
The desired real numbers \( c \) are precisely those for which \( 1/3 < c \leq 1 \). For any positive integer \( m \) and any sequence \( 0 = x_0 < x_1 < \cdots < x_m = 1 \), the cost of jumping along this sequence is \( \sum_{i=1}^m (x_i - x_{i-1})x_i^2 \). Since
\[
1 = \sum_{i=1}^m (x_i - x_{i-1}) \geq \sum_{i=1}^m (x_i - x_{i-1})x_i^2 > \sum_{i=1}^m \int_{x_{i-1}}^{x_i} t^2 dt = \int_0^1 t^2 dt = \frac{1}{3},
\]
we can only achieve costs \( c \) for which \( 1/3 < c \leq 1 \).

It remains to check that any such \( c \) can be achieved. Suppose \( 0 = x_0 < \cdots < x_m = 1 \) is a sequence with \( m \geq 1 \). For \( i = 1, \ldots, m \), let \( c_i \) be the cost of the sequence \( 0, x_i, x_{i+1}, \ldots, x_m \). For \( i > 1 \) and \( 0 < y \leq x_{i-1} \), the cost of the sequence \( 0, y, x_i, \ldots, x_m \) is
\[
c_i + y^3 + (x_i - y)x_i^2 - x_i^3 = c_i - y(x_i^2 - y^2),
\]
which is less than \( c_i \) but approaches \( c_i \) as \( y \to 0 \). By continuity, for \( i = 2, \ldots, m \), every value in the interval \( [c_{i-1}, c_i) \) can be achieved, as can \( c_m = 1 \) by the sequence \( 0, 1 \).

To show that all costs \( c \) with \( 1/3 < c \leq 1 \) can be achieved, it now suffices to check that for every \( \varepsilon > 0 \), there exists a sequence with cost at most \( 1/3 + \varepsilon \). For instance, if we take \( x_i = i/m \) for \( i = 0, \ldots, m \), the cost becomes
\[
\frac{1}{m^3}(1^2 + \cdots + m^2) = \frac{(m + 1)(2m + 1)}{6m^2},
\]
which converges to \( 1/3 \) as \( m \to +\infty \).

**Reinterpretation.** The cost of jumping along a particular sequence is an upper Riemann sum of the function \( t^2 \). The fact that this function admits a Riemann integral implies that for any \( \varepsilon > 0 \), there exists \( \delta_0 \) such that the cost of the sequence \( x_0, \ldots, x_m \) is at most \( 1/3 + \varepsilon \) as long as \( \max_i \{x_i - x_{i-1}\} < \varepsilon \). (The computation of the integral using the sequence \( x_i = i/m \) was already known to Archimedes.)