Difference between revisions of "2010 AMC 12A Problems/Problem 20"
m (→Solution 3) |
(→Alternative Thinking) |
||
(10 intermediate revisions by 5 users not shown) | |||
Line 25: | Line 25: | ||
− | Hence, we have to find the largest <math>n</math> such that <math>\frac{a_n-1}{n-1}</math> and <math>\frac{b_n-1}{n-1}</math> are both integers. | + | Hence, we have to find the largest <math>n</math> such that <math>\frac{a_n-1}{n-1}</math> and <math>\frac{b_n-1}{n-1}</math> are both integers; equivalently, we want to maximize <math>\gcd(a_n-1, b_n-1)</math>. |
− | The prime factorization of <math>2010</math> is <math>2\cdot{3}\cdot{5}\cdot{67}</math>. We list out all the possible pairs that have a product of <math>2010</math> | + | The prime factorization of <math>2010</math> is <math>2\cdot{3}\cdot{5}\cdot{67}</math>. We list out all the possible pairs that have a product of <math>2010</math>, noting that these are the possible values of <math>(a_n, b_n)</math> and we need <math>a_n \leq b_n</math>: |
<cmath>(2,1005), (3, 670), (5,402), (6,335), (10,201),(15,134),(30,67)</cmath> | <cmath>(2,1005), (3, 670), (5,402), (6,335), (10,201),(15,134),(30,67)</cmath> | ||
Line 46: | Line 46: | ||
Hence <math>n=8</math> is the largest possible <math>n</math>. (There is no need to check <math>n=2</math> anymore.) | Hence <math>n=8</math> is the largest possible <math>n</math>. (There is no need to check <math>n=2</math> anymore.) | ||
− | == | + | ==Alternative Thinking== |
− | + | Since | |
+ | |||
+ | |||
+ | <math>a_n*b_n = 2010,</math> | ||
+ | |||
+ | |||
+ | and | ||
+ | |||
+ | |||
+ | <math>a_n \le b_n</math>, | ||
+ | blue+yellow=green | ||
+ | |||
+ | |||
+ | it follows that | ||
+ | |||
+ | |||
+ | <math>a_n \le \sqrt{2010} \Rightarrow a_n \le 44</math>. | ||
+ | |||
+ | |||
+ | But <math>a_n</math> and <math>b_n</math> are also integers, so <math>a_n</math> must be a factor of <math>2010</math> smaller than <math>44</math>. Notice that <math>2010 = 2*3*5*67</math>. Therefore <math>a_n = 2, 3, 5, 6, 112, 15,</math> or <math>30</math> and <math>b_n = 1005, 670, 402, 335, 201, 134,</math> or <math>67</math>; respectively. | ||
+ | |||
+ | |||
+ | Notice that the term <math>a_m</math> is equivalent to the first term <math>a_1 = 1</math> plus <math>(m-1)</math> times the common difference for that particular arithmetic sequence. Let the common difference of <math>(a_n)</math> be <math>k</math> and the common difference of <math>(b_n)</math> be <math>i</math> (not <math>\sqrt{-1}</math>). Then | ||
+ | |||
+ | |||
+ | <math>a_n</math> (the <math>n</math>th term, not the sequence itself) <math>=1 + k(n-1)</math> | ||
+ | |||
+ | |||
+ | and | ||
+ | |||
+ | |||
+ | <math>b_n = 1 + i(n-1)</math> | ||
+ | |||
+ | |||
+ | Subtracting one from all the possible values listed above for <math>a_n</math> and <math>b_n</math>, we get | ||
+ | |||
+ | |||
+ | <math>k(n-1) = 1, 2, 4, 5, 9, 14, 29</math> | ||
+ | |||
+ | |||
+ | and | ||
+ | |||
+ | |||
+ | <math>i(n-1) = 1004, 669, 401, 334, 200, 133, 66</math> | ||
+ | |||
+ | |||
+ | In order to maximize <math>n</math>, we must maximize <math>n-1</math>. Therefore <math>k</math> and <math>i</math> are [[coprime]] and <math>n-1</math> is the [[Greatest common factor|GCF]] of any corresponding pair. Inspecting all of the pairs, we see that the [[Greatest common factor|GCF]] is always <math>1</math> except for the pair <math>(14, 133),</math> which has a GCF of <math>7</math>. Therefore the maximum value of <math>n</math> is <math>8 \Rightarrow \boxed{\text{C}}</math>. | ||
== See also == | == See also == |
Latest revision as of 15:27, 3 July 2023
Problem
Arithmetic sequences and
have integer terms with
and
for some
. What is the largest possible value of
?
Solution
Solution 1
Since and
have integer terms with
, we can write the terms of each sequence as
where and
(
) are the common differences of each, respectively.
Since
it is easy to see that
.
Hence, we have to find the largest such that
and
are both integers; equivalently, we want to maximize
.
The prime factorization of is
. We list out all the possible pairs that have a product of
, noting that these are the possible values of
and we need
:
and soon find that the largest value is
for the pair
, and so the largest
value is
.
Solution 2
As above, let and
for some
.
Now we get , hence
. Therefore
divides
. And as the second term is greater than the first one, we only have to consider the options
.
For we easily see that for
the right side is less than
and for any other
it is way too large.
For we are looking for
such that
. Note that
must be divisible by
. We can start looking for the solution by trying the possible values for
, and we easily discover that for
we get
, which has a suitable solution
.
Hence is the largest possible
. (There is no need to check
anymore.)
Alternative Thinking
Since
and
,
blue+yellow=green
it follows that
.
But and
are also integers, so
must be a factor of
smaller than
. Notice that
. Therefore
or
and
or
; respectively.
Notice that the term is equivalent to the first term
plus
times the common difference for that particular arithmetic sequence. Let the common difference of
be
and the common difference of
be
(not
). Then
(the
th term, not the sequence itself)
and
Subtracting one from all the possible values listed above for and
, we get
and
In order to maximize , we must maximize
. Therefore
and
are coprime and
is the GCF of any corresponding pair. Inspecting all of the pairs, we see that the GCF is always
except for the pair
which has a GCF of
. Therefore the maximum value of
is
.
See also
2010 AMC 12A (Problems • Answer Key • Resources) | |
Preceded by Problem 19 |
Followed by Problem 21 |
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.