# Difference between revisions of "2006 USAMO Problems/Problem 5"

## Problem

(Zoran Sunik) 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^i k$ is greater than the minimum number of jumps needed to reach $2^i$.

## Solutions

### Solution 1

For $i\geq 0$ and $k\geq 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\qquad (1)$$ for all $i\geq 0$ and $k\geq 2$. We prove this using the method of descent.

First note that $(1)$ holds for $i = 0$ and all $k\geq 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\geq 2$. Now assume that $(1)$ is not true for all choices of $i$ and $k$. Let $i_0$ be the minimal value of $i$ for which $(1)$ fails for some $k$, let $k_0$ be the minimal value of $k > 1$ for which $x_{i_0,k}\leq x_{i_0,1}$. Then it must be the case that $i_0\geq 1$ and $k_0\geq 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^{t_0}$ because it takes more jumps to reach $2^{t_0} k_0$ than it does to reach $2^{t_0}$. Let $2^{M+1}$, $M\geq 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$. 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_0}$. 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$.

### Solution 2

Suppose $x_0 = 1, x_1, \ldots, x_t = 2^i k$ are the integers visited by the frog on his trip from 1 to $2^i k$, $k\geq 2$. Let $s_j = x_j - x_{j-1}$ be the jump sizes. Define a reduced path $y_j$ inductively by $$y_j = \left\{\begin{array}{ll} y_{j-1} + s_j & \text{if }y_{j-1} + s_j\leq 2^i, \\ y_{j-1} & \text{otherwise.} \end{array}\right.$$ 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\leq 2^i$ for all $j$. Suppose $2^i - 2^{r+1} < y_j\leq 2^i - 2^r$ for some $0\leq r\leq 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\geq 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\leq 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.