Difference between revisions of "1991 USAMO Problems/Problem 3"
(problem and solution) |
(→Solution 2) |
||
(7 intermediate revisions by 5 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> | + | 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> | + | 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> | ||
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. | ||
− | + | == Solution 2 == | |
− | == | + | 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}} | ||
* [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=113561#113561 Discussion on AoPS/MathLinks] | * [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=113561#113561 Discussion on AoPS/MathLinks] | ||
* [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=110644#110644 Discussion of generalization] | * [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=110644#110644 Discussion of generalization] | ||
+ | {{MAA Notice}} | ||
[[Category:Olympiad Number Theory Problems]] | [[Category:Olympiad Number Theory Problems]] |
Latest revision as of 19:18, 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
, it follows by 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.