The score breakdown for this problem is as follows: 3 zeroes 9 ones 38 twos 0 threes 2 fours 9 fives 1 six 28 sevens Consider yourself warned.

We claim the answer is $\frac{4^n - 1}{3}$. We first prove the bound. First notice that the hop sizes are in $\{2^0, 2^1, \ldots, 2^{n - 1}\}$, 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\le i\le n - 1$. Claim: For any $k = 1, \dots, n$ we have \[ a_{n-1} + \dots + a_{n-k} \le 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. So the total number of large jumps is at most $2^m \left( \frac{2^n}{2^m} - 1 \right) = 2^n - 2^m$. $\blacksquare$ (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 + 2a_1 + 4a_2 + \dots + 2^{n-1} a_{n-1}. \]We rewrite using the so-called ``summation by parts'': \begin{align*} S &= a_0 + a_1 + a_2 + a_3 + \dots + a_{n-1} \\ &+ a_1 + a_2 + a_3 + \dots + a_{n-1} \\ &+ 2a_2 + 2a_3 + \dots + 2a_{n-1} \\ &+ 4a_3 + \dots + 4a_{n-1} \\ &+\vdots \\ &+ 2^{n-2}a_{n-1}. \\ \end{align*}Hence \begin{align*} S &\le (2^n-2^0) + (2^n-2^1) + 2(2^n-2^2) + \dots + 2^{n-2}(2^n-2^{n-1}) \\ &= \frac{4^n-1}{3}. \end{align*} 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\le k\le n - 1$, and we visit each of $\{0, \ldots, 2^n - 1\}$ once, starting on $0$ and ending on $x$, for the two values $x\in\{1, 2^n - 1\}$. The base case $n = 1$ is clear. To take a path from $0$ to $2^{n+1}-1$. Take a path on $\{0, 2, 4, \ldots, 2^{n+1} - 2\}$ starting from $0$ and ending on $2$ (by inductive hypothesis). Take a path on $\{1, 3, 5, \ldots, 2^{n+1} - 1\}$ starting from $1$ and ending on $2^{n+1}-1$ (by inductive hypothesis). Link them together by adding a single jump $2 \to 1$. The other case is similar, but we route $0 \to (2^{n+1}-2) \to (2^{n+1}-1) \to 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|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}\ge\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.

By the way, the solution to this problem is the bit-reflection of what's known as the n-bit Gray code in computer science. The explicit formula for the k-th position of the frog is given by $\text{reverse}(k \oplus (k \gg 1))$, where $\oplus$ is bitwise XOR and $\gg$ is a bitshift.

@Below: you're right, this doesn't solve the entire problem. Seems like considering the reverse sum is the only clean way...

Did anyone else get the solution in the case the frog jumps to all points, then spend another 3 hours trying to generalize? The thing I did was consider $a_1+\cdots+a_k$ (using Evan's notation) and bound that by the fact that mod $2^{k+1}$, all residue classes are hit. This works for the case where all points are hit, but as far as I know, is impossible to generalize. I didn't see the idea to consider sums from $a_n$ backwards. In retrospect, this is something I should have obviously tried (given I tried all sorts of random crazy stuff for 3 hours, mainly about bounding by looking at mod powers of 2), but of course, in retrospect is a dangerous phrase, especially for olympiads..........

The frog can start from any point from $1,2,...,m$ and is allowed to visit any point at most once. Then the maximum sum of lengths of hops is given by $s_m$ where $s_1=0 , s_2=1$ and $$s_{2m}=4s_m+1 $$$$ s_{2m+1}=2(s_m+s_{m+1})+1$$For $m=1,2 $ this is obvious now for some $1,2,..,n$ if there are $\lfloor n/2 \rfloor $ even and $\lceil n/2 \rceil$ odd numbers then the frog does the $\lfloor n/2 \rfloor $ process at the evens (with double hops)jumps by $1$ and does the $\lceil n/2 \rceil$ process at the odds (or vice versa)which shows that $s_n$ is attainable . Now alter the problem and let the frog do any jump so that he starts at $a_1$ goes to $a_2,a_3,...$ and stops at $a_m$ We show that $$2^{v_2(a_2-a_1)}+...+2^{v_2(a_m-a_{m-1})} \le s_m $$Which is however pretty straightforward with induction and proves the initiall statement.Just observe that when rearranging $a_i$ to get all evens and odds succesively in two sequences in the same order they appeared before increases this sum and implement the induction for these two sequences . (there will also be one $2^{v_2(a_i-a_{i-1})}=1$ among the summands)

Here is an outline of an amusing solution submitted by a contestant, which allows a "greedy" strategy to actually work. As shown above, there exists a path with $S = \tfrac{4^n - 1}{3}$, so we prove that we cannot do better. Create a weighted complete graph on $\{0, \dots, 2^n - 1\}$, labeling an edge $x \sim y$ with $2^{\nu_2(x - y)}$. (Note that this is consistent with the weights given in the problem.) We claim that it has no spanning tree with weight larger than $\tfrac{4^n - 1}{3}$. By Kruskal's algorithm, an optimal spanning tree is obtained by greedily choosing edges; now it's easy to see that the maximal spanning tree has weight $\tfrac{4^n - 1}{3}$.

Define a new game, such that the frog can either move a distance which is a power of 2, and add $2^k$ to its score, or "teleport" by any other length, and add $1/2$ to his score. Also, let $A_n$ be the max answer if we can start at any point between $0$ and $2^n-1$. (In fact, we will show that $A_n$ can be achieved starting at any position.) We claim that $A_n=\frac{4^n-1}{3}$, and the optimal strategy cannot include a hop of score $\frac{1}{2}$. We will prove this with induction. The base case of $n=1$ is clear, because we get $1$ no matter if we start at $0$ or $1$, and this obviously doesn't include a hop of score $1/2$. For the inductive step, suppose that $n-1$ works. Now, given a move sequence on the numbers $0$ to $2^n-1$, I claim that there exists a pair of move sequences on games of size $n-1$, such that the sum of their scores times two plus one is greater than or equal to the score of the move sequence in the $n$ game. This immediately bounds our answer at $4*\frac{4^{n-1}-1}{3}+1=\frac{4^n-1}{3}$, which is what we want to show. To prove this claim, consider the evens and the odds as separate games. Also, define a switching move to be a move which alters the parity of the number. Clearly, the only switching moves are $1$, and any odd number jump (with value $1/2$.) A switching move has value at most $1$, and can be thought of as a teleport in the respective games, since if we exclude the last switching move, every switching move must be succeeded by another one which brings the sequence of moves back to the initial parity, and results in an effective jump of arbitrary length. We will construct our two subgames in the following manner: 1) If the initial game has a move from $2m$ to $2n$, then our even subgame will have the move from $m$ to $n$. 2) Likewise, if the game has move $2m+1$ to $2n+1$, then our oddgame will have the move from $m$ to $n$. 3) If we have two consecutive switching moves from $2m$ to $2n+1$, then $2x+1$ to $2y$, then our even subgame will have a teleport from $m$ to $y$. (likewise for odds.) It is not hard to see that if these two subgames have score $S_e$ and $S_o$ respectively, then our original game has value at most $2(S_e+S_o)+1$, and this bound is strict if our original game had a teleport. (The 1 comes from the final switching move.) The construction is easy, though. If we started with an even number, then we just construct the maximum game on the even numbers first (using induction), then add one to switch to the odds, and then construct another maximum game on the odd numbers. The construction is the same when we start with an odd number.

We claim that the answer is $\frac{2^{2n}-1}{3}$. This can be achieved by a sequence of moves $a_1,a_2,\dots,a_{2^n-1}$ such that for any nonnegative integer $m$, $a_i=2^m$ if and only if $v_2(i)={n-m-1}$. The directions are arbitrarily chosen as long as the resulting position lies in the range (which is always possible). Notice that in any continuous subsequence of the moves, the move with smallest power of 2 appears only once. This makes sure that each point is visited at most once, since if some point is visited twice, there exists a subsequence of moves that sum to zero mod $2^n$, which is clearly impossible. The sum of lengths of moves equals $$\sum_{i=0}^{n-1} 2^{2i}=\frac{2^{2n}-1}{3}.$$ Now we prove that this is the upper bound. Suppose that there are $k$ moves in total. Notice that if there are $2^{n-i}$ continuous moves that are divisible by $2^i$, then the frog must visit one point more than one time. Thus, the number of moves divisible by $2^i$ is smaller than or equal to $$\left\lfloor\frac{k}{2^{n-i}}\right\rfloor(2^{n-i}-1)+\left\{\frac{k}{2^{n-i}}\right\}\cdot 2^{n-i}.$$Because this is increasing, we have that the above expression is smaller than or equal to $$(2^i-1)(2^{n-i}-1)+2^{n-i}-1=2^n-2^i.$$Suppose that we have $a_i$ moves of length $2^i$. Then we want to find the maximum of $\sum_{i=0}^{n-1} 2^i a_i$: \begin{align*} \sum_{i=0}^{n-1} 2^i a_i &= \sum_{i=0}^{n-1} a_i + \sum_{j=1}^{n-1} 2^{j-1} \left(\sum_{i=j}^{n-1} a_i\right)\\ &\le 2^n-1+\sum_{j=1}^{n-1} 2^{j-1}(2^n-2^j)\\ &\le 2^n-1+2^{2n-1}-2^n-2\left(\frac{2^{2n-2}-1}3\right)\\ &= 2^{2n-1}-1-\frac13\cdot2^{2n-1}+\frac23\\ &= \frac{2^{2n}-1}{3} \end{align*}which is the maximum value.

Cute! The answer is $(4^n-1)/3$ Lemma: The number of hops such that $2^k$ divides the length of the hop ($0 \le k \le n-1$) (denoted by $s_k$) is $\le 2^n-2^k$ Proof: Note that there are $2^k$ distinct residue classes modulo $2^k$, and except the class we're originally in (i.e. $0$ modulo $2^k$), for any number in any other class to be reached by a hop of length divisible by $2^k$, at least one of the numbers in that class must have earlier been reached by a hop of length not divisible by $2^k$. Hence summing the maximum number of numbers in each class reached by a hop of length divisible by $2^k$ we get $s_k \le (2^{n-k}-1)*2^k = 2^n - 2^k$. Under the condition of the lemma, the maximum $S$ we can get is $\le 1^2+2^2...+(2^{n-1})^2 = (4^n-1)/3$ To see why, let the sequence the lengths of the hops in non-decreasing order (initial lengths are to be put $0$ if number of hops is $< 2^n-1$) be $l_1, l_2, ..., l_{2^n-1}$, and note that $l_i < 2^k$ if $i < 2^k$. We prove this can be achieved by induction on $n$. The base case $n = 1$ has the trivial unique construction. To go from a construction for $n$ to one for $n+1$, let the sequence of directed lengths of hops in the order they are to be performed in an equality case for $n$ be $h_1, h_2, ..., h_{2^n-1}$. To get the sequence for $n+1$, insert $+2^n$ before $h_1$, and insert $-2^n$ after each $h_i$ for $i$ odd, and $+2^n$ after each $h_i$ for $i$ even. It is easy to see that this gets a valid sequence (we are simply lifting the sequence for $n$ to $n+1$ by working modulo $2^n$, covering both the positions in the same residue class modulo $2^n$ in a pair of consecutive moves, alternating between the two halves $0, ..., 2^n-1$ and $2^n, ..., 2^{n+1}-1$).

I claim the answer is $\frac{4^n-1}{3}$. Construction: Use induction; strengthen the claim to include the fact that the construction will end in $1$ or $2^n-1$. Base cases: $(0, 1)$, $(0, 2, 1, 3)$. Inductive step: first do the sequence for $n-1$ except all the hop lengths are multiplied by 2; this way we get all evens and end up at $2$ or $2^n-2$. Then go up to $2^n-1$ or down to $1$; then do the $n-1$ sequence if we're at $1$, or the reverse of the $n-1$ sequence if we're at $2^n-1$ (it'll have the same total length by symmetry), again with the hop lengths multiplied by $2$. Then we'll either end in $2^n-1$ or $1$ and $f(n)=4f(n-1)+1=\frac{4^n-1}{3}$ which completes the induction. Bound: Let $a_k$ of the jumps be length $k$. Suppose that $c$ of the residues mod $2^k$ are hit; then, by total numbers hit, $a_0+...+a_{n-1}\le 2^{n-k}c-1$. Also note that a move of length $2^k$ or more does not change the residue mod $2^k$, so since there are $c$ residues there must be $c-1$ residue changes, we have $a_0+...+a_{k-1}\ge c+1$. Hence we have $a_k+...+a_{n-1}\le 2^{n-k}c-1-(c-1)=c(2^{n-k}-1)\le 2^k(2^{n-k}-1)=2^n-2^k$ for all $k$. Multiplying this by $2^{k-1}$ we have $2^{k-1}a_k+2^{k-1}a_{k+1}+...+2^{k-1}a_{n-1}\le 2^{k-1}(2^n-2^k)$. Summing this up for $k\in [1, n-1]$ and then adding it to $a_0+a_1+...+a_{n-1}\le 2^n-1$ at the end gives $S=\sum_{k=0}^{n-1}2^ka_k\le \frac{4^n-1}{3}$, as desired. $\blacksquare$

The answer is $\tfrac{4^n-1}{3}$. We first show a construction, then we prove this is maximal. The construction is inductive, with $n=1$ trivial. We will end with $2^i$ jumps for each $i\ge 0$. First jump by $2^n$. Take the construction for $n$, and between jumps alternate between $+2^n$ and $-2^n$. This ends us up with $2^n$ jumps of $2^n$, as needed. Claim: The number of hops whose length is divisible by $2^k$ is at most $2^n-2^k$. Proof: This proof is really nice. Color with color $i$ a number which is $i \pmod{2^k}$, for all $i=0,\ldots,2^k-1$. There are $2^{n-k}$ copies of color $i$, for each $i$. Now, any hop of length divisible by $2^k$ does not change colors. Within each color, we can hit at most $2^{n-k}$ numbers. Suppose we cover a total of $x$ colors by the end. The number of jumps of length divisible by $2^k$ are ``intra-color''. Since there are $2^{n-k}-1$ numbers in each color, we can have at most $2^{n-k}-1$ intra-color jumps per color. Taking this bound over all $x$ colors tells us that there's at most $x(2^{n-k}-1)$ intra-color jumps overall. Now we need to bound $x$. Since there are only $2^k$ colors, $x\le 2^k$. Hence there's at most $2^k(2^{n-k}-1) = 2^n-2^k$ intra-color jumps in total. $\square$ Claim: $S\le \tfrac{4^n-1}{3}$. Proof: This is a computation, using the above bounds. Let there be $a_i$ jumps of length $2^i$. The claim tells us that $a_{n-1} + a_{n-2} + \cdots + a_k \le 2^n-2^k$. Unfortunately, we cannot directly bound $a_i$ from this. The sum of the lengths of all jumps is $S=2^{n-1}a_{n-1} + 2^{n-2}a_{n-2} + \cdots + 2^0a_0$. However, $S$ is also equal to \begin{align*} &\ \ \ 2^{n-2}a_{n-1} \\ & + 2^{n-3}a_{n-1} + 2^{n-3}a_{n-2} \\ &+ \cdots \\ & + 2^0a_{n-1} + 2^0a_{n-2} + \cdots + 2^0a_1 \\ & + 1 a_{n-1} + 1a_{n-2} + \cdots + 1a_1 + 1a_0. \end{align*}Using the bounds we found, the above is at most \begin{align*} & \ \ \ \ 2^{n-2}(2^n - 2^{n-1}) + 2^{n-3}(2^n-2^{n-2}) + \cdots + 2^0(2^n - 2^1) + (2^n-2^0) \\ &= 2^n(2^{n-2} + 2^{n-3} + \cdots + 2^0) - [2^{2n-3} + 2^{2n-5} + \cdots + 2^1] + (2^n-2^0) \\ &= 2^n (2^{n-1} - 1) - 2\left(\frac{4^{n-1}-1}{3}\right) + (2^n-2^0) \\ &= \frac{4^n-1}{3}. \end{align*}This proves the bound. $\square$

same sol as many @above but posting for reference We claim the answer is $\frac{4^n - 1}{3}$, and we will begin with the construction. As an illustrative example, we show the construction for $n = 1$, $n = 2$, and $n = 3$; $n = 1$ is trivial. For $n = 2$, partition the numbers into equal size sets of odd versus even to get $(0, 2)$, $(1, 3)$. Then, observe that we simply need to repeat the $n = 1$ path for odd and even numbers(where the length of each jump is doubled), and then add a jump of length $1$ to change parity. For $n = 3$, we partition into $(0, 2, 4, 6)$ and $(1, 3, 5, 7)$, then use analogous logic. This generalizes readily to yield the recurrence $F(n) = 4F(n - 1) + 1$, and we can show by induction that $F(n) = \frac{4^n - 1}{3}$. We now set about proving the bound; this requires the key lemma that for $k$ ranging from $1$ to $n - 1$, we have $$a_{n - 1} + a_{n - 2} + \cdots + a_{n-k} \leq 2^n - 2^{n-k}.$$Consider what happens when we take the allowed integers $(0, 1, \cdots, 2^n - 1)$ modulo $2^{n-k}$; if we let $j$ be a residue mod $2^{n-k}$, then there are exactly $2^k$ numbers congruent to $j \pmod{2^{n-k}}$. Now, observe that adding or subtracting $2^{n-k}$ or any greater powers of two does not affect the residue mod $2^{n-k}$. As a result, in order for the frog to be able to switch between residue classes, one of the $2^k$ numbers with a given residue mod $2^{n-k}$ must have been landed on as a result of a jump with length smaller than $2^{n-k}$. This yields the desired upper bound of $2^{n-k} (2^k - 1) = 2^n - 2^{n-k}$. Next, define $a_i$ as the number of jumps of length $2^i$. We sum the $n$ inequalities $$\begin{aligned} a_0 + a_1 + a_2 + a_3 + \cdots + a_{n-1} &\leq 2^n - 1 \\ a_1 + a_2 + a_3 + \cdots + a_{n-1} &\leq 2^n - 2^1 \\ 2a_2 + 2a_3 + \cdots + 2a_{n-1} &\leq 2^1(2^n - 2^2) \\ 4a_3 + \cdots + 4a_{n-1} &\leq 2^2(2^n - 2^3) \\ & \cdots \\ 2^{n-2} a_{n-1} &\leq 2^{n-2} (2^n - 2^{n-1}). \end{aligned}$$Noticing that $S = a_0 + 2a_1 + \cdots + 2^{n-1} a_{n-1}$, this simplifies to the desired $S \leq \frac{4^n - 1}{3}$.

The answer is $\boxed{\frac{4^n-1}{3}.}$ Bound: Let $a_i$ be the number of hops of length $2^i$ used. The key claim is as follows: Claim: [Bound on partial sums of $a_i$] For any $1 \leq i \leq n,$ the sum $a_{n-1}+a_{n-2}+ \cdots + a_{n-i} \leq 2^n - 2^{n-i}.$ Proof: For each $1 \leq k \leq 2^{n-i},$ consider the number of hops from two elements with residue $k\pmod {2^{n-i}}.$ This is at most $2^i-1,$ so over all $k$ we have that the number of hops from two elements with distance $\geq 2^{n-i}$ is at most $2^n-2^{n-i}.$ Now note that $$\begin{aligned} &2^n-1 \geq a_0+a_1+a_2+a_3+a_4+\cdots+a_{n-1}& \\ &2^n-2^1 \geq a_1+a_2+ a_3+a_4\cdots + a_{n-1}& \\ &2^1(2^n-2^2) \geq 2a_2+ 2a_3+2a_4+ \cdots + 2a_{n-1}& \\ &2^2(2^n-2^3) \geq 2^2a_3 + 2^2a_4+ \cdots + 2^2a_{n-1}& \\ &2^3(2^n-2^4) \geq 2^3a_4 + \cdots + 2^3a_{n-1}& \\ &\cdots \\ &2^{n-2}(2^n-2^{n-1}) \geq 2^{n-2}a_{n-1}& \\ \end{aligned}$$ Summing these $n$ inequalities yields $\frac{4^n-1}{3} \geq S$ as desired. Construction: Here is a construction for $n=4,$ which is easily generalizable: $$0 \to 8 \to 4 \to 12 \to 14 \to 6 \to 2 \to 10 \to 9 \to 1 \to 5 \to 13 \to 15 \to 7 \to 3.$$Remarks: Nice problem but I think too difficult for its placement. I think the bound is really tricky, as there are a lot of seemingly viable ways to proceed, using induction or other techniques but unfortunately fail. The main way I motivated this solution is thinking about how such a solution to this problem could be created. The solution should exploit the equality cases. Of course this problem is in the OTIS equality unit, but even without I think the fact that equality holds when each jump of length $2^i$ occurs exactly $2^i$ times should be something important. At first I tried bounding each jump separately using induction and smoothing (?), but in hindsight after 30 minutes of that not working I should've just moved on. However, thinking about bounding the number of jumps of length $2^i$ one at a time is good motivation for the actual solution, even if it didn't work. The fact that bounding one at a time doesn't work is the main motivation about thinking of bounding multiple lengths of jumps at the same time. In fact, I think realizing to think about this is the main step towards the solution. There's only really one way to do this that makes sense: thinking about jumps with length greater than or equal to some $2^i.$ Once you try this, the problem is basically solved. The equality cases tell us what the bound must be, and constructing the equality case is actually good motivation for proving the main claim. In my equality case, I tried to jump to all numbers divisible by $2^i$ before moving to numbers not divisible by $2^i$ for each $i.$ Now with the claim proved, the problem basically dissolves, nice!

Why is this problem so hard... Clearly jump sizes are $\in \{2^0, \ldots 2^{n -1}\}$ because the frog is bound by $[1, 2^n - 1]$. Suppose the frog makes a $2^i$ move $a_i$ times, for each $i$ from $0$ to $n-1$. We wish to minimize\[\sum_{i = 0}^{n-1} 2^ia_i.\]In fact, I claim that we can place the following bound: Claim: We have $a_{n - k} + \ldots + a_{n-1} \leq 2^{n} - 2^{n-k}$ for all $k$ from $1$ to $n$. Proof: We want to show that the number of jumps whose size is $\geq 2^{n.- k}$ is at most $2^{n-k}(2^k - 1)$. Suppose we split the number line section from $0$ to $2^n - 1$ into $2^k$ sections of modulo $2^{n - k}$ residue classes, for example\[\{0, \ldots , 2^{n-k} - 1\} \cup \{2^{n-k}, \ldots , 2^{n - k + 1} - 1\} \cup \ldots \cup \{2^{n} - 2^{n - k}, \ldots , 2^n - 1\}.\]For each residue modulo $2^{n - k}$ the frog can jump to at most $2^k - 1$ different sections (not including the original) and there are $2^{n - k}$ residues, hence a total of $\leq 2^{n-k}(2^k - 1) = 2^n - 2^{n - k}$ such jumps as desired. $\square$ Now, we wish to maximize \begin{align*} \sum_{i = 0}^{n-1} 2^ia_i &= a_0 + 2a_1 + 4a_2 + \ldots + 2^{n-1}a_{n-1}\\&\leq S_0 + S_1 + 2S_2 + 4S_3 + \ldots + 2^{n-2}S_{n-1} \end{align*}where $S_i = a_i + \ldots + a_{n-1}$. Now substitute in $S_i \leq 2^n - 2^{i}$ for all $i$ from $0 \to n - 1$. We evaluate as follows:\begin{align*}S_0 + 2S_2 + 4S_3 + \ldots + 2^{n-2}S_{n-1} &= (2^n - 2^0) + (2^n - 2^1) + \ldots + 2^{n-2} \cdot (2^n - 2^{n-1})\\ &= (1 + 1 + 2 + \ldots + 2^{n-2}) \cdot 2^n - (2^0 + 2^1 + 2^3 + 2^5 + \ldots + 2^{2n - 3})\\&= 2^{2n-1} - \left(1 + 2\cdot \frac{4^{n-1} - 1}{3}\right)\\&= \frac{4^n - 1}{3}\end{align*}so indeed our maximum has been established. I am too lazy to post the construction.

We claim that the answer is $\frac{4^n-1}{3}$, which can be achieved by splitting the points into $2$ sets of points $\{0,1,...,2^{n-1}-1\};\{2^{n-1},2^{n-1}+1,...,2^n\}$ and using $2^{n-1}$ hops of length $2^{n-1}$ to travel between the sets. Finally, we use that the frog gives $2^k$ hops of length $2^k$ for all $0 \leq k \leq n-1$, by constructing the example inductively, with the cases $n=1,2$ being easy. Now, we will prove the upper bound. Let $a_k$ the quantity of hops of length $2^k$ that the frog has given. We prove the following claim: Claim: $a_k+a_{k+1}+...+a_{n-1} \leq 2^n-2^k$ for all $ 0 \leq k \leq n-1$. Proof: Split the points into $2^{n-k}$ sets of size $2^k$ in the following way: $$\{0,1,...,2^k-1\};\{2^k,2^k+1,...,2^{k+1}-1\};...;\{2^{n-1},2^{n-1}+1,...,2^n\}$$$\implies$ since the jumps of length at least $2^k$ are invariant $\pmod{2^k}$, we can give at most $2^{n-k}-1$ hops of length at least $2^k$ with the same remainder $\pmod{2^k}$. Since we have $2^k$ remainders $\pmod{2^k}$, the frog can give at most $(2^{n-k}-1)2^k=2^n-2^k$ hops with length at least $2^k$. $$\implies a_k+a_{k+1}+...+a_{n-1} \leq 2^n-2^k$$$\square$ Now, let $S_k=a_k+a_{k+1}+...+a_{n-1} \leq 2^n-2^k$, from the claim $$\implies \sum_{k=0}^{n-1}a_k2^k=S_0+S_1+2S_2+...+2^{n-2}S_{n-1} \leq (2^n-1)+(2^n-2)+2(2^n-2^2)+...+2^{n-2}(2^n-2^{n-1})$$$$=(2^n-1)+2^n(1+2+...+2^{n-2})-2(1+2^2+...+2^{2n-4})$$$$=2^{2n-1}-1-2(\frac{4^{n-1}-1}{3})$$$$=\frac{4^n-1}{3}$$as desired! $\blacksquare$

The answer is $\boxed{\frac{4^n-1}{3}}.$ $\emph{Construction: }$ Assume the sequence $$0=a_1\to a_2\to\dots\to a_{2^{n-1}}=1$$achieves the claimed maximum for $n-1.$ Then, $$0=2a_1\to 2a_2\to\dots\to 2a_{2^{n-1}}=2$$$$\to 3=2a_{2^{n-1}}+1\to 2a_{2^{n-1}-1}+1\to\dots 2a_{1}+1=1$$clearly works for $n,$ so we are done by induction. $\blacksquare$ $\emph{Proof: }$ Let $s_i$ denote the number of jumps of size at least $2^i.$ Note that there cannot be $2^{n-i}$ consecutive jumps of size at least $2^i,$ so we have $$s_i\le 2^n-1-\left\lfloor\frac{2^n-1}{2^{n-i}}\right\rfloor=2^n-2^i.$$Therefore, since the number of jumps of size $2^i$ is $s_{i}-s_{i+1},$ we have \begin{align*} S &= \sum_{i=0}^{n-1}2^i(s_{i}-s_{i+1})\\ &= a_0+\sum_{i=1}^{n-1}2^{i-1}s_i.\\ &\le 2^{n}-1+\sum_{i=1}^{n-1}(2^{n+i-1}-2^{2i-1})\\ &= 2^n-1+(2^{2n-1}-2^{n})-\left(\frac{2^{2n-1}-1}{3}\right)\\ &= \frac{4^n-1}{3}, \end{align*}as desired.

Solved with nukelauncher. The answer is \(\frac{4^n-1}3\). \bigskip Construction: We show by induction on \(n\) it is possible to find a sequence of hops of length \(1+4+\cdots+4^{n-1}\) starting at 0 and ending at 1. The base case is trivial. If we have such a sequence of moves \(0\to a_1\to\cdots\to a_k\to1\) on the set \(\{1,2,\ldots,2^n-1\}\), then the sequence \[0\to2a_1\to\cdots\to2a_k\to2\to3\to(2a_k+1)\to\cdots\to(2a_1+1)\to1\]is a valid sequence on \(\{1,2,\ldots,2^{n+1}-1\}\). \bigskip Upper bound: Let there be \(a_i\) hops of length \(2^i\) for each \(i\). The key estimate: Claim: \(a_i+a_{i+1}+\cdots+a_n\le2^n-2^i\). Proof. We want to upper-bound the number of jumps of length divisible by \(2^i\). We can split the possible points into \(2^i\) sets of the form \(\{k,2^i+k,2\cdot2^i+k,\ldots\}\), so that each such jump sends the frog from one point to another point in the same set. There are \(2^{n-i}-1\) possible jumps between elements of each set, so the number of possible jumps is at most \(2^i(2^{n-i}-1)\). \(\blacksquare\) At last, observe the inequalities \begin{align*} a_0+a_1+a_2+\cdots+a_{n-1}&\le2^n-1\\ a_1+a_2+\cdots+a_{n-1}&\le2^n-2\\ a_2+\cdots+a_{n-1}&\le2^n-2^2\\ &\;\vdots \end{align*}A linear combination provides an upper bound for \(2^{n-1}a_{n-1}+2^{n-2}a_{n-2}+\cdots+2^0a_0\), and in our construction above it is easy to see that equality holds. This completes the proof.

The answer is $\frac{4^n-1}{3}$. Construction: We use an inductive construction. Suppose the construction for $n-1$ is $0\rightarrow a_1\rightarrow a_2\rightarrow \cdots \rightarrow a_{2^{n-1}-1}$, then the construction for $n$ is $0\rightarrow a_1\rightarrow 2^{n-1}+a_1\rightarrow 2^{n-1}+a_2\rightarrow a_2\cdots \rightarrow a_{2^{n-1}-1}+2^{n-1}$. Bound: let $x_i$ be the number of steps of length $i$. Claim: $\sum\limits_{i=0}^k x_i\ge 2^{k+1}-1$. Proof: Consider residues mod $2^{k+1}$. Notice only using steps of length $2^0, \cdots, 2^k$ can swap its remainder. Since the remainder needs to be swapped $2^{k+1}-1$ times, we're done. We wish to maximize $\sum\limits_{i=0}^k x_i2^i$ subject to the above condition and $\sum\limits_{i=0}^{n-1} x_i = 2^n-1$. Let $y_i=x_i-2^i$, then we wish to show $\sum\limits_{i=0}^k y_i2^i\le 0$ given $\sum\limits_{i=0}^{n-1} y_i=0, \sum\limits_{i=k}^{n-1} y_i\le 0$. If $y_{n-1}=0$, we can simply induct down. Otherwise, $y_{n-1}<0$, then we take the maximal $k$ such that $\sum\limits_{i=k}^{n-1} y_i= 0$. Note $k$ exists since $k=0$ satisfies this property. Then we can check that incrementing $y_{n-1}$ by 1 and decrementing $y_k$ by 1 would still obey the constraints but give a bigger sum.

The answer is $\boxed{\frac{4^n-1}{3}}$. We demonstrate inductively that this can be achieved: in particular, we claim we can use exactly $2^i$ moves of length $2^i$ for each $i \le n-1$. The base case is clear. If $(m_1, \cdots, m_{2^{k-1}})$ is a sequence of moves satisfying the aforementioned description when $n=k$, then when $n=k+1$ it's clear that the sequence of moves$$(2^k, m_1, -2^k, m_2, 2^k, m_3, -2^k, m_4, \cdots , 2^k, m_{2^{k-1}}, -2^k)$$works (for instance, consider pairing up the numbers which differ by $2^k$).

).

Similar solution to Idio-logy, I think. The story of how I found this solution is rather funny. When solving this I didn't have the problem statement in front of me, so I misremembered the condition that the frog visits the points at most once, instead believing that it visited the points exactly once. This led me to a fairly quick solution (basically the same one below, but with $q=1$). When I went to the thread to post my solution, I realized that I had misremembered the problem and managed to pick up my previous proof by introducing $q$. I honestly think without this misread the problem would've been much harder to do (the insight for this particular solution path is much less motivated), so being sloppy and not reading carefully helped me here The answer is $\frac{4^n-1}{3}$. I will prove the bound first. Suppose the frog visits $q2^n$ points in $\{0,1,2,\ldots,2^n-1\}$, where $0<q\leq 1$. Note that the frog always visits $0$, since it started there. Let $a_i$ denote the number of jumps the frog makes that are of length $2^i$. Note that for $i\geq n$ we have $a_i=0$. The key bound is the following: Claim: For $0\leq k \leq n-1$, we have $$a_0+a_1+\cdots+a_k \geq q2^{k+1}-1$$Proof: Suppose otherwise. Since moves of length $2^k$ or less are the only ones that change the residue class mod $2^{k+1}$ of the frog's position, it follows that the frog would hit less than $q2^{k+1}$ residue classes. Each residue class mod $2^{k+1}$ corresponds to $2^{n-k-1}$ spots, hence the frog would visit less than $q2^{k+1}\cdot 2^{n-k-1}=q2^n$ spots, which is impossible. $\blacksquare$ The total distance the frog travels is equal to $$T=a_0+2a_1+4a_2+\cdots+2^{n-1}a_{n-1}.$$Let $f(k)=a_0+a_1+\cdots+a_k$, so $f(k)\geq q2^{k+1}-1$. Also note that $f(n-1)=q2^n-1$. Then, this summation rewrites as $$f(0)+2(f(1)-f(0))+4(f(2)-f(1))+\cdots+2^{n-1}(f(n-1)-f(n-2))=2^{n-1}(q2^n-1)-(f(0)+2f(1)+\cdots+2^{n-2}f(n-2))$$Using the inequality, the RHS is at most $$2^{n-1}(q2^n-1)-(q(2+8+\cdots+2^{2n-3})-(1+2+\cdots+2^{n-2}))=q\left(2^{2n-1}-\frac{2}{3}\cdot (4^{n-1}-1)\right)-1=\frac{q(4^n+2)}{3}-1.$$Since $\frac{4^n+2}{3}>0$, the rightmost expression is in turn maximized when $q=1$, in which case it is equal to $\frac{4^n-1}{3}$, which is our desired bound. $\blacksquare$ Now I will provide a construction. For $n=1$ have the frog hop $0\to 1$. Now I will recursively create constructions for some $n$ that end at $1$ and $2^n-1$, provided that there exists a construction for $n-1$ ending at $1$ and one ending at $2^{n-1}-1$. To end at $1$, first double the construction for $n-1$ ending at $2^{n-1}-1$. Then move from $2^n-2$ to $2^n-1$ and run the doubled construction for $n-1$ in reverse, ending at $1$. To end at $2^n-1$, first double the construction for $n-1$ ending at $1$. Then move from $1$ and run the doubled construction for $n-1$ ending at $2^{n-1}-1$, ending at $2^n-1$. By induction, this establishes two constructions for all positive integers $n$. If we let $b_n$ denote the distance travelled in this series of moves, we have the recursion $b_n=4b_{n-1}+1$, which combined with $b_1=1$ gives $b_n=\frac{4^n-1}{3}$ for all $n$: the desired result. $\blacksquare$

This must be a really smart frog!

bever209 wrote:

If I'm reading this correctly, this solution is invalid, since the frog doesn't have to visit every point in $\{1,2,\ldots,2^n-1\}$. (Proof of bound)

We make the following claim: The maximum possible value of $S$ is $\frac{4^n-1}{3}$ Consider $a_k$ to be the number of moves of length $2^k$ made by the frog. Note that $k<n$ since the frog must remain within the given bounds. Claim $a_{n-1}+a_{n-2}+\cdots +a_{t} \leq 2^n- 2^t$ for all $0\leq t\leq n-1$ The proof is simply that the remainder modulo $2^t$ does not change for the above mentioned steps, and we can therefore bound the number of moves made within any residue class. Now just using the right weights along with each term we can bound $a_1+2a_2+4a_4+\cdots +2^n a_n$ as $\frac{4^n-1}{3}$ The construction is just induction, first hopping through the even values and then through the odd ones, always ending up at $1$ or $2^n - 1$

The answer is $\frac{4^n-1}{3}$. An example of how it is achieved can be constructed inductively in the following manner: Take the construction for $n=k$, where we would inductively have made sure that the process ends either at 1 or $2^k-1$, and scale it twice. In this way the frog has gone trough all even indices. Now it makes a jump of length $1$, and lands either at $1$ or $2^{k+1}-1$, and now it does the example again for $n=k$ scaled twice and either moved to the right with 1 or flipped. It's not hard to show that this indeed works. Now we'll prove the bound. Notice that the jumps of length $\geq 2^k$ are at most $2^n-2^k$. Indeed, consider the $2^k$ groups of indices $(0;2^k;2.2^k;....);(1;2^k+1;2.2^k+1...);...;(2^k-1;2.2^k-1;...);$ Jumps of length at least $2^k$ can be performed only between indices of the same groups, and at most $2^{n-k}-1$ such jumps in each group, which gives the desired total. Now it would be most optimal to pick $2^{n-1}$ jumps of length $2^{n-1}$; $2^{n-2}$ jumps of length $2^{n-2}$; and so on 1 jump of length 1; which when summing up gives the desired total distance.

The answer is $\frac{4^n-1}{3}$. We first show that it is always attainable. Proceed by induction on the statement: "$\frac{4^n-1}{3}$ is attainable no matter which of $0,1,2,\ldots, 2^n-1$ you start on." The base case $n=1$ is trivial, either $1$ to $0$ or $0$ to $1$, giving $\frac{4^1-1}{3}$. For the inductive step, if we start at any number $i\in\{0,1,\ldots, 2^{k+1}-1\}$, take the sequence of moves that worked for $n=k$ starting at $\left\lfloor \frac{i}{2}\right\rfloor$, except double the length of every hop. Then, move by $2^0$ to the left or right to $j$, and we repeat. Thus, starting at any $i$, we have travelled $$\frac{4^k-1}{3}\times 2\times 2+1=\frac{4^{k+1}-4}{3}+1=\frac{4^{k+1}-1}{3}$$completing the inductive step. To prove the bound, let $a_{n-1}, a_{n-2},\ldots, a_0$ be the number of jumps of $2^{n-1},2^{n-2},\ldots, 2^0$ respectively. By counting the number of pairs $(i,i+2^j)$ for each $j$ that the frog has not been to: \begin{align*} a_{n-1}&\leq 2^{n-1}\\ a_{n-1}+a_{n-2}&\leq 2^{n-1}+2^{n-2}\\ &\vdots\\ a_{n-1}+a_{n-2}+\ldots +a_0 &\leq 2^{n-1}+2^{n-2}+\ldots+ 2^{0} \end{align*}The distance that the frog travels is: $$d=2^{n-1}a_{n-1}+2^{n-2}a_{n-2}+\ldots+2^0a_0\leq 2^{n-1}\cdot 2^{n-1}+2^{n-2}\cdot 2^{n-2}+\ldots +2^0\cdot 2^0=\frac{4^n-1}{4-1}$$by the rearrangement inequality, as desired.

Solved with GoodMorning. The answer is $\boxed{\frac{4^n - 1}{3} } $. First we give a construction to show it works. In the $i$th hop, move $2^{n - \nu_2(i) - 1}$ units up or down, up if $i \equiv \{1,2\}\pmod 4$, and down otherwise. Such a construction will work for a total of $2^n - 1$ hops, so a sum of lengths of\[ 2^{n-1} \cdot 2^{n-1} + 2^{n-2} \cdot 2^{n-2} + \cdots + 2^0 \cdot 2^0 = \frac{4^n - 1}{3},\]as desired. Now we prove the bound. Fix any nonnegative integer $m\le n$. First notice that each residue modulo $2^m$ of the frog's location can be hit at most $2^{n-m}$ times by the frog. This implies that for a fixed residue $r$ modulo $2^m$, there are at most $2^{n-m} - 1$ hops that go from $r\pmod{2^m}$ to $r\pmod{2^m}$ (otherwise, the frog would hit $r\pmod{2^m}$ at least $2^{n-m} + 1$ times). Therefore the number of jumps with size at least $2^m$ is bounded above at $2^m \cdot (2^{n-m} - 1) = 2^n - 2^m$. Claim: For any sequence of nonnegative integers $x_0, x_1, x_2, \ldots, x_{n-1}$ such that $x_i + x_2 + \cdots + x_{n-1} \le 2^n - 2^i$ for each $1\le i\le m$, we have $\sum_{i=0}^{n-1} 2^i x_i \le \frac{4^n - 1}{3}$. Proof: Call such sequences valid. Suppose this was not the case and consider a valid sequence $(x_i)$ satisfying this with a maximal sum of of $2^i x_i$ over all $0\le i\le n -1 $ (greater than $\frac{4^n - 1}{3}$) Case 1: $x_i\ge 2^i$ for all $i$. We must have $\sum x_i \ge \sum_{i=0}^{n-1} 2^i = 2^n - 1$, but also $\sum x_i \le 2^n - 1$, so we have $x_i = 2^i$ for each $i$. In this case $\sum_{i=0}^{n-1} 2^i x_i = \frac{4^n - 1}{3}$, contradiction. Case 2: There exists $i$ with $x_i< 2^i$. Consider the largest positive integer $j<n$ such that $x_j < 2^j$. Let $(y_i)$ denote the sequence given by $y_i = x_i$ for all $i > j$ and $i < j - 1$, $y_j = x_j + 1$, $y_{j-1} = x_{j-1} - 1$. We have $\sum_{k=i}^{n-1} y_k= \sum_{k=i}^{n-1} x_k \le 2^n - 2^i$ as long as $i\ne j$ and\[ \sum_{k=j}^{n-1} y_k < x_j + 1 + \sum_{k=j + 1}^{n-1} x_k = x_j + 1 + \sum_{k = j + 1}^{n-1} 2^k = x_j + 1 + (2^n - 1) - (2^{j+1} - 1) \le 2^n - 2^j \]since $x_j + 1 \le 2^j$. This implies that the sequence $(y_i)$ is also valid. Now,\[ \sum_{i=0}^{n-1} 2^i y_i = \sum_{i=0, i\ne j-1,j}^{n-1} 2^i x_i + 2^j (x_j + 1) + 2^{j-1} (x_{j-1} - 1) = \sum_{i=0}^{n-1} 2^i x_i + 2^{j-1} > \sum_{i=0}^{n-1} 2^i x_i, \]so the sum is not maximal, contradiction. $\square$ Now if we let $x_i$ denote the number of hops with length $2^i$, we get $(x_i)$ is valid, so the sum of the length is equal to $\sum_{i=0}^{n-1} 2^i x_i \le \frac{4^n - 1}{3}$, as desired.

Solved with Om245. The problem isn't actually hard it merely takes a lot of time to work it out. Looking at the equality case helps a lot to motivate the solution. We claim that the maximum sum of lengths of jumps that the frog can execute is given by the function, \[S(n)=\frac{4^n-1}{3}\]When $n=1$ the problem is obvious so we deal with $n \ge 2$. We start off by providing a construction, via induction. We show that in fact there exists a sequence of hops for which $S$ achieves this claimed maximum, which end in positions $1$ and $2^n-1$ respectively. This is clear when $n=2$ since \[0 \to 2 \to 3 \to 1 \text{ and } 0 \to 2 \to 1 \to 3\]both have a hop-sum of $5$. Now, say we have two constructions for a positive integer $k$ where the hop-sum is $\frac{4^k-1}{3}$ and we start from $0$ and end up at positions $1$ and $2^k-1$ respectively. We call these two the $k$-one type path and $k$-end type paths respectively. Then, for $k+1$. Consider the even and odd numbered points seperately. The frog first scales up his sequence of moves on the $k$-end type path by two and stepping on the even numbered points, reaches $2^{k+1}-2$. Then, he does a hop of size one and goes to the point $2^{k+1}-2$. Then, the frog who reverses his direction, repeats the scaled by two $k$-end type path on the odd points, ending up at point number 1. Thus, we have successfully constructed a $(k+1)-$one type path. Further, here \[S_{k+1} =2S_k + 1 + 2S_k = 4S_k+1 = \frac{4^{k+1}-1}{3} \]so first half of the induction is complete. For the other, the frog scales up his sequence of moves on the $k$-one type path by two and stepping on the even numbered points, reaches $2$. He then jumps to point $1$, and repeats the scaled by two $k$-end type path on the odd points, ending up at point number $2^{k+1}-1$. Similar to before, we can easily check that $S_{k+1} = \frac{4^{k+1}-1}{3}$ and this is a successful $(k+1)-$end type path finishing the induction, and completing our construction. Now, we prove the bound. The basic idea is that, if the frog visits $a$ distinct points, he must visit $\lceil \frac{a}{2^{n-i}} \rceil$ different residue classes$\pmod{2^i}$ for all $0 \le i \le n-1$. But, if the frog does a jump of size $2^{i+1}$ or greater, his point number $\pmod{2^i}$ remains invariant. Thus, he must do atleast $\lceil \frac{a}{2^{n-i}} \rceil -1$ switches/changes to his point number $\pmod{2^i}$. The only way to do such a change is to execute a hop of size atmost $2^i$. Thus, for all $0 \le i <n$, the frog is forces to do atleast $\lceil \frac{a}{2^{n-i}} \rceil -1$ hops of size at most $2^i$. We now forget all about the problem and simply try to maximize the sum $S$ of $a$ terms each of the form $2^r$, which satisfies the condition that for all $0 \le i <n$ we have atleast $\lceil \frac{a}{2^{n-i-1}} \rceil -1$ terms of size at most $2^i$. This is in fact quite easy. It is easy to see that we would wish to maximize the number of larger terms. So we would wish to have the minimum possible number of terms of each size $2^i$ for $0 \le i < n-1$. In such a maximal $S$, then we would have exactly $\lceil \frac{a}{2^{n-1}} \rceil-1 \le \frac{a}{2^n}$ terms of size 1. For all other $i \le n-1$ we would have, \[\lceil \frac{a}{2^{n-i}} \rceil -1 - \left(\lceil \frac{a}{2^{n-i-1}} \rceil -1 \right ) \le \frac{a}{2^{n-i}} - \frac{a}{2^{n-i-1}} = \frac{a}{2^{n-i}} \]terms of size $2^i$. Thus, clearly, \[S \le 2^0 \cdot \frac{a}{2^{n}} + 2^1 \cdot \frac{a}{2^{n-1}} + 2^2 \cdot \frac{a}{2^{n-2}} + \dots + 2^{n-1} \cdot \frac{a}{2} =a \left( \frac{\frac{1}{2^{n}}(4^n-1)}{3}\right)\] Thus, our maximum hop-sum for a path which visits $a$ points is $a \left( \frac{\frac{1}{2^{n}}(4^n-1)}{3}\right)$. We further know that $a \le 2^n$ so, \[S \le \frac{4^n-1}{3} \]as we set out to show.

Here's a local solution in a thread full of global solutions (though this gives credence to this being a fakesolve ) We claim the answer is \[ S_n \coloneq 1 + 4 + \dots + 4^{n-1} = \frac{4^n - 1}{3}. \] Construction Take the construction of hopping from $0$ to $1$ as the base case. Then if \[ a_1, a_2, \dots, a_{2^n-1} \]are our hops for $n$, then we take \[ 2^n, a_1, -2^n, a_2, 2^n, a_3, 2^n, \dots, -2^n \]in a snake like pattern which adds an additional length of $2^n \cdot 2^n = 4^n$ (For instance, this turns $0 \to 1$ into $0 \to 2 \to 3 \to 1$). Bound We prove this inductively, with the bound immediate for $n = 1$. Generalize to the case of taking a forest of paths $\mathcal{F}$, and make the frog hop around a circle of ${\mathbb Z}/2^n{\mathbb Z}$. Call two numbers $a, b$ friends if $a-b = 2^{n-1}$. Claim: If $a, b$ are friends, then we can WLOG that the edge between $a$ and $b$ is in $\mathcal{F}$. Proof. Suppose there is no edge between $a$ and $b$. Do the following procedure. Delete a specific edge $e_a$ containing $a$ if it exists, and do the same for $b$ with $e_b$ This decreases $S$ by at most $2^{n-2} + 2^{n-2}$. Then adding the edge between $a$ and $b$ means that $S$ has not decreased, and this can be made to preserve acyclicity by specifically choosing $e_a$, $e_b$. $\blacksquare$ Apply this so that all $2^{n-1}$ pairs of friends are connected in $\mathcal{F}$. Remove these $2^{n-1}$ friend edges to get $\mathcal{F}'$. Then note that if we replace each edge $(a, b) \mapsto (a \pmod{2^{n-1}}, b \pmod{2^{n-1}})$ in $\mathcal{F}'$ and instead consider a circle $\mathbb{Z}/2^{n-1}\mathbb{Z}$, this satisfies the desired properties so inductively $|\mathcal{F}'| \le S_{n-1}$, so \[ |\mathcal{F}| \le 2^{n-1} \cdot 2^{n-1} + S_{n-1} = S_n \]as desired.