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 "2019 AMC 10B Problems/Problem 24"

(→‎Solution 1)
(All AMC 10 problem pages should include a solution that doesn't mention logarithms; I'll finish this later)
Line 57: Line 57:
  
 
Solution by mathsuper(丹神)
 
Solution by mathsuper(丹神)
 +
 +
==Solution 2==
 +
 +
The condition where <math>x_m\leq 4+\frac{1}{2^{20}}</math> gives the motivation to make a substitution to change the equilibrium from <math>4</math> to <math>0</math>. We can substitute <math>x_n = y_n + 4</math> to achieve that.
 +
 +
Now, we need to find the smallest value of <math>m</math> such that <math>y_m\leq \frac{1}{2^{20}}</math> given that <math>y_0 = 1</math> and the recursion <math>y_{n+1} = \frac{y_n^2 + 9y_n}{y_n + 10}</math>.
 +
 +
Using wishful thinking, we can simplify the recursion as follows:
 +
 +
<math>y_{n+1} = \frac{y_n^2 + 9y_n + y_n - y_n}{y_n + 10}</math>
 +
 +
<math>y_{n+1} = \frac{y_n(y_n + 10) - y_n}{y_n + 10}</math>
 +
 +
<math>y_{n+1} = y_n - \frac{y_n}{y_n + 10}</math>
 +
 +
<math>y_{n+1} = y_n(1 - \frac{1}{y_n + 10})</math>
 +
 +
The recursion looks like a geometric sequence with the ratio changing slightly after each term. Notice from the recursion that the <math>y_n</math> sequence is strictly decreasing, so all the terms after <math>y_0</math> will be less than 1. Also, notice that all the terms in sequence will be positive. Both of these can be proven by induction.
 +
 +
With both of those observations in mind, <math>\frac{9}{10} < 1 - \frac{1}{y_n + 10} \leq \frac{10}{11}</math>. Combining this with the fact that the recursion resembles a geometric sequence, we conclude that <math>(\frac{9}{10})^2 < y_n \leq (\frac{10}{11})^2</math>.
 +
 +
Note: Solution is incomplete
  
 
==See Also==
 
==See Also==

Revision as of 18:48, 20 February 2019

The following problem is from both the 2019 AMC 10B #24 and 2019 AMC 12B #22, so both problems redirect to this page.

Problem

Define a sequence recursively by $x_0=5$ and \[x_{n+1}=\frac{x_n^2+5x_n+4}{x_n+6}\] for all nonnegative integers $n.$ Let $m$ be the least positive integer such that \[x_m\leq 4+\frac{1}{2^{20}}.\]In which of the following intervals does $m$ lie?

$\textbf{(A) } [9,26] \qquad\textbf{(B) } [27,80] \qquad\textbf{(C) } [81,242]\qquad\textbf{(D) } [243,728] \qquad\textbf{(E) } [729,\infty)$

Solution 1

We first prove that $x_n > 4$ for all $n \ge 0$, by induction. Observe that \[x_{n+1} - 4 = \frac{x_n^2 + 5x_n + 4 - 4(x_n+6)}{x_n+6} = \frac{(x_n - 4)(x_n+5)}{x_n+6}\] so (since $x_n$ is clearly positive for all $n$, from the initial definition), $x_{n+1} > 4$ if and only if $x_{n} > 4$.

We similarly prove that $x_n$ is decreasing, since \[x_{n+1} - x_n = \frac{x_n^2 + 5x_n + 4 - x_n(x_n+6)}{x_n+6} = \frac{4-x_n}{x_n+6} < 0\]

Now we need to estimate the value of $x_{n+1}-4$, which we can do using the rearranged equation \[x_{n+1} - 4 = (x_n-4)\cdot\frac{x_n + 5}{x_n+6}\] Since $x_n$ is decreasing, $\frac{x_n + 5}{x_n+6}$ is clearly also decreasing, so we have \[\frac{9}{10} < \frac{x_n + 5}{x_n+6} \le \frac{10}{11}\] and \[\frac{9}{10}(x_n-4) < x_{n+1} - 4 \le \frac{10}{11}(x_n-4)\]

This becomes \[\left(\frac{9}{10}\right)^n = \left(\frac{9}{10}\right)^n \left(x_0-4\right) < x_{n} - 4 \le \left(\frac{10}{11}\right)^n \left(x_0-4\right) = \left(\frac{10}{11}\right)^n\] The problem thus reduces to finding the least value of $n$ such that \[\left(\frac{9}{10}\right)^n < x_{n} - 4 \le \frac{1}{2^{20}} \text{ and } \left(\frac{10}{11}\right)^{n-1} > x_{n-1} - 4 > \frac{1}{2^{20}}\]

Taking logarithms, we get $n \ln \frac{9}{10} < -20 \ln 2$ and $(n-1)\ln \frac{10}{11} > -20 \ln 2$, i.e.

\[n > \frac{20\ln 2}{\ln\frac{10}{9}} \text{ and } n-1 < \frac{20\ln 2}{\ln\frac{11}{10}}\]

As approximations, we can use $\ln\frac{10}{9} \approx \frac{1}{9}$, $\ln\frac{11}{10} \approx \frac{1}{10}$, and $\ln 2\approx 0.7$. These allow us to estimate that \[126 < n < 141\] which gives the answer as $\boxed{\textbf{(C) } [81,242]}$.

Solution by mathsuper(丹神)

Solution 2

The condition where $x_m\leq 4+\frac{1}{2^{20}}$ gives the motivation to make a substitution to change the equilibrium from $4$ to $0$. We can substitute $x_n = y_n + 4$ to achieve that.

Now, we need to find the smallest value of $m$ such that $y_m\leq \frac{1}{2^{20}}$ given that $y_0 = 1$ and the recursion $y_{n+1} = \frac{y_n^2 + 9y_n}{y_n + 10}$.

Using wishful thinking, we can simplify the recursion as follows:

$y_{n+1} = \frac{y_n^2 + 9y_n + y_n - y_n}{y_n + 10}$

$y_{n+1} = \frac{y_n(y_n + 10) - y_n}{y_n + 10}$

$y_{n+1} = y_n - \frac{y_n}{y_n + 10}$

$y_{n+1} = y_n(1 - \frac{1}{y_n + 10})$

The recursion looks like a geometric sequence with the ratio changing slightly after each term. Notice from the recursion that the $y_n$ sequence is strictly decreasing, so all the terms after $y_0$ will be less than 1. Also, notice that all the terms in sequence will be positive. Both of these can be proven by induction.

With both of those observations in mind, $\frac{9}{10} < 1 - \frac{1}{y_n + 10} \leq \frac{10}{11}$. Combining this with the fact that the recursion resembles a geometric sequence, we conclude that $(\frac{9}{10})^2 < y_n \leq (\frac{10}{11})^2$.

Note: Solution is incomplete

See Also

2019 AMC 10B (Problems • Answer Key • Resources)
Preceded by
Problem 23 		Followed by
Problem 25
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 10 Problems and Solutions
2019 AMC 12B (Problems • Answer Key • Resources)
Preceded by
Problem 21 		Followed by
Problem 23
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=2019_AMC_10B_Problems/Problem_24&oldid=103644"