Difference between revisions of "2006 AMC 12B Problems/Problem 25"
(→Problem) |
(→Solution) |
||
Line 17: | Line 17: | ||
== Solution == | == Solution == | ||
− | + | We say the sequence <math>(a_n)</math> completes at <math>i</math> if <math>i</math> is the minimal positive integer such that <math>a_i = a_{i + 1} = 1</math>. Otherwise, we say <math>(a_n)</math> does not complete. | |
+ | |||
+ | |||
+ | Note that if <math>d = \gcd(999, a_2) \neq 1</math>, then <math>d|a_n</math> for all <math>n \geq 1</math>, and <math>d</math> does not divide <math>1</math>, so if <math>\gcd(999, a_2) \neq 1</math>, then <math>(a_n)</math> does not complete. | ||
+ | |||
+ | From now on, suppose <math>\gcd(999, a_2) = 1</math>. | ||
+ | |||
+ | |||
+ | We will now show that <math>(a_n)</math> completes at <math>i</math> for some <math>i \leq 2006</math>. We will do this with 3 lemmas. | ||
+ | |||
+ | |||
+ | '''Lemma:''' If <math>a_j \neq a_{j + 1}</math>, and neither value is <math>0</math>, then <math>\max(a_j, a_{j + 1}) > \max(a_{j + 2}, a_{j + 3})</math>. | ||
+ | |||
+ | '''Proof:''' There are 2 cases to consider. | ||
+ | |||
+ | If <math>a_j > a_{j + 1}</math>, then <math>a_{j + 2} = a_j - a_{j + 1}</math>, and <math>a_{j + 3} = |a_j - 2a_{j + 1}|</math>. So <math>a_j > a_{j + 2}</math> and <math>a_j > a_{j + 3}</math>. | ||
+ | |||
+ | If <math>a_j < a_{j + 1}</math>, then <math>a_{j + 2} = a_{j + 1} - a_j</math>, and <math>a_{j + 3} = a_j</math>. So <math>a_{j + 1} > a_{j + 2}</math> and <math>a_{j + 1} > a_{j + 3}</math>. | ||
+ | |||
+ | In both cases, <math>\max(a_j, a_{j + 1}) = \max(a_{j + 2}, a_{j + 3})</math>, as desired. | ||
+ | ---------------------- | ||
+ | |||
+ | '''Lemma:''' If <math>a_i = a_{i + 1}</math>, then <math>a_i = 1</math>. Moreover, if instead we have <math>a_i = 0</math> for some <math>i > 2</math>, then <math>a_{i - 1} = a_{i - 2} = 1</math>. | ||
+ | |||
+ | '''Proof:''' By the way <math>(a_n)</math> is constructed in the problem statement, having two equal consecutive terms <math>a_i = a_{i + 1}</math> implies that <math>a_i</math> divides every term in the sequence. So <math>a_i | 999</math> and <math>a_i | a_2</math>, so <math>a_i | \gcd(999, a_2) = 1</math>, so <math>a_i = 1</math>. For the proof of the second result, note that if <math>a_i = 0</math>, then <math>a_{i - 1} = a_{i - 2}</math>, so by the first result we just proved, <math>a_{i - 2} = a_{i - 1} = 1</math>. | ||
+ | ---------------------- | ||
+ | |||
+ | '''Lemma:''' <math>(a_n)</math> completes at <math>i</math> for some <math>i \leq 2006</math>. | ||
+ | |||
+ | '''Proof:''' Suppose <math>(a_n)</math> completed at some <math>i > 2000</math> or not at all. Then by the second lemma, 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 | ||
+ | <cmath>\max(a_1, a_2) > \max(a_3, a_4) > \cdots > \max(a_{1999}, a_{2000}),</cmath> | ||
+ | so <math>999 = \max(a_1, a_2) \geq 1000</math>, a contradiction. Hence <math>(a_n)</math> completes at <math>i</math> for some <math>i \leq 2000</math>. | ||
+ | ---------------------- | ||
+ | |||
+ | |||
+ | Now we're ready to find exactly which values of <math>a_2</math> we want to count. | ||
+ | |||
+ | Let's keep in mind that <math>2006 \equiv 2 \pmod 3</math> and that <math>a_1 = 999</math> is odd. We have two cases to consider. | ||
+ | |||
+ | |||
+ | '''Case 1:''' If <math>a_2</math> is odd, then <math>a_3</math> is even, so <math>a_4</math> is odd, so <math>a_5</math> is odd, so <math>a_6</math> is even, and this pattern must repeat every three terms because of the recursive definition of <math>(a_n)</math>, so the terms of <math>(a_n)</math> reduced modulo 2 are | ||
+ | <cmath>1, 1, 0, 1, 1, 0, ...,</cmath> | ||
+ | so <math>a_{2006}</math> is odd and hence <math>1</math>. | ||
+ | --------------------- | ||
+ | |||
+ | '''Case 2:''' If <math>a_2</math> is even, then <math>a_3</math> is odd, so <math>a_4</math> is odd, so <math>a_5</math> is even, so <math>a_6</math> is odd, and this pattern must repeat every three terms, so the terms of <math>(a_n)</math> reduced modulo 2 are | ||
+ | <cmath>1, 0, 1, 1, 0, 1, ...,</cmath> | ||
+ | so <math>a_{2006}</math> is even, and hence <math>0</math>. | ||
+ | --------------------- | ||
+ | |||
+ | |||
+ | We have found that <math>a_{2006} = 1</math> is true precisely when <math>\gcd(999, a_2) = 1</math> and <math>a_2</math> is odd. This tells us what we need to count. | ||
+ | |||
+ | |||
+ | There are <math>\phi(999) = 648</math> numbers less than <math>999</math> and relatively prime to it (<math>\phi</math> is the Euler totient function). We want to count how many of these are even. Note that | ||
+ | <cmath>t \mapsto 999 - t</cmath> | ||
+ | is a 1-1 correspondence between the odd and even numbers less than and relatively prime to <math>999</math>. So our final answer is <math>648/2 = 324</math>, or <math>\boxed{B}</math>. | ||
== See also == | == See also == | ||
{{AMC12 box|year=2006|ab=B|num-b=24|after=Last Question}} | {{AMC12 box|year=2006|ab=B|num-b=24|after=Last Question}} |
Revision as of 19:37, 13 September 2012
This is an empty template page which needs to be filled. You can help us out by finding the needed content and editing it in. Thanks.
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.
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, 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 .
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 |