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

Latest revision as of 10:06, 31 October 2024

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

Solution 4 (no logs)

We start by simplifying the recursion: $x_{n+1} = x_n + \frac{4-x_n}{x_n+6}$ . While $x_n > 4$ , $x_n$ is a decreasing sequence. Let $x_n = 4 + f_n$ . Then $x_{n} - x_{n+1} = \frac{x_n-4}{x_n+6} = \frac{f_n}{10 + f_n} \approx \frac{f_n}{10}.$ Now notice that we want to find $m$ , such that $x_m \leq 4 + \frac{1}{2^{20}}$ , and $x_0 = 4 + \frac{1}{2^0}$ . We are going to find an approximate number of steps to go from $4 + \frac{1}{2^i}$ to $4 + \frac{1}{2^{i+1}}$ . If $x_j = 4 + \frac{1}{2^i}$ , then $f_j = \frac{1}{2^i}$ and if $x_k = 4 + \frac{1}{2^{i+1}}$ , then $f_k = \frac{1}{2^{i+1}}$ . Then $x_j - x_k = \frac{1}{2^{i+1}} \approx \frac{f_j}{10} + \frac{f_{j+1}}{10} + ... + \frac{f_{k-1}}{10}.$ Furthermore, $\frac{1}{2^i} = f_j > f_{j+1} > f_{j+2} > ... > f_{k-1} > f_k = \frac{1}{2^{i+1}}.$ Therefore, $(k-j) \cdot \frac{\frac{1}{2^i}}{10} > \frac{f_j}{10} + \frac{f_{j+1}}{10} + ... + \frac{f_{k-1}}{10} > (k-j) \cdot \frac{\frac{1}{2^{i+1}}}{10},$ so $5 < k-j < 10$ . Therefore, to go from $f_0 = \frac{1}{2^0}$ to $f_m = \frac{1}{2^{20}}$ , we will need to do this 20 times, which means $100 < m - 0 < 200$ , which is within the range of [81,242], so we have the answer. $\boxed{\textbf{(C) } [81,242]}$ .

-alligator112

Solution 5

This solution uses approximation to estimate ranges.

As in Solution 1, we first show that all $x_n>4$ by induction.

Next, we let $a_n=x_n-4$ , so then all $a_n>0$ . Replacing this in the formula results in $a_{n+1}+4=\frac{(a_n+4)^2+5(a_n+4)+4}{(a_n+4)+6}=\frac{a_n^2+13a_n+40}{a_n+10}$ , so then

$a_{n+1}=\frac{a_n^2+9a_n}{a_n+10}$

The problem statement asks us to find some $m$ such that $a_m\le\frac{1}{2^{20}}$ .

Then we let $b_n=\frac{1}{a_n}$ . Note that $a_n>0$ , so $b_n$ is never undefined. Replacing this in the formula results in $\frac{1}{b_{n+1}}=\frac{\left(\frac{1}{b_n}\right)^2+9\cdot\frac{1}{b_n}}{\frac{1}{b_n}+10}=\frac{9b_n+1}{10b_n^2+b_n}$ , so $b_{n+1}=\frac{10b_n^2+b_n}{9b_n+1}=\frac{10}{9}b_n-\frac{1}{81}+\frac{1}{729b_n+81}$ . Now we must find the least $m$ such that $b_m\ge2^{20}$ . Notice that only the $\frac{10}{9}n$ portion of the equation plays a significant role in determining the value of the entire value at higher values of $b_n$ , so we may simply let $b_{n+1}\approx\frac{10}{9}b_n$ .

Since $b_0=\frac{1}{a_n}=\frac{1}{x_0-4}=\frac{1}{5-4}=1$ , we know that $b_n\approx\left(\frac{10}{9}\right)^n=\left(\frac{100}{81}\right)^{\frac{n}{2}}\approx\left(\frac{100}{80}\right)^{\frac{n}{2}}=\left(\frac{5}{4}\right)^{\frac{n}{2}}=\left(\frac{125}{64}\right)^{\frac{n}{6}}\approx\left(\frac{128}{64}\right)^{\frac{n}{6}}=2^{\frac{n}{6}}$ .

Then we have $\frac{m}{6}\ge20$ , so we can estimate that the smallest value $m$ satisfying the condition is $m=120$ . Since this solution is well inside one of the answer choices’ bounds, we can assume this is a good enough estimate, so the answer is $\boxed{\textbf{(C) } [81,242]}$ .

~eevee9406

Remark

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

Video Solution

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

~MathProblemSolvingSkills.com

Video Solution

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

@@ 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
-<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>
 == Solution 1 ==
-We first prove that <math>x_n > 4</math> for all <math>n \ge 0</math> by induction from
+We first prove that <math>x_n > 4</math> for all <math>n \ge 0</math>, by induction. Observe that
 <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>
-and then prove <math>x_n</math>'s are decreasing by
+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:
 <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>
-Now we need to estimate the value of <math>x_{n+1}-4</math> by
+Now we need to estimate the value of <math>x_{n+1}-4</math>, which we can do using the rearranged equation:
 <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>
-since <math>x_n</math>'s are decreasing, <math>\frac{x_n + 5}{x_n+6}</math> are 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>
 \frac{9}{10} < \frac{x_n + 5}{x_n+6} \le \frac{10}{11}
@@ Line 27: / Line 33: @@
 and
 <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>
-which leads to
+This becomes
 <cmath>
-(\frac{9}{10})^n = (\frac{9}{10})^n (x_0-4) < x_{n} - 4 \le (\frac{10}{11})^n (x_0-4) = (\frac{10}{11})^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>
-The problem requires us to find the value of <math>n</math> such that
+The problem thus reduces to finding the least value of <math>n</math> such that
 <cmath>
-(\frac{9}{10})^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  }
-(\frac{10}{11})^{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>
-using natural logarithm, we need
-<math>n \ln \frac{9}{10} < -20 \ln 2</math> and <math>(n-1)\ln \frac{10}{11} > -20 \ln 2</math>, or
+Taking logarithms, we get
+<math>n \ln \frac{9}{10} < -20 \ln 2</math> and <math>(n-1)\ln \frac{10}{11} > -20 \ln 2</math>, i.e.
 <cmath>
 n > \frac{20\ln 2}{\ln\frac{10}{9}} \text{  and  }  n-1 < \frac{20\ln 2}{\ln\frac{11}{10}}
-</cmath>
+.</cmath>
-As estimations, <math>\ln\frac{10}{9} \approx 1/9</math> and <math>\ln\frac{11}{10} \approx 1/10</math>, <math>\ln 2\approx 0.7</math>
+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
-we can estimate that
 <cmath>
-< n < 141
+< n < 141,
 </cmath>
-Choose <math>\boxed{C}</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>.
-== Solution 2 ==
+-Mathdummy
-Making the reasonable assumption that <math>x_n</math> approaches <math>4</math>, we can translate <math>x</math> down by <math>4</math> to obtain a more simple sequence <math>a_n=x_n-4</math> that should approach  <math>0</math>.
+==Solution 4 (no logs)==
+We start by simplifying the recursion: <math>x_{n+1} = x_n + \frac{4-x_n}{x_n+6}</math>.
+While <math>x_n > 4</math>, <math>x_n</math> is a decreasing sequence. Let <math>x_n = 4 + f_n</math>. Then <cmath>x_{n} - x_{n+1} = \frac{x_n-4}{x_n+6} = \frac{f_n}{10 + f_n} \approx \frac{f_n}{10}.</cmath>
+Now notice that we want to find <math>m</math>, such that <math>x_m \leq 4 + \frac{1}{2^{20}}</math>, and <math>x_0 = 4 + \frac{1}{2^0}</math>.
+We are going to find an approximate number of steps to go from <math>4 + \frac{1}{2^i}</math> to <math>4 + \frac{1}{2^{i+1}}</math>.
+If <math>x_j = 4 + \frac{1}{2^i}</math>, then <math>f_j = \frac{1}{2^i}</math> and if <math>x_k = 4 + \frac{1}{2^{i+1}}</math>, then <math>f_k = \frac{1}{2^{i+1}}</math>. Then <cmath>x_j - x_k = \frac{1}{2^{i+1}} \approx \frac{f_j}{10} + \frac{f_{j+1}}{10} + ... + \frac{f_{k-1}}{10}.</cmath>
+Furthermore, <cmath>\frac{1}{2^i} = f_j > f_{j+1} > f_{j+2} > ... > f_{k-1} > f_k = \frac{1}{2^{i+1}}.</cmath> Therefore, <cmath>(k-j) \cdot \frac{\frac{1}{2^i}}{10} > \frac{f_j}{10} + \frac{f_{j+1}}{10} + ... + \frac{f_{k-1}}{10} > (k-j) \cdot \frac{\frac{1}{2^{i+1}}}{10},</cmath> so <math>5 < k-j < 10</math>. Therefore, to go from <math>f_0 = \frac{1}{2^0}</math> to <math>f_m = \frac{1}{2^{20}}</math>, we will need to do this 20 times, which means <math>100 < m - 0 < 200</math>, which is within the range of [81,242], so we have the answer.
+<math>\boxed{\textbf{(C) } [81,242]}</math>.
+-alligator112
-Substitution of <math>(a_{n}+4)</math> for <math>(x_{n})</math> and <math>(a_{n+1}+4)</math> for <math>(x_{n+1})</math> in the definition of <math>x_{n+1}</math> leads to
+==Solution 5==
+This solution uses approximation to estimate ranges.
+As in Solution 1, we first show that all <math>x_n>4</math> by induction.
-<math>a_{n+1}+4 = \frac{(a_{n} + 8)(a_{n}+5)}{a_{n}+10} =  \frac{a_{n}^2 + 13a_{n}+40}{a_{n}+10} \implies a_{n+1} = a_{n}(\frac{a_{n}+9}{a_{n}+10}) \implies \frac{a_{n+1}}{a_{n}} = \frac{a_{n}+9}{a_{n}+10}</math>
+Next, we let <math>a_n=x_n-4</math>, so then all <math>a_n>0</math>. Replacing this in the formula results in <math>a_{n+1}+4=\frac{(a_n+4)^2+5(a_n+4)+4}{(a_n+4)+6}=\frac{a_n^2+13a_n+40}{a_n+10}</math>, so then
+<cmath>a_{n+1}=\frac{a_n^2+9a_n}{a_n+10}</cmath>
-The ratio of consecutive terms is thus always positive and less than 1 (because <math>a_0</math> is positive). This means that the largest possible value for <math>a_n</math> is 1 and that no value of <math>a_n</math> can be less than or equal to 0.
+The problem statement asks us to find some <math>m</math> such that <math>a_m\le\frac{1}{2^{20}}</math>.
-Plugging the extrema of <math>a_n</math> back into the ratio shows that <math>\frac{9}{10}<\frac{a_{n+1}}{a_{n}}\leq\frac{10}{11}</math> for all <math>n</math>.
+Then we let <math>b_n=\frac{1}{a_n}</math>. Note that <math>a_n>0</math>, so <math>b_n</math> is never undefined. Replacing this in the formula results in <math>\frac{1}{b_{n+1}}=\frac{\left(\frac{1}{b_n}\right)^2+9\cdot\frac{1}{b_n}}{\frac{1}{b_n}+10}=\frac{9b_n+1}{10b_n^2+b_n}</math>, so <math>b_{n+1}=\frac{10b_n^2+b_n}{9b_n+1}=\frac{10}{9}b_n-\frac{1}{81}+\frac{1}{729b_n+81}</math>. Now we must find the least <math>m</math> such that <math>b_m\ge2^{20}</math>. Notice that only the <math>\frac{10}{9}n</math> portion of the equation plays a significant role in determining the value of the entire value at higher values of <math>b_n</math>, so we may simply let <math>b_{n+1}\approx\frac{10}{9}b_n</math>.
+Since <math>b_0=\frac{1}{a_n}=\frac{1}{x_0-4}=\frac{1}{5-4}=1</math>, we know that <math>b_n\approx\left(\frac{10}{9}\right)^n=\left(\frac{100}{81}\right)^{\frac{n}{2}}\approx\left(\frac{100}{80}\right)^{\frac{n}{2}}=\left(\frac{5}{4}\right)^{\frac{n}{2}}=\left(\frac{125}{64}\right)^{\frac{n}{6}}\approx\left(\frac{128}{64}\right)^{\frac{n}{6}}=2^{\frac{n}{6}}</math>.
-For <math>(n>0)</math>, we can bound <math>a_{n}</math> by applying this rule recursively  :   <math>(\frac{9}{10})^n < a_{n} \leq (\frac{10}{11})^n</math>
+Then we have <math>\frac{m}{6}\ge20</math>, so we can estimate that the smallest value <math>m</math> satisfying the condition is <math>m=120</math>. Since this solution is well inside one of the answer choices’ bounds, we can assume this is a good enough estimate, so the answer is <math>\boxed{\textbf{(C) } [81,242]}</math>.
+~eevee9406
+==Remark==
+The actual value of <math>m</math> is <math>m=133</math>.
-Therefore, <math>a_{n}</math> is always less than <math>(\frac{1}{2^{20}})</math> when <math>(\frac{10}{11})^n<\frac{1}{2^{20}}\implies n>20log_{\frac{11}{10}}{2}</math>
+==Video Solution==
-and <math>a_{n}</math> is never less than <math>(\frac{1}{2^{20}})</math> when <math>(\frac{9}{10})^n>\frac{1}{2^{20}}\implies n<20log_{\frac{10}{9}}{2}</math>
+https://www.youtube.com/watch?v=toHqTtcCcJQ
+~MathProblemSolvingSkills.com
+==Video Solution==
-The first integer <math>m</math> such that <math>a_{m}\leq\frac{1}{2^{20}}</math> must therefore lie in the interval
+Video Solution: https://www.youtube.com/watch?v=Ok7bYOdiF6M
-<math>\left[\left\lfloor 20log_{\frac{10}{9}}{2}\right\rfloor+1, \left\lceil 20log_{\frac{11}{10}}{2}\right\rceil\right]</math>
-Both of these can be quickly estimated at c. <math>140</math>, so the answer must be <math>\boxed{C}</math>.
-(actual values are <math>132</math> and <math>147</math>)
 ==See Also==
@@ Line 89: / Line 172: @@
 {{AMC12 box|year=2019|ab=B|num-b=21|num-a=23}}
 {{MAA Notice}}
-SUB2PEWDS

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

Page

Toolbox

Search

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

Latest revision as of 10:06, 31 October 2024

Contents

Problem

Solution 1

Solution 2

Solution 3

Solution 4 (no logs)

Solution 5

Remark

Video Solution

Video Solution

See Also