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.

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

2006 USAMO (Problems • Resources)
Preceded by Problem 4	Followed by Problem 6
1 • 2 • 3 • 4 • 5 • 6
All USAMO Problems and Solutions

Page

Toolbox

Search

2006 USAMO Problems/Problem 5

Contents

Problem

Solutions

Solution 1

Solution 2

See also