1991 USAMO Problems/Problem 3: Difference between revisions

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.

@@ Line 29: / Line 29: @@
 <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> of the sequence, it follows from Euler’s theorem that
+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>

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

Page

Toolbox

Search

1991 USAMO Problems/Problem 3: Difference between revisions

Latest revision as of 18:18, 5 June 2023

Contents

Problem

Solution 1

Solution 2

See Also