USAMO

For $i \ge 0$ and $k \ge 1$, let $x_{i,k}$ denote the minimum number of jumps needed to reach the integer $n_{i,k} = 2^i k$. We must prove that
$$x_{i,k} > x_{i,1} \qquad (*)$$
for all $i \ge 0$ and $k \ge 2$. We prove this using the method of descent.

First note that $(*)$ holds for $i = 0$ and all $k \ge 2$, because it takes $0$ jumps to reach the starting value $n_{0,1} = 1$, and at least one jump to reach $n_{0,k} = k \ge 2$. Now assume that $(*)$ is not true for all choices of $i$ and $k$. Let $i_0$ be the minimal value of $i$ for which $(*)$ fails for some $k$, let $k_0$ be the minimal value of $k > 1$ for which $x_{i_0,k} \le x_{i_0,1}$. Then it must be the case that $i_0 \ge 1$ and $k_0 \ge 2$.

Let $J_{i_0,k_0}$ be a shortest sequence of $x_{i_0,k_0} + 1$ integers that the frog occupies in jumping from $1$ to $2^{i_0} k_0$. The length of each jump, that is, the difference between consecutive integers in $J_{i_0,k_0}$, is either $1$ or a positive integer power of $2$. The sequence $J_{i_0,k_0}$ cannot contain $2^{i_0}$ because it takes more jumps to reach $2^{i_0} k_0$ than it does to reach $2^{i_0}$. Let $2^{M+1}$, $M \ge 0$ be the length of the longest jump made in generating $J_{i_0,k_0}$. Such a jump can only be made from a number that is divisible by $2^M$ (and by no higher power of $2$). Thus we must have $M < i_0$, since otherwise a number divisible by $2^{i_0}$ is visited before $2^{i_0} k_0$ is reached, contradicting the definition of $k_0$.

Let $2^{m+1}$ be the length of the jump when the frog jumps over $2^{i_0}$. If this jump starts at $2^m(2t - 1)$ for some positive integer $t$, then it will end at $2^m(2t - 1) + 2^{m+1} = 2^m(2t + 1)$. Since it goes over $2^{i_0}$ we see $2^m(2t - 1) < 2^{i_0} < 2^m(2t + 1)$ or $(2^{i_0-m} - 1)/2 < t < (2^{i_0-m} + 1)/2$. Thus $t = 2^{i_0-m-1}$ and the jump over $2^{i_0}$ is from $2^m(2^{i_0-m} - 1) = 2^{i_0} - 2^m$ to $2^m(2^{i_0-m} + 1) = 2^{i_0} + 2^m$.

Considering the jumps that generate $J_{i_0,k_0}$, let $N_1$ be the number of jumps from $1$ to $2^{i_0} + 2^m$, and let $N_2$ be the number of jumps from $2^{i_0} + 2^m$ to $2^{i_0} k_0$. By definition of $i_0$, it follows that $2^m$ can be reached from $1$ in less than $N_1$ jumps. On the other hand, because $m < i_0$, the number $2^{i_0}(k_0 - 1)$ can be reached from $2^m$ in exactly $N_2$ jumps by using the same jump length sequence as in jumping from $2^m + 2^{i_0}$ to $2^{i_0} k_0 = 2^{i_0}(k_0 - 1) + 2^i$. The key point here is that the shift by $2^{i_0}$ does not affect any of divisibility conditions needed to make jumps of the same length. In particular, with the exception of the last entry, $2^{i_0} k_0$, all of the elements of $J_{i_0,k_0}$ are of the form $2^p(2t + 1)$ with $p < i_0$, again because of the definition of $k_0$. Because $2^p(2t + 1) - 2^{i_0} = 2^p(2t - 2^{i_0-p} + 1)$ and the number $2t + 2^{i_0-p} + 1$ is odd, a jump of size $2^{p+1}$ can be made from $2^p(2t + 1) - 2^{i_0}$ just as it can be made from $2^p(2t + 1)$.

Thus the frog can reach $2^m$ from $1$ in less than $N_1$ jumps, and can then reach $2^{i_0}(k_0 - 1)$ from $2^m$ in $N_2$ jumps. Hence the frog can reach $2^{i_0}(k_0 - 1)$ from $1$ in less than $N_1 + N_2$ jumps, that is, in fewer jumps than needed to get to $2^{i_0} k_0$ and hence in fewer jumps than required to get to $2^{i_0}$. This contradicts the definition of $k_0$.

Suppose $x_0 = 1, x_1, \dots, x_t = 2^i k$ are the integers visited by the frog on his trip from $1$ to $2^i k$, $k \ge 2$. Let $s_j = x_j - x_{j-1}$ be the jump sizes. Define a reduced path $y_j$ inductively by
$$y_j = \begin{cases} y_{j-1} + s_j & \text{if } y_{j-1} + s_j \le 2^i, \\ y_{j-1} & \text{otherwise.} \end{cases}$$
Say a jump $s_j$ is deleted in the second case. We will show that the distinct integers among the $y_j$ give a shorter path from $1$ to $2^i$. Clearly $y_j \le 2^i$ for all $j$. Suppose $2^i - 2^{r+1} < y_j \le 2^i - 2^r$ for some $0 \le r \le i - 1$. Then every deleted jump before $y_j$ must have length greater than $2^r$, hence must be a multiple of $2^{r+1}$. Thus $y_j \equiv x_j \pmod{2^{r+1}}$. If $y_{j+1} > y_j$, then either $s_{j+1} = 1$ (in which case this is a valid jump) or $s_{j+1}/2 = 2^m$ is the exact power of $2$ dividing $x_j$. In the second case, since $2^r \ge s_{j+1} > 2^m$, the congruence says $2^m$ is also the exact power of $2$ dividing $y_j$, thus again this is a valid jump. Thus the distinct $y_j$ form a valid path for the frog. If $j = t$ the congruence gives $y_t \equiv x_t \equiv 0 \pmod{2^{r+1}}$, but this is impossible for $2^i - 2^{r+1} < y_t \le 2^i - 2^r$. Hence we see $y_t = 2^i$, that is, the reduced path ends at $2^i$. Finally since the reduced path ends at $2^i < 2^i k$ at least one jump must have been deleted and it is strictly shorter than the original path.

(By Brian Lawrence) Suppose $2^i k$ can be reached in $m$ jumps.

Our approach will be to consider the frog's life as a sequence of leaps of certain lengths. We will prove that by removing the longest leaps from the sequence, we generate a valid sequence of leaps that ends at $2^i$. Clearly this sequence will be shorter, since it was obtained by removing leaps. The result will follow.

Lemma If we remove the longest leap in the frog's life (or one of the longest, in case of a tie) the sequence of leaps will still be legitimate.

Proof: By definition, a leap from $n$ to $n + \nu$ is legitimate if and only if either (a) $\nu = 1$, or (b) $\nu = 2^{m_n+1}$. If all leaps are of length $1$, then clearly removing one leap does not make any others illegitimate; suppose the longest leap has length $2^s$.

Then we remove this leap and consider the effect on all the other leaps. Take an arbitrary leap starting (originally) at $n$, with length $\nu$. Then $\nu \le 2^s$. If $\nu = 1$ the new leap is legitimate no matter where it starts. Say $\nu > 1$. Then $\nu = 2^{m_n+1}$. Now if the leap is before the removed leap, its position is not changed, so $\nu = 2^{m_n+1}$ and it remains legitimate. If it is after the removed leap, its starting point is moved back to $n - 2^s$. Now since $2^{m_n+1} = \nu \le 2^s$, we have $m_n \le s - 1$; that is, $2^s$ does not divide $n$. Therefore, $2^{m_n}$ is the highest power of $2$ dividing $n - 2^s$, so $\nu = 2^{m_n-2^s+1}$ and the leap is still legitimate. This proves the Lemma. ■

We now remove leaps from the frog's sequence of leaps in decreasing order of length. The frog's path has initial length $2^i k - 1$; we claim that at some point its length is $2^i - 1$.

Let the frog's $m$ leaps have lengths
$$a_1 \ge a_2 \ge a_3 \ge \dots \ge a_m.$$
Define a function $f$ by
$$f(0) = 2^i k \\ f(i) = f(i-1) - a_i, \quad 1 \le i \le m.$$
Clearly $f(i)$ is the frog's final position if we remove the $i$ longest leaps. Note that $f(m) = 1$ – if we remove all leaps, the frog ends up at $1$. Let $f(j)$ be the last value of $f$ that is at least $2^i$. That is, suppose $f(j) \ge 2^i$, $f(j+1) < 2^i$. Now we have $a_{j+1}|a_k$ for all $k \le j$ since $\{a_k\}$ is a decreasing sequence of powers of $2$. If $a_{j+1} > 2^i$, we have $2^i|a_p$ for $p \le j$, so $2^i|f(j+1)$. But $0 < f(j+1) < 2^i$, contradiction. Thus $a_{j+1} \le 2^i$, so, since $a_{j+1}$ is a power of two, $a_{j+1}|2^i$. Since $a_{j+1}|2^i k$ and $a_1, \dots, a_j$, we know that $a_{j+1}|f(j)$, and $a_{j+1}|f(j+1)$. So $f(j+1)$, $f(j)$ are two consecutive multiples of $a_{j+1}$, and $2^i$ (another such multiple) satisfies $f(j+1) < 2^i \le f(j)$. Thus we have $2^i = f(j)$, so by removing $j$ leaps we make a path for the frog that is legitimate by the Lemma, and ends on $2^i$.

Now let $m$ be the minimum number of leaps needed to reach $2^i k$. Applying the Lemma and the argument above the frog can reach $2^i$ in only $m-j$ leaps. Since $j > 0$ trivially ($j = 0$ implies $2^i = f(j) = f(0) = 2^i k$) we have $m-j < m$ as desired.