Difference between revisions of "2006 USAMO Problems/Problem 5"
Ragnarok23 (talk | contribs) |
(→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 | + | |
− | *[[ | + | == 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 , 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.