Difference between revisions of "2006 AMC 12B Problems/Problem 25"
m (→Solution) |
(→Solution) |
||
Line 14: | Line 14: | ||
</math> | </math> | ||
− | == Solution == | + | == Solution 1 == |
+ | Define <math>g:= \gcd(999,a_2)</math>; then <math>g\mid a_3</math>, and, by induction, <math>g\mid a_k</math> for all <math>k>0</math>. Since <math>a_{2006}=1</math>, we have <math>g=1</math>, i.e. <math>a_2</math> is in the set, <math>S</math>, of positive integers less than <math>999</math> and relatively prime to <math>999</math>. We have <math>|S|=\varphi(999)=648</math>. Moreover, <math>a_2</math> must be odd, because if <math>a_2</math> is even, then every third term after <math>a_2</math> will be even; in particular, <math>2006\equiv 2\pmod 3</math>, so <math>a_{2006}</math> must be even, which is not the case. The subset of odd integers in <math>S</math> (denoted <math>S_{\textrm{o}}</math>) is in <math>1</math>--<math>1</math> correspondence with the subset of even integers in <math>S</math> via <math>x \mapsto 999 - x</math>; so <math>a_2\in S_{\textrm{o}}</math> with <math>|S_{\textrm{o}}|=324</math>. | ||
+ | |||
+ | We will now show that <math>a_{2006}=1</math> whenever <math>a_2\in S_{\textrm{o}}</math>. Suppose <math>a_2\in S</math> is odd, and define <math>M_i=\max(a_{i}, a_{i+1})</math> and <math>m_i=\min(a_{i}, a_{i+1})</math>. | ||
+ | |||
+ | Since <math>a_{i+1}=M_{i-1}-m_{i-1} \le M_{i-1}</math>, we have <math>M_i \le M_{i-1}</math> for all <math>i>0</math>. In fact, as long as <math>m_{i-1}\neq 0</math>, we have <math>a_{i+1}< M_{i-1}</math> and it follows that <math>M_{i+1} < M_{i-1}</math>. Then <math>M_1=999</math>, <math>M_3\le 998</math>, <math>M_5\le 997</math>, and, in general, <math>M_{2k+1}\le 999-k</math>. This implies that <math>m_k=0</math> for some <math>k< 2000</math>, i.e. <math>a_k=0</math> for some <math>k\le 2000</math>. If <math>a_k=0</math> then <math>a_{k-2}=a_{k-1}=a</math> (say), and it follows that <math>a\mid a_{k-3}</math>, and, by induction, <math>a\mid a_j</math> for all <math>j=1,2,\ldots , k-1</math>. Then <math>a\mid \gcd(999,a_2)=1</math>, so <math>a=1</math>. Therefore, the sub-sequence <math>\{a_i\}_{i\ge k-2}</math> <math>(k\le 2000)</math> will be<cmath>1, 1, 0, 1, 1, 0, \ldots</cmath>In particular, <math>a_{2006}</math> will be either <math>0</math> or <math>1</math>; but since <math>a_2</math> is odd, every third term after <math>a_2</math> will be odd, so <math>a_{2006}</math> must be odd, so it must equal <math>1</math>. We have shown that <math>a_2\in S_{\textrm{o}}</math> implies <math>a_{2006}=1</math>. So our final answer is <math>|S_{\textrm{o}}|=324</math>, or <math>\boxed{\text{B}}</math>. | ||
+ | |||
+ | == Solution 2== | ||
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. | 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. | ||
Revision as of 11:12, 14 June 2022
Contents
Problem
A sequence of non-negative integers is defined by the rule
for
. If
,
and
, how many different values of
are possible?
Solution 1
Define ; then
, and, by induction,
for all
. Since
, we have
, i.e.
is in the set,
, of positive integers less than
and relatively prime to
. We have
. Moreover,
must be odd, because if
is even, then every third term after
will be even; in particular,
, so
must be even, which is not the case. The subset of odd integers in
(denoted
) is in
--
correspondence with the subset of even integers in
via
; so
with
.
We will now show that whenever
. Suppose
is odd, and define
and
.
Since , we have
for all
. In fact, as long as
, we have
and it follows that
. Then
,
,
, and, in general,
. This implies that
for some
, i.e.
for some
. If
then
(say), and it follows that
, and, by induction,
for all
. Then
, so
. Therefore, the sub-sequence
will be
In particular,
will be either
or
; but since
is odd, every third term after
will be odd, so
must be odd, so it must equal
. We have shown that
implies
. So our final answer is
, or
.
Solution 2
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 |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.