1993 USAMO Problems/Problem 4
Problem 4
Let ,
be odd positive integers. Define the sequence
by putting
,
, and by letting
for
be the greatest odd divisor of
.
Show that
is constant for
sufficiently large and determine the eventual
value as a function of
and
.
Solution
Part 1) Prove that is constant for sufficiently large
.
Note that if there is some for any
, then
, which is odd. Thus,
and by induction, all
is constant for
.
Also note that since average of
positive number is always positive.
Thus, assume for contradiction, ,
.
Then, ,
Thus, and that means that
is a strictly decreasing function and it must reach
as
, which contradict with the fact that
.
Part 1 proven.
Part 2) Show that the constant is .
For any where
.
for
with the same property except with
and
.
Therefore, if I prove that the constant for any with relatively prime
,
is
, then I have shown that part 2 is true.
Lemma) If , then
.
Assume for contradiction that , since both
and
are odd,
is not divisible by
.
for some
such that
is odd.
, where
and
is another integer.
Thus, is divisible by
which contradicts with the assumption that
.
Lemma proven
By induction, since
.
Since there must exist some where
(part 1),
.
Resources
1993 USAMO (Problems • Resources) | ||
Preceded by Problem 3 |
Followed by Problem 5 | |
1 • 2 • 3 • 4 • 5 | ||
All USAMO Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.