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 "2016 AIME II Problems/Problem 9"

(→‎Solution 2)
m (→‎Solution 2 (No trial and error))
 
(8 intermediate revisions by 3 users not shown)
Line 5: Line 5:
 
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 2==
+
== 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>.  
 
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., <math>700 < r^k < 1000</math>. Dividing through by <math>r^2</math> we get <cmath>\frac{700}{r^2} < r^{j} < \frac{1000}{r^2}</cmath>where <math>j=k-2</math>. 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>. Let's make a table:
+
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 }
 
<cmath>\begin{array}[b]{ c c c c c c c c c }
 
r & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\[2ex]
 
r & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\[2ex]
−
\left\lfloor\frac{700}{r^2}\right\rfloor & 175 & 77 & 43 & 28 & 19 & 14 & 10 & 8\\[2ex]
+
i(r) & 9 & 5 & 4 & 4 & 3 & 3 & 3 & 2\\[2ex]
−
\left\lfloor\frac{1000}{r^2}\right\rfloor & 250 & 111 & 63 & 40 & 28 & 20 & 16 & 12
+
j(r) & 10 & 7 & 5 & 5 & 4 & 4 & 4 & 4
 
\end{array} </cmath>
 
\end{array} </cmath>
−
The only admissible <math>r^j</math> values are <math>\{3^4, 9\}</math>.  
+
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.  
−
 
 
−
Since <math>100=c_{j+1}=r^j+jd+1</math>, we must have <math>j\mid 99-r^j</math>.
 
−
 
 
−
Note that <math>99-3^4=18</math>, which is not a multiple of <math>4</math>, which leaves <math>r^j=9^1</math>. We check: <math>a_j=9</math> implies <math>b_j=91</math>, i.e. <math>d=90</math>, so <math>b_{j+2}=271</math> and <math>a_{j+2}=729</math> and <math>c_{j+2}=1000</math>! So it works! Then <math>c_{j+1}=9^2+181=262</math>.
 
−
 
 
  
 +
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>.
  
 
== Solution 3==
 
== Solution 3==
Line 33: Line 29:
 
Solution by rocketscience
 
Solution by rocketscience
  
−
== Solution 3 (More Robust Bash) ==
+
== Solution 4 (More Robust Bash) ==
  
 
The reason for bashing in this context can also be justified by the fact 100 isn't very big.  
 
The reason for bashing in this context can also be justified by the fact 100 isn't very big.  
Line 49: Line 45:
 
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.
 
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.
  
−
-Dankster42
+
==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 ==
 
== See also ==
 
{{AIME box|year=2016|n=II|num-b=8|num-a=10}}
 
{{AIME box|year=2016|n=II|num-b=8|num-a=10}}
 
{{MAA Notice}}
 
{{MAA Notice}}

Latest revision as of 00:18, 2 February 2023

Problem

The sequences of positive integers $1,a_2, a_3,...$ and $1,b_2, b_3,...$ are an increasing arithmetic sequence and an increasing geometric sequence, respectively. Let $c_n=a_n+b_n$. There is an integer $k$ such that $c_{k-1}=100$ and $c_{k+1}=1000$. Find $c_k$.

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 $b_2$. When we get to $b_2=9$ and $a_2=91$, we have $a_4=271$ and $b_4=729$, which works, therefore, the answer is $b_3+a_3=81+181=\boxed{262}$.

Solution 2 (Some trial and error)

We have $a_k=r^{k-1}$ and $b_k=(k-1)d$. First, $b_{k-1}<c_{k-1}=100$ implies $d<100$, so $b_{k+1}<300$.

It follows that $a_{k+1}=1000-b_{k+1}>700$, i.e., \[700 < r^k < 1000.\] Moreover, since $k$ is atleast $3$ we get $r^3\le r^k <1000$, i.e. $r<10$. For every value of $r$ in this range, define $i(r) = \max \{x : r^x < 700\}$, and define $j(r) = \min \{x : r^x > 1000\}$. We are looking for values of $r$ such that $j(r) -i(r)>1$. Let's make a table: \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} The only admissible values for $r^k$ are $\{3^6, 9^3\}$. However, since $100=c_{k-1}=r^{k-2}+(k-2)d+1$, we must have $(k-2)\mid 99-r^{k-2}$. This does not hold for $r^k=3^6$ because $4$ does not divide $99-3^4=18$. This leaves $r^k=9^3$ as the only option.

For $r=9$ and $k=3$, we check: $a_{k-1}= a_2 = r =9$ implies $b_{k-1}= b_2 = 91$, i.e. $d=90$. Then $a_{k+1}=a_4 = r^3 = 729$ and $b_{k+1}=b_4 = 1+3d = 271$ and $c_{k+1}=c_4=a_4+b_4 = 729+271=1000$; so it works! Then $c_k = c_3 = 9^2+181 = 262$.

Solution 3

Using the same reasoning ($100$ isn't very big), we can guess which terms will work. The first case is $k=3$, so we assume the second and fourth terms of $c$ are $100$ and $1000$. We let $r$ be the common ratio of the geometric sequence and write the arithmetic relationships in terms of $r$.

The common difference is $100-r - 1$, and so we can equate: $2(99-r)+100-r=1000-r^3$. Moving all the terms to one side and the constants to the other yields

$r^3-3r = 702$, or $r(r^2-3) = 702$. Simply listing out the factors of $702$ shows that the only factor $3$ less than a square that works is $78$. Thus $r=9$ and we solve from there to get $\boxed{262}$.

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 $a$, and the common ratio for the geometric sequence be $b$. The sequences are now $1, a+1, 2a+1, \ldots$, and $1, b, b^2, \ldots$. We can now write the given two equations as the following:

$1+(k-2)a+b^{k-2} = 100$

$1+ka+b^k = 1000$

Take the difference between the two equations to get $2a+(b^2-1)b^{k-2} = 900$. Since 900 is divisible by 4, we can tell $a$ is even and $b$ is odd. Let $a=2m$, $b=2n+1$, where $m$ and $n$ are positive integers. Substitute variables and divide by 4 to get:

$m+(n+1)(n)(2n+1)^{k-2} = 225$

Because very small integers for $n$ yield very big results, we can bash through all cases of $n$. Here, we set an upper bound for $n$ by setting $k$ as 3. After trying values, we find that $n\leq 4$, so $b=9, 7, 5, 3$. Testing out $b=9$ yields the correct answer of $\boxed{262}$. Note that even if this answer were associated with another b value like $b=3$, the value of $k$ can still only be 3 for all of the cases.

Solution 5 (Casework)

Let $a_n$ and $b_n$ be in the form of \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} Case $1.\hspace{10mm} k = 3\hspace{5mm} (c_1=2 \implies k > 2).$ \[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}.\] Case $2. \hspace{10mm} k = 4.$ \[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.\] Case $3. \hspace{10mm} k \ge 5.\hspace{3mm} b^5 < 1000 \implies b = \{2,3\}.$

Case $3.1.\hspace{10mm} b = 2.$ \[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.\] Case $3.2.\hspace{10mm} b = 3.$ \[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.\] 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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2016_AIME_II_Problems/Problem_9&oldid=188498"