Putnam 2009 B2

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$?

The most interesting part of this problem is getting the answer--proving that it works is one of those things that probably has an elegant solution, but the one you come up with while you're taking the exam is most likely going to be ugly.

The point is that the cost, $b^2(b-a)$, is the area of a rectangle with vertices on the $x$-axis at $a$ and $b$, and height $b^2$. So the total cost in jumping from $0$ to $1$ is the sum of the areas of a bunch of rectangles whose bases are all next to each other on the $x$-axis and whose upper right vertex is on the curve $y=x^2$. (Sorry I'm not industrious enough to figure out how to embed the right picture!) And that should stir a memory from calculus class...So the sums of these rectangles are always bigger than \[ \int_0^1 x^2 \, dx = 1/3. \] And of course they're always less than $1$. But in the limit, they should approach $1/3$, so we expect the answer to the question to be $c \in (1/3,1]$. At least we've already shown that the only representable $c$ are in $(1/3,1]$, so the idea will be to show that any such value of $c$ can be attained by judiciously choosing the steps along the way.

There's probably some elegant way to do this, but let's try the following: jump at $0, a, 2a, \cdots, na, 1$, where $n$ is some integer and $a$ is some real number such that $na \le 1$. Let's figure out the total cost.

Remembering that $\sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}6$, we can pretty quickly get the total cost to be \[ 1 - na + \frac{n(n+1)(2n+1)}6 a^3, \] and the only question is which values this can take. Well, this is a cubic polynomial in $a$. It's $1$ when $a=0$ and its derivative is $\frac{n(n+1)(2n+1)}2 a^2 - n$, which is negative for $a$ between $0$ and \[ \sqrt{\frac2{(n+1)(2n+1)}} = \sqrt{\frac1{(n+1)(n+1/2)}}, \] where it reaches its minimum over all positive values of $a$. (Notice that that value is less than $1/n$ as well.)

So the cubic polynomial, since it's continuous, can take on all values between its minimum and $1$. If we plug in the $a$ where it reaches its minimum value and simplify, we get that its minimum value is \[ 1- \frac23 n \sqrt{\frac2{(n+1)(2n+1)}} = 1 - \frac23 \sqrt{\frac1{(1+1/n)(1+1/2n)}}. \] Let's call that $y_n$. Then $y_n > 1/3$ for any $n$, but for $n$ sufficiently large, the expression inside the square root can get as close to $1$ as we want, so $y_n$ can get as close to $1/3$ as we want. Thus, to get any $c \in (1/3,1]$, first take $n$ large enough so that $y_n < c$, and then there will be some value of $a$ such that jumping at $0,a,2a,\cdots,na,1$ will give us $c$ (by e.g. the Intermediate Value Theorem, if you like).

See, I told you that the details of the proof wouldn't be all that nice. Actually, after checking the official solution I still like mine a little better (it's essentially the same, of course).

Top 200 scores:
(62,3,0),(63,13,59).