Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2006 AMC 12B Problems/Problem 25"
(solution 2)
 
(22 intermediate revisions by 11 users not shown)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
 +
A sequence <math>a_1,a_2,\dots</math> of non-negative integers is defined by the rule <math>a_{n+2}=|a_{n+1}-a_n|</math> for <math>n\geq 1</math>. If <math>a_1=999</math>, <math>a_2<999</math> and <math>a_{2006}=1</math>, how many different values of <math>a_2</math> are possible?
  
−
== Solution ==
+
<math>
 +
\mathrm{(A)}\ 165
 +
\qquad
 +
\mathrm{(B)}\ 324
 +
\qquad
 +
\mathrm{(C)}\ 495
 +
\qquad
 +
\mathrm{(D)}\ 499
 +
\qquad
 +
\mathrm{(E)}\ 660
 +
</math>
 +
 
 +
== Solution 1==
 +
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. (Also, <math>a_{2006}</math> cannot be 1 in this case since <math>d</math> does not divide <math>1</math>, so we do not care about these <math>a_2</math> at all.)
 +
 
 +
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 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
 +
<cmath>\max(a_1, a_2) > \max(a_3, a_4) > \cdots > \max(a_{1999}, a_{2000})  > 0,</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> (since if <math>(a_n)</math> completes at <math>i</math>, then <math>a_k</math> must be <math>0</math> or <math>1</math> for all <math>k \geq i</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 odd. 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{\text{B}}</math>.
 +
 
 +
==Solution 2 (estimation)==
 +
As in Solution 1, we show that <math>a_2</math> must be odd. We notice that, after experimentation, all numbers eventually end up in a sequence <math>1,1,0,1,1,0,\ldots</math>, which points to the assumption that every <math>2</math> out of <math>3</math> values for <math>a_2</math> work due to residue classes. Combining this with an estimated 50-50 chance that these values are either odd or even, since <math>999</math> values are nonnegative integers less than <math>999</math>, we can estimate that there are about <math>999\cdot\frac{2}{3}\cdot\frac{1}{2}=333</math> different values of <math>a_2</math> that work. The closest answer choice by far is <math>\boxed{\textbf{(B) }324}</math>.
 +
 
 +
~eevee9406
  
 
== See also ==
 
== See also ==
−
* [[2006 AMC 12B Problems]]
+
{{AMC12 box|year=2006|ab=B|num-b=24|after=Last Question}}
 +
{{MAA Notice}}

Latest revision as of 22:32, 9 November 2024

Problem

A sequence $a_1,a_2,\dots$ of non-negative integers is defined by the rule $a_{n+2}=|a_{n+1}-a_n|$ for $n\geq 1$. If $a_1=999$, $a_2<999$ and $a_{2006}=1$, how many different values of $a_2$ are possible?

$\mathrm{(A)}\ 165 \qquad \mathrm{(B)}\ 324 \qquad \mathrm{(C)}\ 495 \qquad \mathrm{(D)}\ 499 \qquad \mathrm{(E)}\ 660$

Solution 1

We say the sequence $(a_n)$ completes at $i$ if $i$ is the minimal positive integer such that $a_i = a_{i + 1} = 1$. Otherwise, we say $(a_n)$ does not complete.


Note that if $d = \gcd(999, a_2) \neq 1$, then $d|a_n$ for all $n \geq 1$, and $d$ does not divide $1$, so if $\gcd(999, a_2) \neq 1$, then $(a_n)$ does not complete. (Also, $a_{2006}$ cannot be 1 in this case since $d$ does not divide $1$, so we do not care about these $a_2$ at all.)

From now on, suppose $\gcd(999, a_2) = 1$.


We will now show that $(a_n)$ completes at $i$ for some $i \leq 2006$. We will do this with 3 lemmas.


Lemma: If $a_j \neq a_{j + 1}$, and neither value is $0$, then $\max(a_j, a_{j + 1}) > \max(a_{j + 2}, a_{j + 3})$.

Proof: There are 2 cases to consider.

If $a_j > a_{j + 1}$, then $a_{j + 2} = a_j - a_{j + 1}$, and $a_{j + 3} = |a_j - 2a_{j + 1}|$. So $a_j > a_{j + 2}$ and $a_j > a_{j + 3}$.

If $a_j < a_{j + 1}$, then $a_{j + 2} = a_{j + 1} - a_j$, and $a_{j + 3} = a_j$. So $a_{j + 1} > a_{j + 2}$ and $a_{j + 1} > a_{j + 3}$.

In both cases, $\max(a_j, a_{j + 1}) > \max(a_{j + 2}, a_{j + 3})$, as desired.

Lemma: If $a_i = a_{i + 1}$, then $a_i = 1$. Moreover, if instead we have $a_i = 0$ for some $i > 2$, then $a_{i - 1} = a_{i - 2} = 1$.

Proof: By the way $(a_n)$ is constructed in the problem statement, having two equal consecutive terms $a_i = a_{i + 1}$ implies that $a_i$ divides every term in the sequence. So $a_i | 999$ and $a_i | a_2$, so $a_i | \gcd(999, a_2) = 1$, so $a_i = 1$. For the proof of the second result, note that if $a_i = 0$, then $a_{i - 1} = a_{i - 2}$, so by the first result we just proved, $a_{i - 2} = a_{i - 1} = 1$.

Lemma: $(a_n)$ completes at $i$ for some $i \leq 2000$.

Proof: Suppose $(a_n)$ completed at some $i > 2000$ or not at all. Then by the second lemma and the fact that neither $999$ nor $a_2$ are $0$, none of the pairs $(a_1, a_2), ..., (a_{1999}, a_{2000})$ can have a $0$ or be equal to $(1, 1)$. So the first lemma implies \[\max(a_1, a_2) > \max(a_3, a_4) > \cdots > \max(a_{1999}, a_{2000}) > 0,\] so $999 = \max(a_1, a_2) \geq 1000$, a contradiction. Hence $(a_n)$ completes at $i$ for some $i \leq 2000$.


Now we're ready to find exactly which values of $a_2$ we want to count.

Let's keep in mind that $2006 \equiv 2 \pmod 3$ and that $a_1 = 999$ is odd. We have two cases to consider.


Case 1: If $a_2$ is odd, then $a_3$ is even, so $a_4$ is odd, so $a_5$ is odd, so $a_6$ is even, and this pattern must repeat every three terms because of the recursive definition of $(a_n)$, so the terms of $(a_n)$ reduced modulo 2 are \[1, 1, 0, 1, 1, 0, ...,\] so $a_{2006}$ is odd and hence $1$ (since if $(a_n)$ completes at $i$, then $a_k$ must be $0$ or $1$ for all $k \geq i$).

Case 2: If $a_2$ is even, then $a_3$ is odd, so $a_4$ is odd, so $a_5$ is even, so $a_6$ is odd, and this pattern must repeat every three terms, so the terms of $(a_n)$ reduced modulo 2 are \[1, 0, 1, 1, 0, 1, ...,\] so $a_{2006}$ is even, and hence $0$.


We have found that $a_{2006} = 1$ is true precisely when $\gcd(999, a_2) = 1$ and $a_2$ is odd. This tells us what we need to count.


There are $\phi(999) = 648$ numbers less than $999$ and relatively prime to it ($\phi$ is the Euler totient function). We want to count how many of these are odd. Note that \[t \mapsto 999 - t\] is a 1-1 correspondence between the odd and even numbers less than and relatively prime to $999$. So our final answer is $648/2 = 324$, or $\boxed{\text{B}}$.

Solution 2 (estimation)

As in Solution 1, we show that $a_2$ must be odd. We notice that, after experimentation, all numbers eventually end up in a sequence $1,1,0,1,1,0,\ldots$, which points to the assumption that every $2$ out of $3$ values for $a_2$ work due to residue classes. Combining this with an estimated 50-50 chance that these values are either odd or even, since $999$ values are nonnegative integers less than $999$, we can estimate that there are about $999\cdot\frac{2}{3}\cdot\frac{1}{2}=333$ different values of $a_2$ that work. The closest answer choice by far is $\boxed{\textbf{(B) }324}$.

~eevee9406

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

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2006_AMC_12B_Problems/Problem_25&oldid=232921"