Difference between revisions of "2019 AMC 10B Problems/Problem 24"
Firebolt360 (talk | contribs) (→Video Solution) |
(solution 5) |
||
(10 intermediate revisions by 6 users not shown) | |||
Line 14: | 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 | + | 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 | + | 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 33: | 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 51: | 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 | + | 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 | + | which gives <math>\boxed{\textbf{(C) } [81,242]}</math>. |
==Solution 2== | ==Solution 2== | ||
Line 123: | Line 123: | ||
-Mathdummy | -Mathdummy | ||
+ | ==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 | ||
+ | |||
+ | ==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. | ||
+ | |||
+ | 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 problem statement asks us to find some <math>m</math> such that <math>a_m\le\frac{1}{2^{20}}</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>. | ||
+ | |||
+ | 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>. | ||
==Video Solution== | ==Video Solution== | ||
https://www.youtube.com/watch?v=toHqTtcCcJQ | https://www.youtube.com/watch?v=toHqTtcCcJQ | ||
+ | |||
~MathProblemSolvingSkills.com | ~MathProblemSolvingSkills.com | ||
− | |||
==Video Solution== | ==Video Solution== | ||
Line 134: | Line 167: | ||
Video Solution: https://www.youtube.com/watch?v=Ok7bYOdiF6M | Video Solution: https://www.youtube.com/watch?v=Ok7bYOdiF6M | ||
− | |||
− | |||
==See Also== | ==See Also== |
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.
Contents
[hide]Problem
Define a sequence recursively by and for all nonnegative integers Let be the least positive integer such that
In which of the following intervals does lie?
Solution 1
We first prove that for all , by induction. Observe that so (since is clearly positive for all , from the initial definition), if and only if .
We similarly prove that is decreasing:
Now we need to estimate the value of , which we can do using the rearranged equation: Since is decreasing, is also decreasing, so we have and
This becomes The problem thus reduces to finding the least value of such that
Taking logarithms, we get and , i.e.
As approximations, we can use , , and . These approximations allow us to estimate which gives .
Solution 2
The condition where gives the motivation to make a substitution to change the equilibrium from to . We can substitute to achieve that. Now, we need to find the smallest value of such that given that .
Factoring the recursion , we get:
.
Using wishful thinking, we can simplify the recursion as follows:
.
The recursion looks like a geometric sequence with the ratio changing slightly after each term. Notice from the recursion that the sequence is strictly decreasing, so all the terms after 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, . Combining this with the fact that the recursion resembles a geometric sequence, we conclude that
is approximately equal to and the ranges that the answer choices give us are generous, so we should use either or to find a rough estimate for .
Since , that means . Additionally,
Therefore, we can estimate that .
Raising both sides to the 40th power, we get
But , so and therefore, .
This tells us that is somewhere around 120, so our answer is .
Solution 3
Since the choices are rather wide ranges, we can use approximation to make it easier. Notice that And , we know that 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 in the denominator so that we have a solvable difference equation: Solve it with , we have Now we wish to find so that Since 120 is safely within the range of [81,242], we have the answer. .
-Mathdummy
Solution 4 (no logs)
We start by simplifying the recursion: . While , is a decreasing sequence. Let . Then Now notice that we want to find , such that , and . We are going to find an approximate number of steps to go from to . If , then and if , then . Then Furthermore, Therefore, so . Therefore, to go from to , we will need to do this 20 times, which means , which is within the range of [81,242], so we have the answer. .
-alligator112
Solution 5
This solution uses approximation to estimate ranges.
As in Solution 1, we first show that all by induction.
Next, we let , so then all . Replacing this in the formula results in , so then
The problem statement asks us to find some such that .
Then we let . Note that , so is never undefined. Replacing this in the formula results in , so . Now we must find the least such that . Notice that only the portion of the equation plays a significant role in determining the value of the entire value at higher values of , so we may simply let .
Since , we know that .
Then we have , so we can estimate that the smallest value satisfying the condition is . 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 .
~eevee9406
Remark
The actual value of is .
Video Solution
https://www.youtube.com/watch?v=toHqTtcCcJQ
~MathProblemSolvingSkills.com
Video Solution
Video Solution: https://www.youtube.com/watch?v=Ok7bYOdiF6M
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.