Let $n$ be a positive integer. A frog starts on the number line at 0 . Suppose it makes a finite sequence of hops, subject to two conditions:
- The frog visits only points in $\left\{1,2, \ldots, 2^{n}-1\right\}$, each at most once.
- The length of each hop is in $\left\{2^{0}, 2^{1}, 2^{2}, \ldots\right\}$. (The hops may be either direction, left or right.)

Let $S$ be the sum of the (positive) lengths of all hops in the sequence. What is the maximum possible value of $S$ ?
We claim the answer is $\frac{4^{n}-1}{3}$.
We first prove the bound. First notice that the hop sizes are in $\left\{2^{0}, 2^{1}, \ldots, 2^{n-1}\right\}$, since the frog must stay within bounds the whole time. Let $a_{i}$ be the number of hops of size $2^{i}$ the frog makes, for $0 \leq i \leq n-1$.
Claim - For any $k=1, \ldots, n$ we have
$$
a_{n-1}+\cdots+a_{n-k} \leq 2^{n}-2^{n-k} .
$$

Proof. Let $m=n-k$ and look modulo $2^{m}$. Call a jump small if its length is at most $2^{m-1}$, and large if it is at least $2^{m}$; the former changes the residue class of the frog modulo $2^{m}$ while the latter does not.

Within each fixed residue modulo $2^{m}$, the frog can make at most $\frac{2^{n}}{2^{m}}-1$ large jumps.
(As an example, when $n=3$ this means there are at most four hops of length 4 , at most six hops of length 2 or 4 , and at most seven hops total. Of course, if we want to max the length of the hops, we see that we want $a_{2}=4, a_{1}=2, a_{0}=1$, and in general equality is achieved when $a_{m}=2^{m}$ for any $m$.)
Now, the total distance the frog travels is
$$
S=a_{0}+2 a_{1}+4 a_{2}+\cdots+2^{n-1} a_{n-1} .
$$

We rewrite using the so-called "summation by parts":
$$
\begin{array}{l}
S=a_{0}+a_{1}+a_{2}+a_{3}+\ldots+\quad a_{n-1} \\
+a_{1}+a_{2}+a_{3}+\ldots+\quad a_{n-1} \\
+\quad 2 a_{2}+2 a_{3}+\ldots+2 a_{n-1} \\
+\quad 4 a_{3}+\ldots+\quad 4 a_{n-1} \\
\vdots \quad \ddots \\
+\quad 2^{n-2} a_{n-1} \text {. } \\
\end{array}
$$

Hence
$$
\begin{aligned}
S & \leq\left(2^{n}-2^{0}\right)+\left(2^{n}-2^{1}\right)+2\left(2^{n}-2^{2}\right)+\cdots+2^{n-2}\left(2^{n}-2^{n-1}\right) \\
& =\frac{4^{n}-1}{3} .
\end{aligned}
$$

It remains to show that equality can hold. There are many such constructions but most are inductive. Here is one approach. We will construct two family of paths such that there are $2^{k}$ hops of size $2^{k}$, for every $0 \leq k \leq n-1$, and we visit each of $\left\{0, \ldots, 2^{n}-1\right\}$ once, starting on 0 and ending on $x$, for the two values $x \in\left\{1,2^{n}-1\right\}$.
The base case $n=1$ is clear. To take a path from 0 to $2^{n+1}-1$.
- Take a path on $\left\{0,2,4, \ldots, 2^{n+1}-2\right\}$ starting from 0 and ending on 2 (by inductive hypothesis).
- Take a path on $\left\{1,3,5, \ldots, 2^{n+1}-1\right\}$ starting from 1 and ending on $2^{n+1}-1$ (by inductive hypothesis).
- Link them together by adding a single jump $2 \rightarrow 1$.

The other case is similar, but we route $0 \rightarrow\left(2^{n+1}-2\right) \rightarrow\left(2^{n+1}-1\right) \rightarrow 1$ instead. (This can also be visualized as hopping along a hypercube of binary strings; each inductive step takes two copies of the hypercube and links them together by a single edge.)
Remark (Ashwin Sah). The problem can also be altered to ask for the minimum value of the sum of the reciprocals of the hop sizes, where further we stipulate that the frog must hit every point precisely once (to avoid triviality). With a nearly identical proof that also exploits the added condition $a_{0}+\cdots+a_{n-1}=2^{n}-1$, the answer is $n$. This yields a nicer form for the generalization. The natural generalization changes the above problem by replacing $2^{k}$ with $a_{k}$ where $a_{k} \mid a_{k+1}$, so that the interval covered by hops is of size $a_{n}$ and the hop sizes are restricted to the $a_{i}$, where $a_{0}=1$. In this case, similar bounding yields
$$
\sum_{i=1}^{2^{n}-1} \frac{1}{b_{k}} \geq \sum_{i=0}^{n-1}\left(\frac{a_{k+1}}{a_{k}}-1\right)
$$

Bounds for the total distance traveled happen in the same way as the solution above, and equality for both can be constructed in an analogous fashion.