Induction destroys it

assume that $i_{0}$ is the minimum number such that $f(2^{i_{0}}k)\leqq(2^{i_{0}})$(*) for some k,where f(t) is the minimum jump that the frog need to reach t.Call $k_{0}$ the smallest such number.Consider the path that the frog jump from $1$ to $2^{i_{0}}k_{0}$.The length of each jump is a power of $2$.Because of (*) the path does not contain $2^{i_{0}}$;therefore assume that the frog jump from a when it pass through $2^{i_{0}}$;assume $a=2^{t}(2m-1)$ then the frog will find himself at $2^{t}(2m+1)$->$2^{t}(2k-1)\leq\ 2^{i_{0}}\leq\ 2^{t}(2t+1)\to t=2^{i_{0}-m-1}$->$a=2^{i_{0)}}-2^{m}$ By the minimal of $i_{0}$ and $k_{0}$ we see that we can go from $1$ to $2^{m}$ by less jump than from $1$ to $2^{m}+2^{i_{0}}$;and we can find a bijection from the path from $2^{m}+2{i_{0}}$ to $2^{i_{0}}k_{0}$ to the path from $2^{m}$ to $2^{i_{0}}(k_{0}-1)$.Then we can go from $1$ to $2^{i_{0}}$ by less than $f(2^{i_{0}}k_{0})$ jump.Contradiction

OK. Base step is obvious for i=0 this thing is obvious. Now assume that the result holds for all i from 0 to k inclusive. Let's prove it'll hold for i = k + 1. look at the 2 paths of the frog to 2^(k+1) and p * 2^(k+1). In the 2nd path, let the largest number the frog jumps to be x, so x < 2 ^(k+1). then x + 2^(m index x + 1) > = 2 ^ (k+1). Then the number of steps needed to get to 2 ^ (k+1) from x is < (a idex (2 ^ m index x + 1) + 1), a index n is the min number of steps needed to get from 1 to n. The min number of steps needed to get from (x + 2^(m index x + 1)) to 2 ^ (k+1) * p is greater than or equal to (a idex (2 ^ m index x + 1) + 1), and the result follows.

Let N(n) is minimal needed jumps to get n, s(n) -sum of 2-adic digits of n. Then (it is easy to show) $N(n)=[log_2 n]+s(n)-1$.

Rust wrote: Then (it is easy to show)$N(n)=[log_2 n]+s(n)-1$. Please explain

Turn round process from n to 1 is $n_0=n$ if $2|n_i, n_{i+1}=\frac n2$ else $n_{i+1}=n_i-1$. Number of steps is N(n).

Rust wrote: Let N(n) is minimal needed jumps to get n, s(n) -sum of 2-adic digits of n. Then (it is easy to show) $N(n)=[log_2 n]+s(n)-1$. The formula is not correct. For example, for 2^n the formula claims that N(2^n) = n, which is not correct. For example, N(8)=4.

shunka wrote: Rust wrote: Let N(n) is minimal needed jumps to get n, s(n) -sum of 2-adic digits of n. Then (it is easy to show) $N(n)=[log_2 n]+s(n)-1$. The formula is not correct. For example, for 2^n the formula claims that N(2^n) = n, which is not correct. For example, N(8)=4. N(8)=3 ($8=2^3$). However I solve for jump n+h, $h=1,2,...,2^{m_n}$. In my case N(3)=2. For this case ($h\le 2^{m_n+1}$) had not effictive formul for N(n).

Rust wrote: N(8)=3 ($8=2^3$). However I solve for jump n+h, $h=1,2,...,2^{m_n}$. In my case N(3)=2. For this case ($h\le 2^{m_n+1}$) had not effictive formul for N(n). Now I understand even less. By definition, N(n) is the minimal number of steps needed to reach n. For n=8, the minimal number of steps is 4. One can go 1 -> 2 -> 6 -> 7 -> 8 or 1 -> 3 ->5 ->7 -> 8. In both cases 4 steps are used, and there is no shorter sequence of steps reaching 8. Thus, I think, N(8)=4. The proposed formula gives N(8) = [log_2(8)] + s(8) -1 = 3 + 1 -1 = 3. Thus the formula gives N(8)=3, which means that something is wrong. The reply now claims that N(3)=2. I think that N(3)=1, since 1-> 3 produces 3 in one step. What does the phrase "I solve for jump n+h" mean?

shunka wrote: Rust wrote: N(8)=3 ($8=2^3$). However I solve for jump n+h, $h=1,2,...,2^{m_n}$. In my case N(3)=2. For this case ($h\le 2^{m_n+1}$) had not effictive formul for N(n). Now I understand even less. By definition, N(n) is the minimal number of steps needed to reach n. For n=8, the minimal number of steps is 4. One can go 1 -> 2 -> 6 -> 7 -> 8 or 1 -> 3 ->5 ->7 -> 8. In both cases 4 steps are used, and there is no shorter sequence of steps reaching 8. Thus, I think, N(8)=4. The proposed formula gives N(8) = [log_2(8)] + s(8) -1 = 3 + 1 -1 = 3. Thus the formula gives N(8)=3, which means that something is wrong. The reply now claims that N(3)=2. I think that N(3)=1, since 1-> 3 produces 3 in one step. What does the phrase "I solve for jump n+h" mean? I think he means he misread the problem. He may have read $2^{m_n}$ instead of $2^{m_n+1}$?

paladin8 wrote: I think he means he misread the problem. He may have read $2^{m_n}$ instead of $2^{m_n+1}$? Yes, this explanation makes sense. Thanks. In fact, now I think that he understood that he could jump by any power of 2 smaller or equal to 2^{m_n}. That would explain the phrase "I solve for jump n+h, for h =1,2,...".

My solution was to prove that the maximum that the frog can move in $i-1$ moves was to $2^i-1$ by induction, and it looked really "elegant". Something was obviously wrong though , due to the dismal score I got.

But when i = 3, i-1 = 2. In two steps one cannot reach 7 = 2^3-1. Thus in general, one cannot even reach 2^i-1 in i-1 steps. It seems that this does not help to find out if we can reach 2^i before we can reach k2^i. All we know that in i-1 steps we are far from both.

hey, 'rem' i dont quite understand your solution. could you perhaps clarify it using better notation? what do these 'indexes' mean? its trivial to reduce it to proving 2^(n+1) takes more jumps than 2^n from which the result follows, since to reach (2k+1) * 2 ^ t you need to jump from (2k-1) * 2^t; so it reduces to the aforementioned problem. another interesting thing i noticed is when you try to work backwards, like from 2^(n+1) go to the next step to all possible values from which 2^(n+1) can be reached, and to continue the process, you get a string of numbers of the form {2^(n+1) - t}. Evidently the numbers {t} are the same numbers generated when you work forwards .. though using this observation doesn't help since it reduces the problem to the problem itself. so as far as im concerned the problem hasn't been solved yet on mathlinks.

epitomy01 wrote: ... since to reach (2k+1) * 2 ^ t you need to jump from (2k-1) * 2^t hmmm....? If I did everything right, I think the sequence of steps 1 -> 3 -> 4 -> 12 -> 20 -> 28 -> 29 -> 30 is the unique sequence of 7 jumps that reaches 30 and there is no shorter sequence of steps that reaches 30. This tells me two things 1) You do not have to come to (2j+1)2^i from (2j-1)2^i (we come to 30 from 29) 2) You do not have to step on 2^i on your path to (2j+1)2^i (we do not step on 2 on the way to 30)

My solution consists of proving first $S(2^n) < S(2^{n+1}) \le 2S(2^n)$...from there proceed by contradiction. I believe I might have used induction too.

I just read the official solution http://www.unl.edu/amc/e-exams/e8-usamo/e8-1-usamoarchive/2006-ua/2006usamoS.pdf and I think it's really strange. Why do they prove $M<i_{0}$ in the third paragraph, since it isn't used later anywhere... can anyone clarify?

It seems that in the 4th paragraph of the official solution one uses (at least implicitly) that m<i_0. The fact that m<i_0 follows from the fact that m is at most M and that M<i_0 (the latter is proved in the third paragraph).

Here's a kind of long-winded solution. I'm not entirely sure it works, but I believe it does. Lack of diagrams probably makes this extremely hard to follow... Define an inverse frog as follows: an inverse frog can jump from $ a$ to $ b$ if and only if a frog can jump from $ b$ to $ a$ (with $ b<a$, of course). So this happens if and only if $ a-b=1$ or $ b=a-2^{m_{b}+1}$. Since $ 2^{m_{b}}||b$, let $ b=2^{m_{b}}B$ where $ B$ is odd. Then we get that $ a=2^{m_{b}}(B+2)$, so $ m_{a}=m_{b}$. However, note that if $ a$ is a power of 2, we get $ B=-1$, and since only care about the positive number line (once we get to a negative number, we can never get back to 1), an inverse frog on a power of 2 can only jump to $ a-1$. Now, we see that an inverse frog on the integer $ a$ jumps according to one of: (i) $ a-1$; (ii) $ a-2^{m_{a}+1}$, given that $ a$ is not a power of 2. Let $ f(n)$ be the minimum number of jumps required for a frog to jump from $ 1$ to $ n$, or equivalently the minimum number of jumps required for an inverse frog to jump from $ n$ to $ 1$. We need to show that $ f(2^{i})<f(k\cdot2^{i})$ for $ k\ge2$. First, we induct strongly on $ i$ to show that it is true for $ k=2$ and all odd $ k\ge3$. Then, we show that it is true for all even $ k\ge4$. First, for the $ k=2$ case. We are showing that $ f(2^{i})<f(2^{i+1})$. Consider two inverse frogs, $ A$, and $ B$, with $ A$ starting on $ 2^{i+1}$ and $ B$ on $ 2^{i}$. Let $ a_{j}$ and $ b_{j}$ be their respective positions after $ j$ jumps. Note that $ a_{1}=2^{i+1}-1$ and $ b_{1}=2^{i}-1$. We construct a tree diagram for the possible values of $ a_{j}$, given the two choices the inverse frog has at each point. This gives us a binary tree, starting from $ j=1$, for each $ A$ and $ B$. Now, if we come to a point in either binary tree where the inverse frog only has one choice (basically, it gets to a power of 2 bigger than 1), on one branch write number-1, and on the other branch we have a blank. Then we can continue our tree off of our blanks, with more blanks. Note that any sequence of $ a_{j}$'s is strictly decreasing, and made up of integers, so in $ B$'s tree we eventually get to a 1 (and we know we won't end up with just a bunch of blanks because we can always just keep subtracting 1). Note that $ f(2^{i})$ is the minimal $ z$ such that there is a path with $ b_{z}=1$. We claim that if we match up the trees from $ j=0$ to $ j=z$, corresponding entries in the binary trees either contain a blank or differ by $ 2^{i}$. We do this by induction on $ j$. It's true for $ j=0$ and $ j=1$. Basically, if we have two non-blanks in corresponding positions on the two different trees, assume these differ by $ 2^{i}$. Thus, they are congruent modulo $ 2^{i}$, so unless $ 2^{i}$ divides both of them, the biggest power of 2 dividing them is the same. But obviously it's not possible for $ 2^{i}$ to divide anything in the $ 2^{i}$ tree because $ b_{1}=2^{i}-1$. Thus, the length of the inverse frog's two possible jumps is the same for both non-blank entries. Now, we claim that there can't be we can't have $ a_{j}=1$ with $ j\le z=f(2^{i})$. Assume we do. Then, the corresponding position in $ B$'s tree must be blank, as it cannot be $ 1-2^{i}\le0$. We can trace this blank back to some power of 2, $ 2^{a}$, with $ a<i$, in $ B$'s tree. The analog on $ A$'s tree is not blank, since we can trace $ a_{j}=1$ back to it, so it is $ 2^{a}+2^{i}=2^{a}(1+2^{i-a})$, which is an odd multiple of $ 2^{a}$. But by the original inductive hypothesis, we take $ k=1+2^{i-a}$, which is again odd, because $ i>a$, and $ f(2^{a})<f^(2^{a}(1+2^{1-a}))$. Thus, we must have had a 1 in $ B$'s tree earlier than the 1 in $ A$'s tree, contradiction, since we took $ z$ to be the earliest 1 in $ B$'s tree. This proves the $ k=2$ case. Now consider $ k\ge3$ odd. Let $ k=2k'+1$ where $ k'$ is a natural number; we induct on $ k'$. First, $ k'=1$, so we're proving that $ f(3\cdot2^{i})>f(2^{i})$. From $ 3\cdot2^{i}$, an inverse frog can jump to either $ 3\cdot2^{i}-1$ or $ 2^{i}$. However, if it jumps to $ 2^{i}$, it needs at least $ 1+f(2^{i})$ jumps to get to 1. So we only consider the former case. Also, note that the $ 2^{i}$ inverse frog has to jump to $ 2^{i}-1$. We now use exactly the same argument from the $ k=2$ case. For the inductive step, note that from $ (2k'+1)\cdot2^{i}$ we can go to $ (2k'+1)\cdot2^{i}-1$ or $ (2(k'-1)+1)\cdot2^{i}$. For the former, apply the same argument as the $ k=2$ case again, and for the latter, by induction hypothesis, we need $ 1+f((2(k'-1)+1)\cdot2^{i})>1+f(2^{i})$ steps to reach 1. This proves the $ k$ odd case. It is left to prove the claim for all even $ k\ge4$. Let $ k=2^{m_{k}}\cdot K$, so $ K$ is odd. We wish to show that $ f(2^{i})<f(2^{m_{k}} \cdot K\cdot2^{i})$. But note that $ f(2^{m_{k}}\cdot K\cdot2^{i})=f(K\cdot2^{m_{k}+i})>f(K\cdot 2^{m_{k}+i-1})>\cdots>f(K\cdot 2^{i})\ge f(2^{i})$, where we repeatedly use the $ k=2$ case, then finally the odd $ k$ case, since $ K$ is odd. This, finally, completes the proof.

My intuition is completely terrible, so here's an unfortunate solution that can probably be cleaned up significantly (it's probably basically equivalent to everyone else's solutions anyway). Let $f(n)$ denote the least number of moves needed to get to $n$. Then the moving condition states that if $n=2^rs>1$ where $s$ is odd ($f(1)=0$), then \[f(n)=f(2^rs)=1+\min(f(2^rs-1),f(2^rs-2^{r+1})),\]where if $s=1$ we simply ignore the second term and have $f(2^r)=1+f(2^r-1)$. (We will repeatedly use these two fundamental relations, of course.) We prove by strong induction on $i,j,k$ in that order that for all integers $i\ge0$, $j\ge1$, and $1\le k\le2^{i+1}-1$, $f(2^{i+1}j+k)>f(k)$. (1) For $i=0$, this is trivial for all $j,k$ since $f(1)=0$, establishing our base case. Now assume that $i\ge1$. For $1\le k\le2^i-1$, the claim is clearly true for all $j$ since by (1), $f(2^{i+1}j+k)=f(2^i(2j)+k)>f(k)$. (2) Now consider $k=2^i$ and $j\ge1$. For $j=1$, using (2) and the fact that $f(2^i)=1+f(2^i-1)$, \begin{align*} f(2^{i+1}+2^i) &=1+\min(f(2^{i+1}+2^i-1),f(2^{i+1}+2^i-2^{i+1}))\\ &=1+\min(f(2^{i+1}+2^i-1),f(2^i))\\ &\ge1+\min(1+f(2^i-1),f(2^i))\\ &=1+f(2^i)>f(2^i). \end{align*}For $j\ge2$, then, \begin{align*} f(2^{i+1}j+2^i) &=1+\min(f(2^{i+1}j+2^i-1),f(2^{i+1}j+2^i-2^{i+1}))\\ &=1+\min(f(2^{i+1}j+2^i-1),f(2^{i+1}(j-1)+2^i))\\ &\ge2+\min(f(2^i-1),f(2^i))\\ &=2+f(2^i-1)>f(2^i). \end{align*}So we've proven (1) for $k=2^i$ and $j\ge1$. (3) Now we look at $2^i+1\le k\le 2^{i+1}-1$, inducting strongly on $k$. For the base case $k=2^i+1$, we have by (2) and (3) that (let $2^e$ be the largest power of two dividing $k$, so that $e\le i-1$ and thus $k>2^i\ge2^{e+1}$) \begin{align*} f(2^{i+1}j+k) &=1+\min(f(2^{i+1}j+k-1),f(2^{i+1}j+k-2^{e+1}))\\ &\ge2+\min(f(k-1),f(k-2^{e+1}))\\ &=1+f(k)>f(k). \end{align*}The exact same argument applies when $k\ge2^i+2$. This completes the induction.$\blacksquare$ With (1), we now find \begin{align*} f(2^{r+1})=1+f(2^{r+1}-1)=1+f(2^r+2^r-1) & \ge2+f(2^r-1)\\ &=1+f(2^r)>f(2^r) \end{align*}and for odd $2t+1\ge3$, \[f(2^r(2t+1))=f(2^{r+1}t+2^r)>f(2^r).\]These two inequalities trivially imply the problem statement. Edit: copied from a PM to KingSmasher3, since it has some stuff that might help others.

Let $a_0, a_1, a_2, ... , a_x$ be the minimal sequence of jumps for the frog to reach $2^ik$ with $a_0=1$ and $a_x=2^ik.$ Let $a_y$ be the smallest term greater than $2^ik-2^i.$ We define the sequence $b_0, b_1, b_2, ... , b_{x-y}$ such that $b_j=a_{j+y}-2^ik+2^i$ for $0 \le j \le x-y.$ Since $v_2(2^ik-r)=v_2(2^k-r)$ for all $r<2^k,$ $b$ is still a valid sequence. Now we have three cases: (1) If $b_0=1,$ then we are done, since we have a sequence, namely $b,$ that gets to $2^k$ in a shorter number of steps. (2) If $b_0>1$ is not a power of $2,$ this contradicts the fact that $a_y$ is minimal: Let $b_0=c2^d$ where $c\ge 3$ is odd and $d \ge 0.$ Then, $a_y=c2^d+2^ik-2^i$ has $2^d$ as its largest power-of-2 factor. This means that $a_{y-1}$ is either $a_y-1$ or $a_y-2^{d+1},$ both of which are greater than $2^ik-2^i.$ (3) If $b_0>1$ is a power of $2,$ it suffices to show that it takes less moves to get to $b_0$ than $a_y.$ Note that this is because $a_0, a_1, a_2, ... , a_y$ is also the shortest path to $a_y.$ We apply strong induction. Clearly, if $i=0,$ then it takes less steps to get to $2^i$ than $2^ik.$ Since $a_y=b_0k',$ we are done by the inductive hypothesis. Edit: Revised solution. Thanks to math154 for help!

@ KingSmasher3: No, because you cannot assume that the minimal paths for both $2^{i}*k$ and $2^{i}$ have the same beginning sequence from $a_{0}$ to $a_{j}$. Edit: Sorry, I misinterpreted that as comparing the minimal paths, instead of building a path.

zero.destroyer wrote: @ KingSmasher3: No, because you cannot assume that the minimal paths for both $2^{i}*k$ and $2^{i}$ have the same beginning sequence from $a_{0}$ to $a_{j}$. zero.destroyer- Thanks for reply. However, this concept shouldn't be a problem right? It does not matter if the minimal maths for both $2^ik$ and $2^i$ both start with $a_0, ... , a_j$ (since they probably don't). We just have to show that there exists a path to $2^i$ that is shorter than $a,$ the minimal path to $2^ik.$ It does not have to be the minimal path to $2^i.$

Here's a pretty short solution: Define $m_{\ell}$ to be the minimum number of steps required to jump from $1$ to $2^\ell$. We pretty much now induct on this statement: If $v_2(a) = p$, the it takes at least $1+m_{p}$ steps for $a$ to jump to a multiple of $2^{p+1}$. So now take the minimal sequence to $k \cdot 2^i$. If this sequence passes through $2^i$, we're of course done. Otherwise it skips over $2^i$. This can only happen if the jump was $2^i-2^j \rightarrow 2^i+2^j$ for some $j$. But by the above statement, since jumping $2^i-2^j$ to $2^i$ takes $1+m_j$ moves (this is clearly achievable) while jumping $2^i+2^j$ to $k \cdot 2^i$ takes at least $1+m_j$ moves, we are done.

We will prove the result with strong induction on $i$. For the base case of $i=0$, it takes the frog 0 hops to jump to 1 and a positive number of hops to jump to any integer greater than 1, so the conclusion follows. For the inductive step, suppose that the result holds for all $i<m$. We will consider what the frog does in reverse, as in its hops from $n$ to 1. Clearly, the hops backwards are $n\rightarrow n-1$ or $n\rightarrow n-2^{m_n+1}$, with the extra constraint that we have to stay positive. Suppose for the sake of contradiction that the frog needs more hops to get from $2^i$ to 1 than $2^ik$ to 1 and furthermore suppose that the frog does not do $2^ik\rightarrow 2^ik-2^{m_{2^ik}+1}$ as its first move. Then, it must go $2^ik\rightarrow 2^ik-1$. Now, from here, have the $2^i$ to 1 frog copy all the moves of the $2^ik$ to 1 frog unless it makes a move that makes it go nonpositive. At this point, the $2^ik$ frog must be at a point of the form $2^i(k-1)+2^a$ for some nonnegative integer $a$. But now, the $2^i$ to 1 frog can just repeat the moves from $2^a$ to 1 and by strong induction it takes less moves than going from $2^i(k-1)+2^a$, a contradiction. If the $2^ik$ to 1 frog makes the second kind of move on its first move, then it must move to some number of the form $2^ik'<2^ik$, and we can finish this case with an induction.

Sketch: Consider the following restatement of the problem: Show that the minimum number of moves to transform the binary number $0...001$ into the number $2^i=1000000..0$ , is less than the amount of moves to transform the original sequence into the number $k2^i=blah0000000..0$, if we are allowed the following moves: a) Add one to the digit one to the left of the rightmost 1, and perform a carry if neccessary b) Add a one to the ones place, and perform a carry if neccessary Now we have that in order to reach the $1000...00000$, the second to last move will be from the number $1111...111$. Similarly, in order to get $k2^i=blah0000..000$, we need to pass through some number of the form $something1111...111$. Now take the strategy that gives the minimum number of moves for $k2^i$, and apply it to get $2^i$, ignoring every move that affects a digit larger than $2^i$. Clearly, this will transform $1$ into $2^i$, and additionally it must take less moves, or else would have that the algorithm to generate $k2^i$ would only involve moves regarding digits less than $2^i$, and thus would force $k=1$, so we are done.

@above, but you forgot the case when the move affects both the digits larger than $2^i$ and the digits lower than $2^i$ that are made through carries. Sketch: Consider a path from $1$ to $k*2^i$, suppose this is the smallest path from $1$ to a number of the form $k*2^i$. Thus, when we take this path mod $2^i$ there must be no repeats. We want to prove that this path is from $1$ to $2^i$. If there are 2 adjacent terms in this path a and b s.t. there is a multiple of $2^i$ in between them, it is easy to see that $a==-2^x$ and $b==2^x$ for some x>1.(Modulo $2^i$ of course) Since x<i we can prove that the smallest path from b to 0 is greater that or equal to the smallest path from a to 0.

The write-up is tricky, so the following might be a nonsense. We slightly alter the problem by letting the frog jumps from $n$ to $n-1$ or $n-2^{\nu_2(n)+1}$ instead, and the goal is to go from $n$ to $1$. This is equivalent to the problem by reversing the sequence of jumps. We also use induction on $i$; the base case $i=0$ and $i=1$ are easy to check. Assume that $a_1, a_2, \hdots, a_m$ is a sequence of jumps from $2^i\cdot k$ to $1$, and let $b_j=a_j-2^i(k-1)$. We analyze the behavior of $b_j$. Case 1: $a_{j+1}=a_j-1$ If $b_j=1$, then we do nothing. If $b_j>1$, then clearly $b_{j+1}=b_j-1$ so the jump from $b_j\to b_{j+1}$ is valid. Case 2: $a_{j+1}=a_j - 2^{\nu_2(a_j)+1}$ If $\nu_2(a_j)\geq i-1$, then $2^{i-1}\mid b_j$. Thus, either $b_j\leq 0$ or $b_j$ is a power of two. Otherwise, $\nu_2(a_j) < i-1$, thus $\nu_2(b_j) = \nu_2(a_j)$. Now we split into two more subcases. If $b_j > 2^{\nu_2(b_j)+1}$, then $b_{j+1} = b_j-2^{\nu_2(b_j)+1}$. The jump from $b_j\to b_{j+1}$ is valid. Otherwise, we must have that $b_j$ is a power of two. In this case, we use the induction hypothesis instead. Summing up the above case split, we get that the sequence $b_1,b_2,\hdots$ is a valid jump until the sequence hit upon a power of two; we must hit since the last term is clearly negative. Let $b_s=2^t$ for some integers $s,t$ which $s$ is minimal. If $t=0$, then $b_1,b_2,\hdots,b_s$ is a valid sequence of jumps from $2^i$ to $1$. Moreover, $a_s>1$; thus, $m>s\geq f(2^i)$. If $t>0$, then we use the induction hypothesis as follows: the number of jumps to get from $a_s$ to $1$ is greater than the number of jumps to get from $b_s=2^t$ to $1$. Since $b_1,b_2,\hdots,b_s$ is a valid sequence of jumps, we get that $$m > s+f(2^t) \geq f(2^i)$$as desired.

Finally.. Finally finished! We'll proceed by induction on i, with i=0 trivial; henceforth assume the inductive hypotheses. We'll look at the frog in reverse moves, that is, the moves $n\to n-1$ or $n\to n-2^{m_n+1}$ (this holds since if this move were to occur, indeed the end move has same $\nu_2$ as the before end move), where we end at 1. Call the $2^ik\to1,2^i\to1$ frogs frog 1 and 2, respectively. Case 1: Frog 2 does $2^ik\to 2^ik-1$. Then, have frog 1 copy all the same length of jumps of frog 2, unless it goes past 1. Then, frog 1 is at a point of the form $2^i(k-1)+2^j:0\le j<i$. Now, frog 1 can make the same length as the moves of the frog going from $2^j$ until it gets to 1, which takes less moves than going from $2^i(k-1)+2^a$ by inductive hypothesis, as needed. Case 2: Frog 2 starts off as $2^ik\to 2^ik-2^{m_{2^ik}+1}$. Then, it goes to a point of the form $2^ij<2^ik$, so if frog 1 copies the move, it reduces directly into inductive hypothesis where frog 1 takes less moves, as needed.

We reverse all of the steps and interpret the frog starting from some number and jumping $n \to n-1$ or $n \to n-2^{\nu_2(n)+1}$ on each turn, with the goal of ending up at $1$. This is clearly equivalent and will make things clearer. We now use strong induction on $i$. First, for $i=0$ the statement is clearly true for all $k$; henceforth suppose $i \geq 1$. Starting from $2^ik$, if the frog ends up at $2^i\ell$ for any $\ell<k$ at any point we are done by downwards induction $k$ (the base case is $k=1$; we don't need a strict inequality). Thus the frog must end up at $2^i(k-1)+2^m$ for some $m<i$ and jump to $2^i(k-1)-2^m$. By inductive hypothesis, reaching $1$ from $2^i(k-1)-2^m$ takes at least as many moves as reaching $1$ from $2^m$. Thus it takes less moves to go from $2^i(k-1)+2^m$ to $2^i(k-1)+1$ than to go from $2^i(k-1)+2^m$ to $1$, so it takes less moves to go from $2^ik$ to $2^i(k-1)+1$ than to go from $2^ik$ to $1$. There's an obvious bijection between a series of moves from $2^ik$ to $2^i(k-1)+1$ (since we never jump more than $2^{i-1}$ in this case) and a series of moves from $2^i$ to $1$, so it takes less moves to go from $2^i$ to $1$ than to go from $2^ik$ to $1$. $\blacksquare$