1991 USAMO Problems/Problem 3: Difference between revisions
problem and solution |
|||
| Line 15: | Line 15: | ||
Note that for all integers <math>b</math>, the sequence <math>2^0, 2^1, 2^2, \dotsc</math> is eventually becomes cyclic mod <math>b</math>. Let <math>k</math> be the period of this cycle. Since there are <math>k-1</math> nonzero residues mod <math>b</math>. <math>1 \le k\le b-1 < b</math>. Since | Note that for all integers <math>b</math>, the sequence <math>2^0, 2^1, 2^2, \dotsc</math> is eventually becomes cyclic mod <math>b</math>. Let <math>k</math> be the period of this cycle. Since there are <math>k-1</math> nonzero residues mod <math>b</math>. <math>1 \le k\le b-1 < b</math>. Since | ||
<cmath> 2, 2^2, 2^{2^2}, 2^{2^{2^2}}, \dotsc </cmath> | <cmath> 2, 2^2, 2^{2^2}, 2^{2^{2^2}}, \dotsc </cmath> | ||
does not become constant mod <math> | does not become constant mod <math>b</math>, it follows the sequence of exponents of these terms, i.e., the sequence | ||
<cmath> 1, 2, 2^2, 2^{2^{2}}, \dotsc </cmath> | <cmath> 1, 2, 2^2, 2^{2^{2}}, \dotsc </cmath> | ||
does not become constant mod <math>k</math>. Then the problem statement is false for <math>n=k</math>. Since <math>k<b</math>, this is a contradiction. Therefore the problem statement is true. <math>\blacksquare</math> | does not become constant mod <math>k</math>. Then the problem statement is false for <math>n=k</math>. Since <math>k<b</math>, this is a contradiction. Therefore the problem statement is true. <math>\blacksquare</math> | ||
Revision as of 18:33, 21 January 2013
Problem
Show that, for any fixed integer 
the sequence
![\[2, \; 2^2, \; 2^{2^2}, \; 2^{2^{2^2}}, \ldots \pmod{n}\]](http://latex.artofproblemsolving.com/a/b/9/ab9bc822f0ae15f00eebdb0827fd4654386f4aef.png)
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
![\[2, 2^2, 2^{2^2}, 2^{2^{2^2}}, \dotsc\]](http://latex.artofproblemsolving.com/6/9/8/698c31481558552d1d3d0d9de46bdec50a637238.png)
does not become constant mod , it follows the sequence of exponents of these terms, i.e., the sequence
![\[1, 2, 2^2, 2^{2^{2}}, \dotsc\]](http://latex.artofproblemsolving.com/c/9/a/c9a7137c3aa003df4d4eb7373bb2b08512ec454f.png)
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 | ||
