Difference between revisions of "1991 USAMO Problems/Problem 3"
(→Solution 2) |
(→Solution 2) |
||
Line 29: | Line 29: | ||
<cmath>a_m = a_{m + 1} = a_{m + 2} = \cdots \pmod{\varphi(n + 1)}.</cmath> | <cmath>a_m = a_{m + 1} = a_{m + 2} = \cdots \pmod{\varphi(n + 1)}.</cmath> | ||
− | Since <math>n + 1</math> is coprime to | + | Since <math>n + 1</math> is coprime to powers of <math>2</math> of the sequence, it follows from Euler’s theorem that |
<cmath>2^{a_m} = 2^{a_{m + 1}} = 2^{a_{m + 2}} = \cdots \pmod{n + 1},</cmath> | <cmath>2^{a_m} = 2^{a_{m + 1}} = 2^{a_{m + 2}} = \cdots \pmod{n + 1},</cmath> |
Revision as of 19:17, 5 June 2023
Contents
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 1
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
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.
Solution 2
We’ll prove by strong induction that for every natural number , the sequence
is eventually constant. Since every term of the sequence is
, the claim is true when
. Assuming that it’s true for
, we’ll now show that it’s true for
as well.
Suppose first that is odd. Since
, by our inductive hypothesis there exists an
such that
Since is coprime to powers of
of the sequence, it follows from Euler’s theorem that
or equivalently
which is what we wanted to show.
Now suppose that is even. Write
, where
is odd. The series must eventually be constant
, since
for large enough
. And by our inductive hypothesis, the series must also eventually be constant
. So for large enough
,
Since and
are coprime, these equations are also true modulo
. So
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 |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.