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

Latest revision as of 16: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.

@@ Line 1: / Line 1: @@
 == 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 <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 . 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$.
+(''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>.
 == Solutions ==
-{{solution}}
+=== 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 ==

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