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: [list] 	[*]The frog visits only points in $\{1, 2, \dots, 2^n-1\}$, 	each at most once. 	[*]The length of each hop is in $\{2^0, 2^1, 2^2, \dots\}$. 	(The hops may be either direction, left or right.) [/list] Let $S$ be the sum of the (positive) lengths of all hops in the sequence. What is the maximum possible value of $S$?

[i]Ashwin Sah[/i]
1. **Construction of the Sequence:**
   - We need to show that the frog can achieve the sum \( S = \frac{4^n - 1}{3} \).
   - Consider the sequence of hops where in the \(i\)-th hop, the frog moves \(2^{n - \nu_2(i) - 1}\) units up or down, where \(\nu_2(i)\) is the largest power of 2 dividing \(i\). The direction of the hop is up if \(i \equiv 1 \pmod{4}\) or \(i \equiv 2 \pmod{4}\), and down otherwise.
   - This construction ensures that the frog makes a total of \(2^n - 1\) hops, and the sum of the lengths of these hops is:
     \[
     2^{n-1} \cdot 2^{n-1} + 2^{n-2} \cdot 2^{n-2} + \cdots + 2^0 \cdot 2^0 = \sum_{i=0}^{n-1} 2^i \cdot 2^i = \sum_{i=0}^{n-1} 4^i
     \]
   - The sum of a geometric series \(\sum_{i=0}^{n-1} 4^i\) is given by:
     \[
     \sum_{i=0}^{n-1} 4^i = \frac{4^n - 1}{4 - 1} = \frac{4^n - 1}{3}
     \]
   - Therefore, the sum of the lengths of all hops in this sequence is \(\frac{4^n - 1}{3}\).

2. **Proof of the Bound:**
   - We need to show that the sum \( S \) cannot exceed \(\frac{4^n - 1}{3}\).
   - Fix any nonnegative integer \( m \le n \). 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} \).
   - Therefore, the number of jumps with size at least \( 2^m \) is bounded above by:
     \[
     2^m \cdot (2^{n-m} - 1) = 2^n - 2^m
     \]

3. **Claim:**
   - For any sequence of nonnegative integers \( x_0, x_1, x_2, \ldots, x_{n-1} \) such that \( x_i + x_{i+1} + \cdots + x_{n-1} \le 2^n - 2^i \) for each \( 0 \le i \le n-1 \), we have:
     \[
     \sum_{i=0}^{n-1} 2^i x_i \le \frac{4^n - 1}{3}
     \]

4. **Proof of the Claim:**
   - Suppose this was not the case and consider a valid sequence \( (x_i) \) satisfying this with a maximal sum 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 = \sum_{i=0}^{n-1} 2^i \cdot 2^i = \sum_{i=0}^{n-1} 4^i = \frac{4^n - 1}{3}
       \]
     - This is a 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 \quad \text{as long as} \quad 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.

5. **Conclusion:**
   - 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}
     \]
   - This completes the proof.

\(\blacksquare\)

The final answer is \(\boxed{\frac{4^n - 1}{3}}\)