Difference between revisions of "2016 AIME II Problems/Problem 9"
(→Solution) |
m (→Solution 2 (No trial and error)) |
||
(22 intermediate revisions by 8 users not shown) | |||
Line 1: | Line 1: | ||
+ | ==Problem== | ||
The sequences of positive integers <math>1,a_2, a_3,...</math> and <math>1,b_2, b_3,...</math> are an increasing arithmetic sequence and an increasing geometric sequence, respectively. Let <math>c_n=a_n+b_n</math>. There is an integer <math>k</math> such that <math>c_{k-1}=100</math> and <math>c_{k+1}=1000</math>. Find <math>c_k</math>. | The sequences of positive integers <math>1,a_2, a_3,...</math> and <math>1,b_2, b_3,...</math> are an increasing arithmetic sequence and an increasing geometric sequence, respectively. Let <math>c_n=a_n+b_n</math>. There is an integer <math>k</math> such that <math>c_{k-1}=100</math> and <math>c_{k+1}=1000</math>. Find <math>c_k</math>. | ||
− | ==Solution== | + | ==Solution 1== |
Since all the terms of the sequences are integers, and 100 isn't very big, we should just try out the possibilities for <math>b_2</math>. When we get to <math>b_2=9</math> and <math>a_2=91</math>, we have <math>a_4=271</math> and <math>b_4=729</math>, which works, therefore, the answer is <math>b_3+a_3=81+181=\boxed{262}</math>. | Since all the terms of the sequences are integers, and 100 isn't very big, we should just try out the possibilities for <math>b_2</math>. When we get to <math>b_2=9</math> and <math>a_2=91</math>, we have <math>a_4=271</math> and <math>b_4=729</math>, which works, therefore, the answer is <math>b_3+a_3=81+181=\boxed{262}</math>. | ||
− | Solution | + | == Solution 2 (Some trial and error)== |
− | == | + | We have <math>a_k=r^{k-1}</math> and <math>b_k=(k-1)d</math>. First, <math>b_{k-1}<c_{k-1}=100</math> implies <math>d<100</math>, so <math>b_{k+1}<300</math>. |
− | + | It follows that <math>a_{k+1}=1000-b_{k+1}>700</math>, i.e., <cmath>700 < r^k < 1000.</cmath> Moreover, since <math>k</math> is atleast <math>3</math> we get <math>r^3\le r^k <1000</math>, i.e. <math>r<10</math>. For every value of <math>r</math> in this range, define <math>i(r) = \max \{x : r^x < 700\}</math>, and define <math>j(r) = \min \{x : r^x > 1000\}</math>. We are looking for values of <math>r</math> such that <math>j(r) -i(r)>1</math>. Let's make a table: | |
+ | <cmath>\begin{array}[b]{ c c c c c c c c c } | ||
+ | r & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\[2ex] | ||
+ | i(r) & 9 & 5 & 4 & 4 & 3 & 3 & 3 & 2\\[2ex] | ||
+ | j(r) & 10 & 7 & 5 & 5 & 4 & 4 & 4 & 4 | ||
+ | \end{array} </cmath> | ||
+ | The only admissible values for <math>r^k</math> are <math>\{3^6, 9^3\}</math>. However, since <math>100=c_{k-1}=r^{k-2}+(k-2)d+1</math>, we must have <math>(k-2)\mid 99-r^{k-2}</math>. This does not hold for <math>r^k=3^6</math> because <math>4</math> does not divide <math>99-3^4=18</math>. This leaves <math>r^k=9^3</math> as the only option. | ||
− | + | For <math>r=9</math> and <math>k=3</math>, we check: <math>a_{k-1}= a_2 = r =9</math> implies <math>b_{k-1}= b_2 = 91</math>, i.e. <math>d=90</math>. Then <math>a_{k+1}=a_4 = r^3 = 729</math> and <math>b_{k+1}=b_4 = 1+3d = 271</math> and <math>c_{k+1}=c_4=a_4+b_4 = 729+271=1000</math>; so it works! Then <math>c_k = c_3 = 9^2+181 = 262</math>. | |
− | <math>r^ | + | == Solution 3== |
+ | |||
+ | Using the same reasoning (<math>100</math> isn't very big), we can guess which terms will work. The first case is <math>k=3</math>, so we assume the second and fourth terms of <math>c</math> are <math>100</math> and <math>1000</math>. We let <math>r</math> be the common ratio of the geometric sequence and write the arithmetic relationships in terms of <math>r</math>. | ||
+ | |||
+ | The common difference is <math>100-r - 1</math>, and so we can equate: <math>2(99-r)+100-r=1000-r^3</math>. Moving all the terms to one side and the constants to the other yields | ||
+ | |||
+ | <math>r^3-3r = 702</math>, or <math>r(r^2-3) = 702</math>. Simply listing out the factors of <math>702</math> shows that the only factor <math>3</math> less than a square that works is <math>78</math>. Thus <math>r=9</math> and we solve from there to get <math>\boxed{262}</math>. | ||
+ | |||
+ | Solution by rocketscience | ||
+ | |||
+ | == Solution 4 (More Robust Bash) == | ||
+ | |||
+ | The reason for bashing in this context can also be justified by the fact 100 isn't very big. | ||
+ | |||
+ | Let the common difference for the arithmetic sequence be <math>a</math>, and the common ratio for the geometric sequence be <math>b</math>. The sequences are now <math>1, a+1, 2a+1, \ldots</math>, and <math>1, b, b^2, \ldots</math>. We can now write the given two equations as the following: | ||
+ | |||
+ | <math>1+(k-2)a+b^{k-2} = 100</math> | ||
+ | |||
+ | <math>1+ka+b^k = 1000</math> | ||
+ | |||
+ | Take the difference between the two equations to get <math>2a+(b^2-1)b^{k-2} = 900</math>. Since 900 is divisible by 4, we can tell <math>a</math> is even and <math>b</math> is odd. Let <math>a=2m</math>, <math>b=2n+1</math>, where <math>m</math> and <math>n</math> are positive integers. Substitute variables and divide by 4 to get: | ||
+ | |||
+ | <math>m+(n+1)(n)(2n+1)^{k-2} = 225</math> | ||
+ | |||
+ | Because very small integers for <math>n</math> yield very big results, we can bash through all cases of <math>n</math>. Here, we set an upper bound for <math>n</math> by setting <math>k</math> as 3. After trying values, we find that <math>n\leq 4</math>, so <math>b=9, 7, 5, 3</math>. Testing out <math>b=9</math> yields the correct answer of <math>\boxed{262}</math>. Note that even if this answer were associated with another b value like <math>b=3</math>, the value of <math>k</math> can still only be 3 for all of the cases. | ||
+ | |||
+ | ==Solution 5 (Casework)== | ||
+ | Let <math>a_n</math> and <math>b_n </math> be in the form of | ||
+ | <cmath>\begin{array}[b]{ c c c c c c c } | ||
+ | n & 1 & 2 & 3 & 4 & 5 & 6 \\[2ex] | ||
+ | a_n & 1 & a+1 & 2a+1 & 3a+1 & 4a+1 & 5a+1 \\[2ex] | ||
+ | b_n & 1 & b & b^2 & b^3 & b^4 & b^5 \\[2ex] | ||
+ | c_n & 2 & b+a+1 & b^2+2a+1 & b^3+3a+1 & b^4+4a+1 & b^5+5a+1 | ||
+ | \end{array} </cmath> | ||
+ | Case <math>1.\hspace{10mm} k = 3\hspace{5mm} (c_1=2 \implies k > 2).</math> | ||
+ | <cmath>c_2 = a+1 + b = 100, c_4 = 3a+1 + b^3 = 1000 \implies b^3 -3b -2 = 1000-300 \implies b^3 - 3b = 702 \implies b = 9, a=90, c_3 = \boxed {262}.</cmath> | ||
+ | Case <math>2. \hspace{10mm} k = 4.</math> | ||
+ | <cmath>c_3 = 2a+1 + b^2 = 100, c_5 = 4a+1 + b^4 = 1000 \implies b^4 -2b^2 -1 = 1000-200 \implies b^4 - 2b^2 = 801 \implies \O.</cmath> | ||
+ | Case <math>3. \hspace{10mm} k \ge 5.\hspace{3mm} b^5 < 1000 \implies b = \{2,3\}.</math> | ||
+ | |||
+ | Case <math>3.1.\hspace{10mm} b = 2.</math> | ||
+ | <cmath>c_{k-1} = 2^{k-2} + (k-2) a + 1 = 100, c_{k+1} = 2^k + ka + 1 = 1000\implies a = 450-3\cdot 2^{k-3} \implies 2^k +450k -3k\cdot 2^{k-3} + 1 = 1000 \implies \O.</cmath> | ||
+ | Case <math>3.2.\hspace{10mm} b = 3.</math> | ||
+ | <cmath>c_{k-1} = 3^{k-2} + (k-2) a + 1 = 100, c_{k+1} = 3^k + ka + 1 = 1000\implies a = 450-4\cdot 3^{k-2} \implies 3^{k-4}(9-4k) +50k = 3\cdot 37 \implies \O.</cmath> | ||
+ | '''vladimir.shelomovskii@gmail.com, vvsss''' | ||
+ | |||
+ | == See also == | ||
+ | {{AIME box|year=2016|n=II|num-b=8|num-a=10}} | ||
+ | {{MAA Notice}} |
Latest revision as of 01:18, 2 February 2023
Contents
Problem
The sequences of positive integers and
are an increasing arithmetic sequence and an increasing geometric sequence, respectively. Let
. There is an integer
such that
and
. Find
.
Solution 1
Since all the terms of the sequences are integers, and 100 isn't very big, we should just try out the possibilities for . When we get to
and
, we have
and
, which works, therefore, the answer is
.
Solution 2 (Some trial and error)
We have and
. First,
implies
, so
.
It follows that , i.e.,
Moreover, since
is atleast
we get
, i.e.
. For every value of
in this range, define
, and define
. We are looking for values of
such that
. Let's make a table:
The only admissible values for
are
. However, since
, we must have
. This does not hold for
because
does not divide
. This leaves
as the only option.
For and
, we check:
implies
, i.e.
. Then
and
and
; so it works! Then
.
Solution 3
Using the same reasoning ( isn't very big), we can guess which terms will work. The first case is
, so we assume the second and fourth terms of
are
and
. We let
be the common ratio of the geometric sequence and write the arithmetic relationships in terms of
.
The common difference is , and so we can equate:
. Moving all the terms to one side and the constants to the other yields
, or
. Simply listing out the factors of
shows that the only factor
less than a square that works is
. Thus
and we solve from there to get
.
Solution by rocketscience
Solution 4 (More Robust Bash)
The reason for bashing in this context can also be justified by the fact 100 isn't very big.
Let the common difference for the arithmetic sequence be , and the common ratio for the geometric sequence be
. The sequences are now
, and
. We can now write the given two equations as the following:
Take the difference between the two equations to get . Since 900 is divisible by 4, we can tell
is even and
is odd. Let
,
, where
and
are positive integers. Substitute variables and divide by 4 to get:
Because very small integers for yield very big results, we can bash through all cases of
. Here, we set an upper bound for
by setting
as 3. After trying values, we find that
, so
. Testing out
yields the correct answer of
. Note that even if this answer were associated with another b value like
, the value of
can still only be 3 for all of the cases.
Solution 5 (Casework)
Let and
be in the form of
Case
Case
Case
Case
Case
vladimir.shelomovskii@gmail.com, vvsss
See also
2016 AIME II (Problems • Answer Key • Resources) | ||
Preceded by Problem 8 |
Followed by Problem 10 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All AIME Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.