Difference between revisions of "2019 AMC 10B Problems/Problem 24"

m (Fixed a typo and removed an irrelevant attribution)
(Solution 1)
(15 intermediate revisions by 11 users not shown)
Line 4: Line 4:
  
 
Define a sequence recursively by <math>x_0=5</math> and <cmath>x_{n+1}=\frac{x_n^2+5x_n+4}{x_n+6}</cmath> for all nonnegative integers <math>n.</math> Let <math>m</math> be the least positive integer such that
 
Define a sequence recursively by <math>x_0=5</math> and <cmath>x_{n+1}=\frac{x_n^2+5x_n+4}{x_n+6}</cmath> for all nonnegative integers <math>n.</math> Let <math>m</math> be the least positive integer such that
<cmath>x_m\leq 4+\frac{1}{2^{20}}.</cmath>In which of the following intervals does <math>m</math> lie?
+
 
 +
<cmath>x_m\leq 4+\frac{1}{2^{20}}.</cmath>
 +
 
 +
In which of the following intervals does <math>m</math> lie?
  
 
<math>\textbf{(A) } [9,26] \qquad\textbf{(B) } [27,80] \qquad\textbf{(C) } [81,242]\qquad\textbf{(D) } [243,728] \qquad\textbf{(E) } [729,\infty)</math>
 
<math>\textbf{(A) } [9,26] \qquad\textbf{(B) } [27,80] \qquad\textbf{(C) } [81,242]\qquad\textbf{(D) } [243,728] \qquad\textbf{(E) } [729,\infty)</math>
Line 11: Line 14:
 
We first prove that <math>x_n > 4</math> for all <math>n \ge 0</math>, by induction. Observe that
 
We first prove that <math>x_n > 4</math> for all <math>n \ge 0</math>, by induction. Observe that
 
<cmath>
 
<cmath>
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}
+
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}.
 
</cmath>
 
</cmath>
 
so (since <math>x_n</math> is clearly positive for all <math>n</math>, from the initial definition), <math>x_{n+1} > 4</math> if and only if <math>x_{n} > 4</math>.
 
so (since <math>x_n</math> is clearly positive for all <math>n</math>, from the initial definition), <math>x_{n+1} > 4</math> if and only if <math>x_{n} > 4</math>.
  
We similarly prove that <math>x_n</math> is decreasing, since
+
We similarly prove that <math>x_n</math> is decreasing:
 
<cmath>
 
<cmath>
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
+
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.
 
</cmath>
 
</cmath>
  
Now we need to estimate the value of <math>x_{n+1}-4</math>, which we can do using the rearranged equation
+
Now we need to estimate the value of <math>x_{n+1}-4</math>, which we can do using the rearranged equation:
 
<cmath>
 
<cmath>
x_{n+1} - 4 = (x_n-4)\cdot\frac{x_n + 5}{x_n+6}  
+
x_{n+1} - 4 = (x_n-4)\cdot\frac{x_n + 5}{x_n+6}.
 
</cmath>
 
</cmath>
Since <math>x_n</math> is decreasing, <math>\frac{x_n + 5}{x_n+6}</math> is clearly also decreasing, so we have
+
Since <math>x_n</math> is decreasing, <math>\frac{x_n + 5}{x_n+6}</math> is also decreasing, so we have
 
<cmath>
 
<cmath>
 
\frac{9}{10} < \frac{x_n + 5}{x_n+6} \le \frac{10}{11}
 
\frac{9}{10} < \frac{x_n + 5}{x_n+6} \le \frac{10}{11}
Line 30: Line 33:
 
and
 
and
 
<cmath>
 
<cmath>
\frac{9}{10}(x_n-4) < x_{n+1} - 4 \le \frac{10}{11}(x_n-4)
+
\frac{9}{10}(x_n-4) < x_{n+1} - 4 \le \frac{10}{11}(x_n-4).
 
</cmath>
 
</cmath>
  
 
This becomes
 
This becomes
 
<cmath>
 
<cmath>
\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
+
\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.
 
</cmath>
 
</cmath>
 
The problem thus reduces to finding the least value of <math>n</math> such that
 
The problem thus reduces to finding the least value of <math>n</math> such that
 
<cmath>
 
<cmath>
 
\left(\frac{9}{10}\right)^n < x_{n} - 4 \le \frac{1}{2^{20}} \text{  and  }  
 
\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}}
+
\left(\frac{10}{11}\right)^{n-1} > x_{n-1} - 4 > \frac{1}{2^{20}}.
 
</cmath>
 
</cmath>
  
Line 48: Line 51:
 
<cmath>
 
<cmath>
 
n > \frac{20\ln 2}{\ln\frac{10}{9}} \text{  and  }  n-1 < \frac{20\ln 2}{\ln\frac{11}{10}}
 
n > \frac{20\ln 2}{\ln\frac{10}{9}} \text{  and  }  n-1 < \frac{20\ln 2}{\ln\frac{11}{10}}
</cmath>
+
.</cmath>
  
As approximations, we can use <math>\ln\frac{10}{9} \approx \frac{1}{9}</math>, <math>\ln\frac{11}{10} \approx \frac{1}{10}</math>, and <math>\ln 2\approx 0.7</math>. These allow us to estimate that
+
As approximations, we can use <math>\ln\frac{10}{9} \approx \frac{1}{9}</math>, <math>\ln\frac{11}{10} \approx \frac{1}{10}</math>, and <math>\ln 2\approx 0.7</math>. These approximations allow us to estimate
 
<cmath>
 
<cmath>
             126 < n < 141
+
             126 < n < 141,
 
</cmath>
 
</cmath>
which gives the answer as <math>\boxed{\textbf{(C) } [81,242]}</math>.
+
which gives <math>\boxed{\textbf{(C) } [81,242]}</math>.
 +
 
 +
==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>.
 +
 
 +
 
 +
 
 +
Factoring the recursion <math>x_{n+1} = \frac{x_n^2 + 5x_n+4}{x_n + 6}</math>, we get:
 +
 
 +
<math>x_{n+1}=\dfrac{(x_n + 4)(x_n + 1)}{x_n + 6} \Rightarrow y_{n+1}+4=\dfrac{(y_n+8)(y_n+5)}{y_n+10}</math>
 +
 
 +
<math>y_{n+1}+4=\dfrac{y_n^2+13y_n+40}{y_n+10} = \dfrac{y_n^2+9y_n +(4y_n+40)}{y_n+10}</math>
 +
 
 +
<math>y_{n+1}+4=\dfrac{y_n^2+9y_n}{y_n+10} + 4</math>
 +
 
 +
<math>y_{n+1}=\dfrac{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\left(1 - \frac{1}{y_n + 10}\right)</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>\left(\frac{9}{10}\right)^n < y_n \leq \left(\frac{10}{11}\right)^n.</math>
 +
 
 +
<math>\frac{9}{10}</math> is approximately equal to <math>\frac{10}{11}</math> and the ranges that the answer choices give us are generous, so we should use either <math>\frac{9}{10}</math> or <math>\frac{10}{11}</math> to find a rough estimate for <math>m</math>.
 +
 
 +
 
 +
Since <math>\dfrac{1}{2}=0.5</math>, that means <math>\frac{1}{\sqrt{2}}=2^{-\frac{1}{2}} \approx 0.7</math>. Additionally, <math>\left(\frac{9}{10}\right)^3=0.729</math>
 +
 
 +
 
 +
Therefore, we can estimate that <math>2^{-\frac{1}{2}} < y_3</math>.
 +
 
 +
Raising both sides to the 40th power, we get <math>2^{-20} < (y_3)^{40}</math>
 +
 
 +
But <math>y_3 = (y_0)^3</math>, so <math>2^{-20} < (y_0)^{120}</math> and therefore, <math>2^{-20} < y_{120}</math>.
 +
 
 +
This tells us that <math>m</math> is somewhere around 120, so our answer is <math>\boxed{\textbf{(C) } [81,242]}</math>.
 +
 
 +
==Solution 3==
 +
Since the choices are rather wide ranges, we can use approximation to make it easier. Notice that
 +
<cmath>x_{n+1} - x_n = \frac{4-x_n}{x_n+6}</cmath>
 +
And <math>x_0 =5</math>, we know that <math>x_n</math> is a declining sequence, and as it get close to 4 its decline will slow, never falling below 4. So we'll use 4 to approximate <math>x_n</math> in the denominator so that we have a solvable difference equation:
 +
<cmath> x_{n+1} - x_n = \frac{4-x_n}{10}</cmath>
 +
<cmath>x_{n+1} = \frac{9}{10}x_n + \frac{2}{5}</cmath>
 +
Solve it with <math>x_0 = 5</math>, we have
 +
<cmath>x_n = 4 + (\frac{9}{10})^n</cmath>
 +
Now we wish to find <math>n</math> so that
 +
<cmath> (\frac{9}{10})^n \approx \frac{1}{2^{20}}</cmath>
 +
<cmath> n \approx \frac{\log{2^{20}}}{\log{10}-\log9} \approx \frac{20*0.3}{0.05} = 120</cmath>
 +
Since 120 is safely within the range of [81,242], we have the answer.
 +
<math>\boxed{\textbf{(C) } [81,242]}</math>.
 +
 
 +
-Mathdummy
 +
 
 +
 
 +
==Video Solution==
 +
 
 +
https://www.youtube.com/watch?v=toHqTtcCcJQ
 +
~MathProblemSolvingSkills.com
 +
 
 +
 
 +
==Video Solution==
 +
 
 +
Video Solution: https://www.youtube.com/watch?v=Ok7bYOdiF6M
 +
 
 +
==Aside==
 +
The actual value of <math>m</math> is <math>m=133</math>.
  
 
==See Also==
 
==See Also==

Revision as of 11:24, 3 November 2022

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: \[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 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 approximations allow us to estimate \[126 < n < 141,\] which gives $\boxed{\textbf{(C) } [81,242]}$.

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$.


Factoring the recursion $x_{n+1} = \frac{x_n^2 + 5x_n+4}{x_n + 6}$, we get:

$x_{n+1}=\dfrac{(x_n + 4)(x_n + 1)}{x_n + 6} \Rightarrow y_{n+1}+4=\dfrac{(y_n+8)(y_n+5)}{y_n+10}$

$y_{n+1}+4=\dfrac{y_n^2+13y_n+40}{y_n+10} = \dfrac{y_n^2+9y_n +(4y_n+40)}{y_n+10}$

$y_{n+1}+4=\dfrac{y_n^2+9y_n}{y_n+10} + 4$

$y_{n+1}=\dfrac{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\left(1 - \frac{1}{y_n + 10}\right)$.


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 $\left(\frac{9}{10}\right)^n < y_n \leq \left(\frac{10}{11}\right)^n.$

$\frac{9}{10}$ is approximately equal to $\frac{10}{11}$ and the ranges that the answer choices give us are generous, so we should use either $\frac{9}{10}$ or $\frac{10}{11}$ to find a rough estimate for $m$.


Since $\dfrac{1}{2}=0.5$, that means $\frac{1}{\sqrt{2}}=2^{-\frac{1}{2}} \approx 0.7$. Additionally, $\left(\frac{9}{10}\right)^3=0.729$


Therefore, we can estimate that $2^{-\frac{1}{2}} < y_3$.

Raising both sides to the 40th power, we get $2^{-20} < (y_3)^{40}$

But $y_3 = (y_0)^3$, so $2^{-20} < (y_0)^{120}$ and therefore, $2^{-20} < y_{120}$.

This tells us that $m$ is somewhere around 120, so our answer is $\boxed{\textbf{(C) } [81,242]}$.

Solution 3

Since the choices are rather wide ranges, we can use approximation to make it easier. Notice that \[x_{n+1} - x_n = \frac{4-x_n}{x_n+6}\] And $x_0 =5$, we know that $x_n$ is a declining sequence, and as it get close to 4 its decline will slow, never falling below 4. So we'll use 4 to approximate $x_n$ in the denominator so that we have a solvable difference equation: \[x_{n+1} - x_n = \frac{4-x_n}{10}\] \[x_{n+1} = \frac{9}{10}x_n + \frac{2}{5}\] Solve it with $x_0 = 5$, we have \[x_n = 4 + (\frac{9}{10})^n\] Now we wish to find $n$ so that \[(\frac{9}{10})^n \approx \frac{1}{2^{20}}\] \[n \approx \frac{\log{2^{20}}}{\log{10}-\log9} \approx \frac{20*0.3}{0.05} = 120\] Since 120 is safely within the range of [81,242], we have the answer. $\boxed{\textbf{(C) } [81,242]}$.

-Mathdummy


Video Solution

https://www.youtube.com/watch?v=toHqTtcCcJQ ~MathProblemSolvingSkills.com


Video Solution

Video Solution: https://www.youtube.com/watch?v=Ok7bYOdiF6M

Aside

The actual value of $m$ is $m=133$.

See Also

2019 AMC 10B (ProblemsAnswer KeyResources)
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 (ProblemsAnswer KeyResources)
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