A mathematical frog jumps along the number line. The frog starts at , and jumps according to the following rule: if the frog is at integer , then it can jump either to or to where is the largest power of that is a factor of Show that if is a positive integer and is a nonnegative integer, then the minimum number of jumps needed to reach is greater than the minimum number of jumps needed to reach
_______

Let be the minimal sequence of jumps for the frog to reach with and Let be the smallest term greater than We define the sequence such that for Since for all is still a valid sequence. Now we have three cases:

(1) If then we are done, since we have a sequence, namely that gets to in a shorter number of steps.

(2) If is not a power of this contradicts the fact that is minimal: Let where is odd and Then, has as its largest power-of-2 factor. This means that is either or both of which are greater than

(3) If is a power of it suffices to show that it takes less moves to get to than Note that this is because is also the shortest path to We apply strong induction. Clearly, if then it takes less steps to get to than Since we are done by the inductive hypothesis.

Main idea: In order to apply induction, the start point of a sequence must be equivalent to in terms of the given conditions. Since try the reverse-sequence from the end of the sequence.