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

(Solution 1)
 
(7 intermediate revisions by 5 users not shown)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
== Solution ==
+
(''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 <math>n</math>, then it can jump either to <math>n+1</math> or to <math>n+2^{m_n+1}</math> where <math>2^{m_n}</math> is the largest power of 2 that is a factor of <math>n</math>. Show that if <math>k\ge 2</math> is a positive integer and <math>i</math> is a nonnegative integer, then the minimum number of jumps needed to reach <math>2^i k</math> is greater than the minimum number of jumps needed to reach <math>2^i</math>.
== See Also ==
+
 
*[[2006 USAMO Problems]]
+
== Solutions ==
 +
 
 +
=== Solution 1 ===
 +
For <math>i\geq 0</math> and <math>k\geq 1</math>, let <math>x_{i,k}</math> denote the minimum number of jumps needed to reach the integer <math>n_{i,k} = 2^i k</math>. We must prove that
 +
<cmath>x_{i,k} > x_{i,1}\qquad\qquad (1)</cmath>
 +
for all <math>i\geq 0</math> and <math>k\geq 2</math>. We prove this using the method of descent.
 +
 
 +
First note that <math>(1)</math> holds for <math>i = 0</math> and all <math>k\geq 2</math>, because it takes 0 jumps to reach the starting value <math>n_{0,1} = 1</math>, and at least one jump to reach <math>n_{0,k} = k\geq 2</math>. Now assume that <math>(1)</math> is not true for all choices of <math>i</math> and <math>k</math>. Let <math>i_0</math> be the minimal value of <math>i</math> for which <math>(1)</math> fails for some <math>k</math>, let <math>k_0</math> be the minimal value of <math>k > 1</math> for which <math>x_{i_0,k}\leq x_{i_0,1}</math>. Then it must be the case that <math>i_0\geq 1</math> and <math>k_0\geq 2</math>.
 +
 
 +
Let <math>J_{i_0,k_0}</math> be a shortest sequence of <math>x_{i_0,k_0} + 1</math> integers that the frog occupies in jumping from 1 to <math>2^{i_0} k_0</math>. The length of each jump, that is, the difference between consecutive integers in <math>J_{i_0,k_0}</math>, is either 1 or a positive integer power of 2. The sequence <math>J_{i_0,k_0}</math> cannot contain <math>2^{t_0}</math> because it takes more jumps to reach <math>2^{t_0} k_0</math> than it does to reach <math>2^{t_0}</math>. Let <math>2^{M+1}</math>, <math>M\geq 0</math> be the length of the longest jump made in generating <math>J_{i_0,k_0}</math>. Such a jump can only be made from a number that is divisible by <math>2^M</math> (and by no higher power of 2). Thus we must have <math>M < i_0</math>, since otherwise a number divisible by <math>2^{i_0}</math> is visited before <math>2^{i_0} k_0</math> is reached, contradicting the definition of <math>k_0</math>.
 +
 
 +
Let <math>2^{m+1}</math> be the length of the jump when the frog jumps over <math>2^{i_0}</math>. If this jump starts at <math>2^m(2t - 1)</math> for some positive integer <math>t</math>, then it will end at <math>2^m(2t - 1) + 2^{m+1} = 2^m(2t + 1)</math>. Since it goes over <math>2^{i_0}</math> we see <math>2^m(2t - 1) < 2^{i_0} < 2^m(2t + 1)</math> or <math>(2^{i_0-m} - 1)/2 < t < (2^{i_0-m} + 1)/2</math>. Thus <math>t = 2^{i_0-m-1}</math> and the jump over <math>2^{i_0}</math> is from <math>2^m(2^{i_0-m} - 1) = 2^{i_0} - 2^m</math> to <math>2^m(2^{i_0-m}+1) = 2^{i_0} + 2^m</math>.
 +
 
 +
Considering the jumps that generate <math>J_{i_0,k_0}</math>, let <math>N_1</math> be the number of jumps from 1 to <math>2^{i_0} + 2^m</math>, and let <math>N_2</math> be the number of jumps from <math>2^{i_0} + 2^m</math> to <math>2^{i_0}k</math>. By definition of <math>i_0</math>, it follows that <math>2^m</math> can be reached from 1 in less than <math>N_1</math> jumps. On the other hand, because <math>m < i_0</math>, the number <math>2^{i_0}(k_0 - 1)</math> can be reached from <math>2^m</math> in exactly <math>N_2</math> jumps by using the same jump length sequence as in jumping from <math>2^m + 2^{i_0}</math> to <math>2^{i_0} k_0 = 2^{i_0}(k_0 - 1) + 2^{i_0}</math>. The key point here is that the shift by <math>2^{i_0}</math> does not affect any of divisibility conditions needed to make jumps of the same length. In particular, with the exception of the last entry, <math>2^{i_0} k_0</math>, all of the elements of <math>J_{i_0,k_0}</math> are of the form <math>2^p(2t + 1)</math> with <math>p < i_0</math>, again because of the definition of <math>k_0</math>. Because <math>2^p(2t + 1) - 2^{i_0} = 2^p(2t - 2^{i_0-p} + 1)</math> and the number <math>2t + 2^{i_0-p} + 1</math> is odd, a jump of size <math>2^{p+1}</math> can be made from <math>2^p(2t + 1) - 2^{i_0}</math> just as it can be made from <math>2^p(2t + 1)</math>.
 +
 
 +
Thus the frog can reach <math>2^m</math> from 1 in less than <math>N_1</math> jumps, and can then reach <math>2^{i_0}(k_0 - 1)</math> from <math>2^m</math> in <math>N_2</math> jumps. Hence the frog can reach <math>2^{i_0}(k_0 - 1)</math> from 1 in less than <math>N_1 + N_2</math> jumps, that is, in fewer jumps than needed to get to <math>2^{i_0} k_0</math> and hence in fewer jumps than required to get to <math>2^{i_0}</math>. This contradicts the definition of <math>k_0</math>.
 +
 
 +
=== Solution 2 ===
 +
Suppose <math>x_0 = 1, x_1, \ldots, x_t = 2^i k</math> are the integers visited by the frog on his trip from 1 to <math>2^i k</math>, <math>k\geq 2</math>. Let <math>s_j = x_j - x_{j-1}</math> be the jump sizes. Define a reduced path <math>y_j</math> inductively by
 +
<cmath>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.</cmath>
 +
Say a jump <math>s_j</math> is deleted in the second case. We will show that the distinct integers among the <math>y_j</math> give a shorter path from 1 to <math>2^i</math>. Clearly <math>y_j\leq 2^i</math> for all <math>j</math>. Suppose <math>2^i - 2^{r+1} < y_j\leq 2^i - 2^r</math> for some <math>0\leq r\leq i - 1</math>. Then every deleted jump before <math>y_j</math> must have length greater than <math>2^r</math>, hence must be a multiple of <math>2^{r+1}</math>. Thus <math>y_j\equiv x_j\pmod{2^{r+1}}</math>. If <math>y_{j+1} > y_j</math>, then either <math>s_{j+1} = 1</math> (in which case this is a valid jump) or <math>s_{j+1}/2 = 2^m</math> is the exact power of 2 dividing <math>x_j</math>. In the second case, since <math>2^r\geq s_{j+1} > 2^m</math>, the congruence says <math>2^m</math> is also the exact power of 2 dividing <math>y_j</math>, thus again this is a valid jump. Thus the distinct <math>y_j</math> form a valid path for the frog. If <math>j = t</math> the congruence gives <math>y_t\equiv x_t\equiv 0\pmod{2^{r+1}}</math>, but this is impossible for <math>2^i - 2^{r+1} < y_t\leq 2^i - 2^r</math>. Hence we see <math>y_t = 2^i</math>, that is, the reduced path ends at <math>2^i</math>. Finally since the reduced path ends at <math>2^i < 2^i k</math> at least one jump must have been deleted and it is strictly shorter than the original path.
 +
 
 +
{{alternate solutions}}
 +
 
 +
== See also ==
 +
* <url>viewtopic.php?t=84558 Discussion on AoPS/MathLinks</url>
 +
 
 +
{{USAMO newbox|year=2006|num-b=4|num-a=6}}
 +
 
 +
[[Category:Olympiad Number Theory Problems]]
 +
{{MAA Notice}}

Latest revision as of 17:23, 26 March 2016

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.

See also

  • <url>viewtopic.php?t=84558 Discussion on AoPS/MathLinks</url>
2006 USAMO (ProblemsResources)
Preceded by
Problem 4
Followed by
Problem 6
1 2 3 4 5 6
All USAMO Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Invalid username
Login to AoPS