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+2mn​+1 where 2mn​ is the largest power of 2 that is a factor of n. Show that if k≥2 is a positive integer and i is a nonnegative integer, then the minimum number of jumps needed to reach 2ik is greater than the minimum number of jumps needed to reach 2i.
Solution:
First Solution. For i≥0 and k≥1, let xi,k​ denote the minimum number of jumps needed to reach the integer ni,k​=2ik. We must prove that
xi,k​>xi,1​(1)
for all i≥0 and k≥2. We prove this using the method of descent.
First note that (1) holds for i=0 and all k≥2, because it takes 0 jumps to reach the starting value n0,1​=1, and at least one jump to reach n0,k​=k≥2. Now assume that that (1) is not true for all choices of i and k. Let i0​ be the minimal value of i for which (1) fails for some k, let k0​ be the minimal value of k>1 for which xi0​,k​≤xi0​,1​. Then it must be the case that i0​≥1 and k0​≥2.
Let Ji0​,k0​​ be a shortest sequence of xi0​,k0​​+1 integers that the frog occupies in jumping from 1 to 2i0​k0​. The length of each jump, that is, the difference between consecutive integers in Ji0​,k0​​, is either 1 or a positive integer power of 2 . The sequence Ji0​,k0​​ cannot contain 2i0​ because it takes more jumps to reach 2i0​k0​ than it does to reach 2i0​. Let 2M+1,M≥0 be the length of the longest jump made in generating Ji0​,k0​​. Such a jump can only be made from a number that is divisible by 2M (and by no higher power of 2 ). Thus we must have M<i0​, since otherwise a number divisible by 2i0​ is visited before 2i0​k0​ is reached, contradicting the definition of k0​.
Let 2m+1 be the length of the jump when the frog jumps over 2i0​. If this jump starts at 2m(2t−1) for some positive integer t, then it will end at 2m(2t−1)+2m+1=2m(2t+1). Since it goes over 2i0​ we see 2m(2t−1)<2i0​<2m(2t+1) or (2i0​−m−1)/2<t< (2i0​−m+1)/2. Thus t=2i0​−m−1 and the jump over 2i0​ is from 2m(2i0​−m−1)=2i0​−2m to 2m(2i0​−m+1)=2i0​+2m.
Considering the jumps that generate Ji0​,k0​​, let N1​ be the number of jumps from 1 to 2i0​+2m, and let N2​ be the number of jumps from =2i0​+2m to 2i0​k. By definition of i0​, it follows that 2m can be reached from 1 in less than N1​ jumps. On the other hand, because m<i0​, the number 2i0​(k0​−1) can be reached from 2m in exactly N2​ jumps by using the same jump length sequence as in jumping from 2m+2i0​ to 2i0​k0​=2i0​(k0​−1)+20i​. The key point here is that the shift by 2i0​ does not affect any of divisibility conditions needed to make jumps of the same length. In particular, with the exception of the last entry, 2i0​k0​, all of the elements of Ji0​,k0​​ are of the form 2p(2t+1) with p<i0​, again because of the definition of k0​. Because 2p(2t+1)−2i0​=2p(2t−2i0​−p+1) and the number 2t+2i0​−p+1 is odd, a jump of size 2p+1 can be made from 2p(2t+1)−2i0​ just as it can be made from 2p(2t+1).
Thus the frog can reach 2m from 1 in less than N1​ jumps, and can then reach 2i0​(k0​−1) from 2m in N2​ jumps. Hence the frog can reach 2i0​(k0​−1) from 1 in less than N1​+N2​ jumps, that is, in fewer jumps than needed to get to 2i0​k0​ and hence in fewer jumps than required to get to 2i0​. This contradicts the definition of k0​.
Second Solution. Suppose x0​=1,x1​,…,xt​=2ik are the integers visited by the frog on his trip from 1 to 2ik,k≥2. Let sj​=xj​−xj−1​ be the jump sizes. Define a reduced path yj​ inductively by
yj​={yj−1​+sj​yj−1​​ if yj−1​+sj​≤2i otherwise ​
Say a jump sj​ is deleted in the second case. We will show that the distinct integers among the yj​ give a shorter path from 1 to 2i. Clearly yj​≤2i for all j. Suppose 2i−2r+1<yj​≤2i−2r for some 0≤r≤i−1. Then every deleted jump before yj​ musthave length greater than 2r, hence must be a multiple of 2r+1. Thus yj​≡xj​(mod2r+1). If yj+1​>yj​, then either sj+1​=1 (in which case this is a valid jump) or sj+1​/2=2m is the exact power of 2 dividing xj​. In the second case, since 2r≥sj+1​>2m, the congruence says 2m is also the exact power of 2 dividing yj​, thus again this is a valid jump. Thus the distinct yj​ form a valid path for the frog. If j=t the congruence gives yt​≡xt​≡0(mod 2r+1 ), but this is impossible for 2i−2r+1<yt​≤2i−2r. Hence we see yt​=2i, that is, the reduced path ends at 2i. Finally since the reduced path ends at 2i<2ik at least one jump must have been deleted and it is strictly shorter than the original path.
This problem was proposed by Zoran Sunik.
The problems on this page are the property of the MAA's American Mathematics Competitions