Difference between revisions of "1991 USAMO Problems/Problem 3"
(→Solution) |
|||
Line 28: | Line 28: | ||
* [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=113561#113561 Discussion on AoPS/MathLinks] | * [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=113561#113561 Discussion on AoPS/MathLinks] | ||
* [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=110644#110644 Discussion of generalization] | * [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=110644#110644 Discussion of generalization] | ||
+ | {{MAA Notice}} | ||
[[Category:Olympiad Number Theory Problems]] | [[Category:Olympiad Number Theory Problems]] |
Revision as of 20:51, 3 July 2013
Problem
Show that, for any fixed integer the sequence
is eventually constant.
[The tower of exponents is defined by . Also
means the remainder which results from dividing
by
.]
Solution
Suppose that the problem statement is false for some integer . Then there is a least
, which we call
, for which the statement is false.
Since all integers are equivalent mod 1, .
Note that for all integers , the sequence
is eventually becomes cyclic mod
. Let
be the period of this cycle. Since there are
nonzero residues mod
.
. Since
does not become constant mod
, it follows the sequence of exponents of these terms, i.e., the sequence
does not become constant mod
. Then the problem statement is false for
. Since
, this is a contradiction. Therefore the problem statement is true.
Note that we may replace 2 with any other positive integer, and both the problem and this solution remain valid.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.
Resources
1991 USAMO (Problems • Resources) | ||
Preceded by Problem 2 |
Followed by Problem 4 | |
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.