Art of Problem Solving
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

1991 USAMO Problems/Problem 3: Difference between revisions

← Older edit
Etude (talk | contribs)
181 edits
No edit summary
Nedsanger (talk | contribs)
editor
40 edits
 
(5 intermediate revisions by 3 users not shown)
Line 7: Line 7:
[The tower of exponents is defined by <math>a_1 = 2, \; a_{i+1} = 2^{a_i}</math>. Also <math>a_i \pmod{n}</math> means the remainder which results from dividing <math>\,a_i\,</math> by <math>\,n</math>.]
[The tower of exponents is defined by <math>a_1 = 2, \; a_{i+1} = 2^{a_i}</math>. Also <math>a_i \pmod{n}</math> means the remainder which results from dividing <math>\,a_i\,</math> by <math>\,n</math>.]


== Solution ==
== Solution 1 ==


Suppose that the problem statement is false for some integer <math>n \ge 1</math>.  Then there is a least <math>n</math>, which we call <math>b</math>, for which the statement is false.
Suppose that the problem statement is false for some integer <math>n \ge 1</math>.  Then there is a least <math>n</math>, which we call <math>b</math>, for which the statement is false.
Line 13: Line 13:
Since all integers are equivalent mod 1, <math>b\neq 1</math>.
Since all integers are equivalent mod 1, <math>b\neq 1</math>.


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> 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>b</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
Line 21: Line 21:
Note that we may replace 2 with any other positive integer, and both the problem and this solution remain valid.
Note that we may replace 2 with any other positive integer, and both the problem and this solution remain valid.


{{alternate solutions}}
== Solution 2 ==


== Resources ==
We’ll prove by strong induction that for every natural number <math>n</math>, the sequence <math>a_1, a_2, \ldots</math> is eventually constant. Since every term of the sequence is <math>0 \mathrm{\ mod\ } 1</math>, the claim is true when <math>n = 1</math>. Assuming that it’s true for <math>1, \ldots, n</math>, we’ll now show that it’s true for <math>n + 1</math> as well.
 
Suppose first that <math>n + 1</math> is odd. Since <math>\varphi(n + 1) < n + 1</math>, by our inductive hypothesis there exists an <math>m</math> such that
 
<cmath>a_m = a_{m + 1} = a_{m + 2} = \cdots \pmod{\varphi(n + 1)}.</cmath>
 
Since <math>n + 1</math> is coprime to powers of <math>2</math>, it follows by Euler’s theorem that
 
<cmath>2^{a_m} = 2^{a_{m + 1}} = 2^{a_{m + 2}} = \cdots \pmod{n + 1},</cmath>
 
or equivalently
 
<cmath>a_{m + 1} = a_{m + 2} = a_{m + 3} = \cdots \pmod{n + 1},</cmath>
 
which is what we wanted to show.
 
Now suppose that <math>n + 1</math> is even. Write <math>n + 1 = 2^{k} \cdot s</math>, where <math>1 \leq s < n + 1</math> is odd. The series must eventually be constant <math>\textrm{mod\ } 2^k</math>, since <math>a_m = 0 \textrm{\ mod\ } {2^k}</math> for large enough <math>m</math>. And by our inductive hypothesis, the series must also eventually be constant <math>\textrm{mod\ } s</math>. So for large enough <math>m</math>,
 
<cmath>a_m = a_{m + 1} = a_{m + 2} = \cdots \pmod{2^k},</cmath>
<cmath>a_m = a_{m + 1} = a_{m + 2} = \cdots \pmod{s}. </cmath>
 
Since <math>2^k</math> and <math>s</math> are coprime, these equations are also true modulo <math>2^k \cdot s = n + 1</math>. So
 
<cmath>a_m = a_{m + 1} = a_{m + 2} = \cdots \pmod{n + 1},</cmath>
 
which completes the proof.
 
== See Also ==


{{USAMO box|year=1991|num-b=2|num-a=4}}
{{USAMO box|year=1991|num-b=2|num-a=4}}

Latest revision as of 18:18, 5 June 2023

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 1

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$ 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.

Solution 2

We’ll prove by strong induction that for every natural number $n$, the sequence $a_1, a_2, \ldots$ is eventually constant. Since every term of the sequence is $0 \mathrm{\ mod\ } 1$, the claim is true when $n = 1$. Assuming that it’s true for $1, \ldots, n$, we’ll now show that it’s true for $n + 1$ as well.

Suppose first that $n + 1$ is odd. Since $\varphi(n + 1) < n + 1$, by our inductive hypothesis there exists an $m$ such that

\[a_m = a_{m + 1} = a_{m + 2} = \cdots \pmod{\varphi(n + 1)}.\]

Since $n + 1$ is coprime to powers of $2$, it follows by Euler’s theorem that

\[2^{a_m} = 2^{a_{m + 1}} = 2^{a_{m + 2}} = \cdots \pmod{n + 1},\]

or equivalently

\[a_{m + 1} = a_{m + 2} = a_{m + 3} = \cdots \pmod{n + 1},\]

which is what we wanted to show.

Now suppose that $n + 1$ is even. Write $n + 1 = 2^{k} \cdot s$, where $1 \leq s < n + 1$ is odd. The series must eventually be constant $\textrm{mod\ } 2^k$, since $a_m = 0 \textrm{\ mod\ } {2^k}$ for large enough $m$. And by our inductive hypothesis, the series must also eventually be constant $\textrm{mod\ } s$. So for large enough $m$,

\[a_m = a_{m + 1} = a_{m + 2} = \cdots \pmod{2^k},\] \[a_m = a_{m + 1} = a_{m + 2} = \cdots \pmod{s}.\]

Since $2^k$ and $s$ are coprime, these equations are also true modulo $2^k \cdot s = n + 1$. So

\[a_m = a_{m + 1} = a_{m + 2} = \cdots \pmod{n + 1},\]

which completes the proof.

See Also

1991 USAMO (Problems • Resources)
Preceded by
Problem 2 		Followed by
Problem 4
1 • 2 • 3 • 4 • 5
All USAMO Problems and Solutions

These problems are copyrighted © by the Mathematical Association of America.

Retrieved from "https://wiki.aopstest.com/wiki/index.php?title=1991_USAMO_Problems/Problem_3&oldid=193945"