Difference between revisions of "2006 AMC 12B Problems/Problem 25"
m |
|||
Line 42: | Line 42: | ||
---------------------- | ---------------------- | ||
− | '''Lemma:''' <math>(a_n)</math> completes at <math>i</math> for some <math>i \leq | + | '''Lemma:''' <math>(a_n)</math> completes at <math>i</math> for some <math>i \leq 2000</math>. |
'''Proof:''' Suppose <math>(a_n)</math> completed at some <math>i > 2000</math> or not at all. Then by the second lemma and the fact that neither <math>999</math> nor <math>a_2</math> are <math>0</math>, none of the pairs <math>(a_1, a_2), ..., (a_{1999}, a_{2000})</math> can have a <math>0</math> or be equal to <math>(1, 1)</math>. So the first lemma implies | '''Proof:''' Suppose <math>(a_n)</math> completed at some <math>i > 2000</math> or not at all. Then by the second lemma and the fact that neither <math>999</math> nor <math>a_2</math> are <math>0</math>, none of the pairs <math>(a_1, a_2), ..., (a_{1999}, a_{2000})</math> can have a <math>0</math> or be equal to <math>(1, 1)</math>. So the first lemma implies |
Revision as of 23:10, 24 December 2012
Problem
A sequence of non-negative integers is defined by the rule for . If , and , how many different values of are possible?
Solution
We say the sequence completes at if is the minimal positive integer such that . Otherwise, we say does not complete.
Note that if , then for all , and does not divide , so if , then does not complete. (Also, cannot be 1 in this case since does not divide , so we do not care about these at all.)
From now on, suppose .
We will now show that completes at for some . We will do this with 3 lemmas.
Lemma: If , and neither value is , then .
Proof: There are 2 cases to consider.
If , then , and . So and .
If , then , and . So and .
In both cases, , as desired.
Lemma: If , then . Moreover, if instead we have for some , then .
Proof: By the way is constructed in the problem statement, having two equal consecutive terms implies that divides every term in the sequence. So and , so , so . For the proof of the second result, note that if , then , so by the first result we just proved, .
Lemma: completes at for some .
Proof: Suppose completed at some or not at all. Then by the second lemma and the fact that neither nor are , none of the pairs can have a or be equal to . So the first lemma implies so , a contradiction. Hence completes at for some .
Now we're ready to find exactly which values of we want to count.
Let's keep in mind that and that is odd. We have two cases to consider.
Case 1: If is odd, then is even, so is odd, so is odd, so is even, and this pattern must repeat every three terms because of the recursive definition of , so the terms of reduced modulo 2 are
so is odd and hence (since if completes at , then must be or for all ).
Case 2: If is even, then is odd, so is odd, so is even, so is odd, and this pattern must repeat every three terms, so the terms of reduced modulo 2 are so is even, and hence .
We have found that is true precisely when and is odd. This tells us what we need to count.
There are numbers less than and relatively prime to it ( is the Euler totient function). We want to count how many of these are even. Note that
is a 1-1 correspondence between the odd and even numbers less than and relatively prime to . So our final answer is , or .
See also
2006 AMC 12B (Problems • Answer Key • Resources) | |
Preceded by Problem 24 |
Followed by Last Question |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25 | |
All AMC 12 Problems and Solutions |