Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1991 USAMO Problems/Problem 3"

(problem and solution)
 
(→‎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>a</math>, it follows the sequence of exponents of these terms, i.e., the sequence
+
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 $\,n \geq 1,\,$ the sequence \[2, \; 2^2, \; 2^{2^2}, \; 2^{2^{2^2}}, \ldots \pmod{n}\] is eventually constant.

[The tower of exponents is defined by $a_1 = 2, \; a_{i+1} = 2^{a_i}$. Also $a_i \pmod{n}$ means the remainder which results from dividing $\,a_i\,$ by $\,n$.]

Solution

Suppose that the problem statement is false for some integer $n \ge 1$. Then there is a least $n$, which we call $b$, for which the statement is false.

Since all integers are equivalent mod 1, $b\neq 1$.

Note that for all integers $b$, the sequence $2^0, 2^1, 2^2, \dotsc$ is eventually becomes cyclic mod $b$. Let $k$ be the period of this cycle. Since there are $k-1$ nonzero residues mod $b$. $1 \le k\le b-1 < b$. Since \[2, 2^2, 2^{2^2}, 2^{2^{2^2}}, \dotsc\] does not become constant mod $b$, it follows the sequence of exponents of these terms, i.e., the sequence \[1, 2, 2^2, 2^{2^{2}}, \dotsc\] does not become constant mod $k$. Then the problem statement is false for $n=k$. Since $k<b$, this is a contradiction. Therefore the problem statement is true. $\blacksquare$

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1991_USAMO_Problems/Problem_3&oldid=50580"