Difference between revisions of "2006 USAMO Problems/Problem 5"
(→Solution 1) |
|||
(4 intermediate revisions by 2 users not shown) | |||
Line 1: | Line 1: | ||
== Problem == | == 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</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 == | ||
+ | * <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]] | [[Category:Olympiad Number Theory Problems]] | ||
{{MAA Notice}} | {{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 , then it can jump either to or to where is the largest power of 2 that is a factor of . Show that if is a positive integer and is a nonnegative integer, then the minimum number of jumps needed to reach is greater than the minimum number of jumps needed to reach .
Solutions
Solution 1
For and , let denote the minimum number of jumps needed to reach the integer . We must prove that for all and . We prove this using the method of descent.
First note that holds for and all , because it takes 0 jumps to reach the starting value , and at least one jump to reach . Now assume that is not true for all choices of and . Let be the minimal value of for which fails for some , let be the minimal value of for which . Then it must be the case that and .
Let be a shortest sequence of integers that the frog occupies in jumping from 1 to . The length of each jump, that is, the difference between consecutive integers in , is either 1 or a positive integer power of 2. The sequence cannot contain because it takes more jumps to reach than it does to reach . Let , be the length of the longest jump made in generating . Such a jump can only be made from a number that is divisible by (and by no higher power of 2). Thus we must have , since otherwise a number divisible by is visited before is reached, contradicting the definition of .
Let be the length of the jump when the frog jumps over . If this jump starts at for some positive integer , then it will end at . Since it goes over we see or . Thus and the jump over is from to .
Considering the jumps that generate , let be the number of jumps from 1 to , and let be the number of jumps from to . By definition of , it follows that can be reached from 1 in less than jumps. On the other hand, because , the number can be reached from in exactly jumps by using the same jump length sequence as in jumping from to . The key point here is that the shift by does not affect any of divisibility conditions needed to make jumps of the same length. In particular, with the exception of the last entry, , all of the elements of are of the form with , again because of the definition of . Because and the number is odd, a jump of size can be made from just as it can be made from .
Thus the frog can reach from 1 in less than jumps, and can then reach from in jumps. Hence the frog can reach from 1 in less than jumps, that is, in fewer jumps than needed to get to and hence in fewer jumps than required to get to . This contradicts the definition of .
Solution 2
Suppose are the integers visited by the frog on his trip from 1 to , . Let be the jump sizes. Define a reduced path inductively by Say a jump is deleted in the second case. We will show that the distinct integers among the give a shorter path from 1 to . Clearly for all . Suppose for some . Then every deleted jump before must have length greater than , hence must be a multiple of . Thus . If , then either (in which case this is a valid jump) or is the exact power of 2 dividing . In the second case, since , the congruence says is also the exact power of 2 dividing , thus again this is a valid jump. Thus the distinct form a valid path for the frog. If the congruence gives , but this is impossible for . Hence we see , that is, the reduced path ends at . Finally since the reduced path ends at 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 (Problems • Resources) | ||
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.