Problem: A mathematical frog jumps along the number line.
The frog starts at $1$, and jumps according to the following rule:
if the frog is at integer $n$,
then it can jump either to $n+1$ or to $n + 2^{m_n+1}$
where $2^{m_n}$ is the largest power of $2$ that is a factor of $n$.
Show that if $k \ge 2$ is a positive integer
and $i$ is a nonnegative integer,
then the minimum number of jumps needed to reach $2^ik$
is greater than the minimum number of jumps needed to reach $2^i$.

Solution: We will think about the problem in terms of
finite sequences of jumps $(s_1, s_2, \dots, s_\ell)$,
which we draw as
\[ 1 = x_0
  \taking{s_1} x_1
  \taking{s_2} x_2
  \taking{s_3} \dots
  \taking{s_\ell} x_\ell \]
where $s_k = x_k - x_{k-1}$ is the length of some hop.
We say the sequence is \emph{valid} if it has the
property required by the problem:
for each $k$, either $s_k = 1$ or $s_k = 2^{m_{x_{k-1}}+1}$.

An example is shown below.

\begin{lemma*}
  Let $(s_1, \dots, s_\ell)$ be a sequence of jumps.
  Suppose we delete pick an index $k$ and exponent $e > 0$,
  and delete any jumps after the $k$th one
  which are divisible by $2^e$.
  The resulting sequence is still valid.
\end{lemma*}
\begin{proof}
  We only have to look after the $k$th jump.
  The launching points of the remaining jumps after the $k$th
  one are now shifted by multiples of $2^e$
  due to the deletions;
  so given a jump $x \taking{s} x+s$
  we end up with a jump $x' \taking{s} x'+s$
  where $x-x'$ is a multiple of $2^e$.

  But since $s < 2^e$, we have $\nu_2(x') < e$
  and hence $\nu_2(x) = \nu_2(x')$ so the jump is valid.
\end{proof}

\begin{center}
\begin{asy}
unitsize(0.6cm);
defaultpen(fontsize(8pt));
for (int i=1; i<=24; ++i) {
  if (i!=8) label("$"+(string)i+"$", (i,0));
}
label("$\boxed{8}$", (8,0));

void arr(int i, int j, pen p, real eps) {
  pair M = ((i+j)/2, eps*(j-i)**0.5/2);
  draw((i,0)..M..(j,0), p, EndArrow(TeXHead), Margin(2,2));
  label("$"+(string)(j-i)+"$", M, eps*dir(90), p);
}

arr( 1,  3, red, 1);
arr( 3,  4, red, -1);
arr( 4, 12, blue+dashed, 1);
arr(12, 13, red, -1);
arr(13, 14, red, 1);
arr(14, 18, blue+dashed, -1);
arr(18, 19, red, 1);
arr(19, 21, blue+dashed, -1);
arr(21, 23, blue+dashed, 1);
arr(23, 24, red, -1);

add(shift(-8, 3)*CC());

for (int i=1; i<=8; ++i) {
  if (i!=8) label("$"+(string)i+"$", (i,0));
}
label("$\boxed{8}$", (8,0));

arr( 1,  3, red, 1);
arr( 3,  4, red, -1);
arr( 4,  5, red, -1);
arr( 5,  6, red, 1);
arr( 6,  7, red, 1);
arr( 7,  8, red, -1);
\end{asy}
\end{center}


Now let's consider a valid path to $2^i k$ with $\ell$ steps, say
\[ 1 = x_0
  \taking{s_1} x_1
  \taking{s_2} x_2
  \taking{s_3} \dots
  \taking{s_\ell} x_\ell = 2^i \cdot k \]
where $s_i = x_i - x_{i-1}$ is the distance jumped.

We delete jumps in the following way:
starting from the largest $e$ and going downwards until $e=0$,
we delete all the jumps of length $2^e$
which end at a point exceeding the target $2^i$.

By the lemma, at each stage, the path remains valid.
We claim more:
\begin{claim*}
  Let $e \ge 0$.
  After the jumps of length greater than $2^e$ are deleted,
  the resulting end-point is at least $2^i$,
  and divisible by $2^{\min(i,e)}$.
\end{claim*}
\begin{proof}
  By downwards induction.
  Consider any step where \emph{some} jump is deleted.
  Then, the end-point must be strictly greater than $x = 2^i - 2^e$
  (i.e.\ we must be within $2^e$ of the target $2^i$).

  It is also divisible by $2^{\min(i,e)}$ by induction hypothesis,
  since we are changing the end-point by multiples of $2^e$.
  And the smallest multiple of $2^{\min(i,e)}$ exceeding $x$ is $2^i$.
\end{proof}
On the other hand by construction when the process ends
the reduced path ends at a point at most $2^i$,
so it is $2^i$ as desired.

Therefore we have taken a path to $2^i k$
and reduced it to one to $2^i$ by deleting some jumps.
This proves the result.