Difference between revisions of "2021 Fall AMC 12B Problems/Problem 18"
m (→Solution) |
Juicefruit (talk | contribs) |
||
(38 intermediate revisions by 6 users not shown) | |||
Line 5: | Line 5: | ||
This sequence tends to a limit; call it <math>L</math>. What is the least value of <math>k</math> such that <cmath>|u_k-L| \le \frac{1}{2^{1000}}?</cmath> | This sequence tends to a limit; call it <math>L</math>. What is the least value of <math>k</math> such that <cmath>|u_k-L| \le \frac{1}{2^{1000}}?</cmath> | ||
− | <math> | + | <math>\textbf{(A)}\: 10\qquad\textbf{(B)}\: 87\qquad\textbf{(C)}\: 123\qquad\textbf{(D)}\: 329\qquad\textbf{(E)}\: 401</math> |
− | ==Solution== | + | ==Solution 1== |
− | + | Note that terms of the sequence <math>(u_k)</math> lie in the interval <math>\left(0,\frac12\right),</math> strictly increasing. | |
− | + | Since the sequence <math>(u_k)</math> tends to the limit <math>L,</math> we set <math>u_{k+1}=u_k=L>0.</math> | |
+ | |||
+ | The given equation becomes <cmath>L=2L-2L^2,</cmath> from which <math>L=\frac12.</math> | ||
+ | |||
+ | The given inequality becomes <cmath>\frac12-\frac{1}{2^{1000}} \leq u_k \leq \frac12+\frac{1}{2^{1000}},</cmath> and we only need to consider <math>\frac12-\frac{1}{2^{1000}} \leq u_k.</math> | ||
+ | |||
+ | We have | ||
+ | <cmath>\begin{alignat*}{8} | ||
+ | u_0 &= \phantom{1}\frac14 &&= \frac{2^1-1}{2^2}, \\ | ||
+ | u_1 &= \phantom{1}\frac38 &&= \frac{2^2-1}{2^3}, \\ | ||
+ | u_2 &= \ \frac{15}{32} &&= \frac{2^4-1}{2^5}, \\ | ||
+ | u_3 &= \frac{255}{512} &&= \frac{2^8-1}{2^9}, \\ | ||
+ | & \phantom{1111} \vdots | ||
+ | \end{alignat*}</cmath> | ||
+ | By induction, it can be proven that <cmath>u_k=\frac{2^{2^k}-1}{2^{2^k+1}}=\frac12-\frac{1}{2^{2^k+1}}.</cmath> | ||
+ | We substitute this into the inequality, then solve for <math>k:</math> | ||
<cmath>\begin{align*} | <cmath>\begin{align*} | ||
− | u_{k+1} &= 2\cdot(\frac{1}{2}-\frac{1}{2^{ | + | \frac12-\frac{1}{2^{1000}} &\leq \frac12-\frac{1}{2^{2^k+1}} \\ |
− | &= 1-\frac{1}{2^{n_k - 1}}-2\cdot(\frac{1}{4}-\frac{1}{2^{n_k}}+\frac{1}{2^{2 \cdot n_k}}) \\ | + | -\frac{1}{2^{1000}} &\leq -\frac{1}{2^{2^k+1}} \\ |
+ | 2^{1000} &\leq 2^{2^k+1} \\ | ||
+ | 1000 &\leq 2^k+1. | ||
+ | \end{align*}</cmath> | ||
+ | Therefore, the least such value of <math>k</math> is <math>\boxed{\textbf{(A)}\: 10}.</math> | ||
+ | |||
+ | ~MRENTHUSIASM | ||
+ | |||
+ | ==Solution 2== | ||
+ | |||
+ | If we list out the first few values of <math>k</math>, we get the series <math>\frac{1}{4}, \frac{3}{8}, \frac{15}{32}, \frac{255}{512}</math>, which always seems to be a negative power of <math>2</math> away from <math>\frac{1}{2}</math>. We can test this out by setting <math>u_k=\frac{1}{2}-\frac{1}{2^{n_k}}</math>, where <math>n_0=2</math>. | ||
+ | |||
+ | Now, we get | ||
+ | <cmath>\begin{align*} | ||
+ | u_{k+1} &= 2\cdot\left(\frac{1}{2}-\frac{1}{2^{n_{k}}}\right)-2\cdot\left(\frac{1}{2}-\frac{1}{2^{n_{k}}}\right)^2 \\ | ||
+ | &= 1-\frac{1}{2^{n_k - 1}}-2\cdot\left(\frac{1}{4}-\frac{1}{2^{n_k}}+\frac{1}{2^{2 \cdot n_k}}\right)\\ | ||
&= 1-\frac{1}{2^{n_k - 1}}-\frac{1}{2}+\frac{1}{2^{n_k-1}}-\frac{1}{2^{2 \cdot n_k-1}} \\ | &= 1-\frac{1}{2^{n_k - 1}}-\frac{1}{2}+\frac{1}{2^{n_k-1}}-\frac{1}{2^{2 \cdot n_k-1}} \\ | ||
− | &= \frac{1}{2}-\frac{1}{2^{2 \cdot n_k-1}} | + | &= \frac{1}{2}-\frac{1}{2^{2 \cdot n_k-1}}. |
− | \end{align*} | + | \end{align*}</cmath> |
− | </ | + | This means that this series approaches <math>\frac{1}{2}</math>, as the second term is decreasing. In addition, we find that <math>n_{k+1}=2 \cdot n_k-1</math>. |
+ | |||
+ | We claim that <math>n_k = 2^k+1</math>, which can be proven by induction: | ||
+ | |||
+ | <u><b>Base Case</b></u> | ||
+ | |||
+ | We have <math>n_0=2=2^0+1</math>. | ||
+ | |||
+ | <u><b>Induction Step</b></u> | ||
+ | |||
+ | Assuming that the claim is true, we have <math>n_{k+1}=2 \cdot (2^k+1)-1=2^{k+1}+1</math>. | ||
+ | |||
+ | It follows that <math>n_{10}=2^{10}+1>1000</math> and <math>n_9=2^9+1<1000</math>. Therefore, the least value of <math>k</math> would be <math>\boxed{\textbf{(A)}\: 10}</math>. | ||
+ | |||
+ | ~ConcaveTriangle | ||
+ | |||
+ | ==Solution 3== | ||
+ | |||
+ | We are given <math>u_{k+1} = 2u_k - 2{u_k}^2</math>. Multiply this equation by <math>2</math> and subtract <math>1</math> from both sides. The equations can then be written nicely as <math>2u_{k+1} - 1 = -(2u_k-1)^2</math>. Let <math>v_k = 2u_k - 1</math> so that <math>v_{k+1} = -(v_k)^2</math>. | ||
− | This means | + | Clearly, <math>v_0 = 2u_0 - 1 = -\frac{1}{2}</math>. Since the magnitude of <math>v_0</math> is less than <math>1</math> and because our recursive relation for <math>v_k</math> squares the previous term (and negates it), we see that as <math>k \rightarrow \infty, 2u_k - 1 = v_k \rightarrow 0</math>. This means <math>u_k \rightarrow \frac{1}{2}</math>, so <math>L = \frac{1}{2}</math>. |
− | + | Isolating <math>u_k</math> in our relation <math>2u_k - 1 = v_k</math> gives us <math>u_k = \frac{v_k + 1}{2}</math>. | |
+ | Substituting into the inequality, we have <math>\left|\frac{v_k + 1}{2}-\frac{1}{2}\right| \le \frac{1}{2^{1000}}</math>. Rewriting this, we get <math>|v_k| \le \frac{1}{2^{999}}</math>. | ||
− | + | The sequence <math>\{v_k\}</math> is much easier to handle because of its simple recursive relation. Writing out a few terms shows that <math>|v_k| = \frac{1}{2^{2^k}}</math>. Now it just comes down to having <math>2^k > 999</math>, so <math>k = \boxed{\textbf{(A)}\: 10}</math>. | |
− | + | ~chezpotato | |
− | + | ==Video Solution== | |
+ | https://youtu.be/ZfHql_vhNes | ||
− | + | ~MathProblemSolvingSkills.com | |
− | - | + | ==See Also== |
+ | {{AMC12 box|year=2021 Fall|ab=B|num-a=19|num-b=17}} | ||
+ | {{MAA Notice}} |
Latest revision as of 10:36, 5 November 2022
Problem
Set , and for
let
be determined by the recurrence
This sequence tends to a limit; call it . What is the least value of
such that
Solution 1
Note that terms of the sequence lie in the interval
strictly increasing.
Since the sequence tends to the limit
we set
The given equation becomes from which
The given inequality becomes and we only need to consider
We have
By induction, it can be proven that
We substitute this into the inequality, then solve for
Therefore, the least such value of
is
~MRENTHUSIASM
Solution 2
If we list out the first few values of , we get the series
, which always seems to be a negative power of
away from
. We can test this out by setting
, where
.
Now, we get
This means that this series approaches
, as the second term is decreasing. In addition, we find that
.
We claim that , which can be proven by induction:
Base Case
We have .
Induction Step
Assuming that the claim is true, we have .
It follows that and
. Therefore, the least value of
would be
.
~ConcaveTriangle
Solution 3
We are given . Multiply this equation by
and subtract
from both sides. The equations can then be written nicely as
. Let
so that
.
Clearly, . Since the magnitude of
is less than
and because our recursive relation for
squares the previous term (and negates it), we see that as
. This means
, so
.
Isolating in our relation
gives us
.
Substituting into the inequality, we have
. Rewriting this, we get
.
The sequence is much easier to handle because of its simple recursive relation. Writing out a few terms shows that
. Now it just comes down to having
, so
.
~chezpotato
Video Solution
~MathProblemSolvingSkills.com
See Also
2021 Fall AMC 12B (Problems • Answer Key • Resources) | |
Preceded by Problem 17 |
Followed by Problem 19 |
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.