|
|
(4 intermediate revisions by the same user not shown) |
Line 1: |
Line 1: |
− | ==Problem==
| + | #redirect [[2022 AMC 10B Problems/Problem 23]] |
− | Ant Amelia starts on the number line at <math>0</math> and crawls in the following manner. For <math>n=1,2,3,</math> Amelia chooses a time duration <math>t_n</math> and an increment <math>x_n</math> independently and uniformly at random from the interval <math>(0,1).</math> During the <math>n</math>th step of the process, Amelia moves <math>x_n</math> units in the positive direction, using up <math>t_n</math> minutes. If the total elapsed time has exceeded <math>1</math> minute during the <math>n</math>th step, she stops at the end of that step; otherwise, she continues with the next step, taking at most <math>3</math> steps in all. What is the probability that Amelia’s position when she stops will be greater than <math>1</math>?
| |
− | | |
− | <math>\textbf{(A) }\frac{1}{3} \qquad \textbf{(B) }\frac{1}{2} \qquad \textbf{(C) }\frac{2}{3} \qquad \textbf{(D) }\frac{3}{4} \qquad \textbf{(E) }\frac{5}{6}</math>
| |
− | | |
− | ==Solution 1==
| |
− | | |
− | We use the following lemma to solve this problem.
| |
− | | |
− | ---------------------------------------
| |
− | Let <math>y_1, y_2, \cdots, y_n</math> be independent random variables that are uniformly distributed on <math>(0,1)</math>. Then for <math>n = 2</math>,
| |
− | <cmath>
| |
− | \[
| |
− | \Bbb P \left( y_1 + y_2 \leq 1 \right) = \frac{1}{2} .
| |
− | \]
| |
− | </cmath>
| |
− | | |
− | For <math>n = 3</math>,
| |
− | <cmath>
| |
− | \[
| |
− | \Bbb P \left( y_1 + y_2 + y_3 \leq 1 \right) = \frac{1}{6} . \textrm{ (Check remark for proof)}
| |
− | \]
| |
− | </cmath>
| |
− | ---------------------------------------
| |
− | | |
− | Now, we solve this problem.
| |
− | | |
− | We denote by <math>\tau</math> the last step Amelia moves. Thus, <math>\tau \in \left\{ 2, 3 \right\}</math>.
| |
− | We have
| |
− | | |
− | <cmath>
| |
− | \begin{align*}
| |
− | P \left( \sum_{n=1}^\tau x_n > 1 \right)
| |
− | & = P \left( x_1 + x_2 > 1 | t_1 + t_2 > 1 \right)
| |
− | P \left( t_1 + t_2 > 1 \right) \\
| |
− | & \hspace{1cm} + P \left( x_1 + x_2 + x_3 > 1 | t_1 + t_2 \leq 1 \right)
| |
− | P \left( t_1 + t_2 \leq 1 \right) \\
| |
− | & = P \left( x_1 + x_2 > 1 \right)
| |
− | P \left( t_1 + t_2 > 1 \right)
| |
− | + P \left( x_1 + x_2 + x_3 > 1 \right)
| |
− | P \left( t_1 + t_2 \leq 1 \right) \\
| |
− | & = \left( 1 - \frac{1}{2} \right)\left( 1 - \frac{1}{2} \right)
| |
− | + \left( 1 - \frac{1}{6} \right) \frac{1}{2} \\
| |
− | & = \boxed{\textbf{(C) } \frac{2}{3}} ,
| |
− | \end{align*}
| |
− | </cmath>
| |
− | | |
− | where the second equation follows from the property that <math>\left\{ x_n \right\}</math> and <math>\left\{ t_n \right\}</math> are independent sequences, the third equality follows from the lemma above.
| |
− | | |
− | ~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)
| |
− | | |
− | ==Solution 2 (Clever)==
| |
− | There are two cases: Amelia takes two steps or three steps.
| |
− | | |
− | The former case has a probability of <math>\frac{1}{2}</math>, as stated above, and thus the latter also has a probability of <math>\frac{1}{2}</math>.
| |
− | | |
− | The probability that Amelia passes <math>1</math> after two steps is also <math>\frac{1}{2}</math>, as it is symmetric to the probability above.
| |
− | | |
− | Thus, if the probability that Amelia passes <math>1</math> after three steps is <math>x</math>, our total probability is <math>\frac{1}{2} \cdot \frac{1}{2} + \frac{1}{2} \cdot x</math>. We know that <math>0 < x < 1</math>, and it is relatively obvious that <math>x > \frac{1}{2}</math> (because the probability that <math>x > \frac{3}{2}</math> is <math>\frac{1}{2}</math>). This means that our total probability is between <math>\frac{1}{2}</math> and <math>\frac{3}{4}</math>, non-inclusive, so the only answer choice that fits is <math>\boxed{\textbf{(C) }\frac{2}{3}}</math>
| |
− | | |
− | ~mathboy100
| |
− | | |
− | ==Solution 3==
| |
− | Obviously the chance of Amelia stopping after only <math>1</math> step is <math>0</math>.
| |
− | | |
− | When Amelia takes <math>2</math> steps, then the sum of the time taken during the steps is greater than <math>1</math> minute. Let the time taken be <math>x</math> and <math>y</math> respectively, then we need <math>x+y>1</math> for <math>0<x<1, 0<y<1</math>, which has a chance of <math>\frac{1}{2}</math>. Let the lengths of steps be <math>a</math> and <math>b</math> respectively, then we need <math>a+b>1</math> for <math>0<a<1, 0<b<1</math>, which has a chance of <math>\frac{1}{2}</math>. Thus the total chance for this case is <math>\frac{1}{4}</math>.
| |
− | | |
− | When Amelia takes <math>3</math> steps, then by complementary counting the chance of taking <math>3</math> steps is <math>1-\frac{1}{2}=\frac{1}{2}</math>. Let the lengths of steps be <math>a</math>, <math>b</math> and <math>c</math> respectively, then we need <math>a+b+c>1</math> for <math>0<a<1, 0<b<1, 0<c<1</math>, which has a chance of <math>\frac{5}{6}</math> (Check the <b>Remark</b> section for proof.). Thus the total chance for this case is <math>\frac{5}{12}</math>.
| |
− | | |
− | Thus the answer is <math>\frac{1}{4}+\frac{5}{12}=\frac{2}{3}</math>.
| |
− | | |
− | ==Solution 4 (Generalization and Induction)==
| |
− | | |
− | We can in fact find the probability that any number of randomly distributed numbers on the interval <math>[0, 1]</math> sum to more than <math>1</math> using geometric probability, as shown in the video below.
| |
− | | |
− | If we graph the points that satisfy <math>x + y < 1</math>, <math>0 < x, y < 1</math>, we get the triangle with points <math>(0, 1)</math>, <math>(0, 0)</math>, and <math>(1, 0)</math>. If we graph the points that satisfy <math>x + y + z < 1</math>, <math>0 < x, y, z < 1</math>, we get the tetrahedron with points <math>(0, 1, 0)</math>, <math>(0, 0, 0)</math>, <math>0, 0, 1</math>, and <math>(1, 0, 0)</math>.
| |
− | | |
− | Of course, the probability of either of these cases happening is simply the area/volume of the points we graphed divided by the total area of the graph, which is always <math>1</math> (this would be much simpler than my calculus proof above).
| |
− | | |
− | Thus, we can now solve for the probability that the sum is less than one for <math>n</math> numbers using induction.
| |
− | | |
− | <math>\textbf{Claim:}</math> The probability that the sum is less than one is <math>\frac{1}{n!}</math>.
| |
− | | |
− | <math>\textbf{Base Case:}</math> For just <math>1</math> number, the probability is <math>1</math>.
| |
− | | |
− | <math>\textbf{Induction step:}</math> Suppose that the probability for <math>n</math> numbers is <math>\frac{1}{n!}</math>. We will prove that the probability for <math>n+1</math> numbers is <math>\frac{1}{(n+1)!}</math>. To prove this, we consider that the area of an <math>n+1</math>-dimensional tetrahedron is simply the area/volume of the base times the height divided by <math>n+1</math>.
| |
− | | |
− | Of course, the area of the base is <math>\frac{1}{n!}</math>, and the height is <math>1</math>, and thus, we obtain <math>\frac{1}{n! \cdot (n+1)} = \frac{1}{(n+1)!}</math> as our volume (this may be hard to visualize for higher dimensions). The induction step is complete.
| |
− | | |
− | The probability of the sum being less than <math>1</math> is <math>\frac{1}{n!}</math>, and the probability of the sum being more than <math>1</math> is <math>\frac{n!-1}{n!}</math>. This trivializes the problem. The answer is <cmath>\frac{1}{2} \cdot \frac{2! - 1}{2!} + \frac{1}{2} \cdot \frac{3! - 1}{3!} = \boxed{\textbf{(C) }\frac{2}{3}}.</cmath>
| |
− | | |
− | ~mathboy100
| |
− | | |
− | ==Remark==
| |
− | It is not immediately clear why three random numbers between <math>0</math> and <math>1</math> have a probability of <math>\frac{5}{6}</math> of summing to more than <math>1</math>. Here is a proof:
| |
− | | |
− | Let us start by finding the probability that two random numbers between <math>0</math> and <math>1</math> have a sum of more than <math>x</math>, where <math>0 \leq x \leq 1</math>.
| |
− | | |
− | Suppose that our two numbers are <math>y</math> and <math>z</math>. Then, the probability that <math>y > x</math> (which means that <math>y + z > x</math>) is <math>1 - x</math>, and the probability that <math>y < x</math> is <math>x</math>.
| |
− | | |
− | If <math>y < x</math>, the probability that <math>y + z > x</math> is <math>1 - x + y</math>. This is because the probability that <math>y + z < x</math> is equal to the probability that <math>z < x - y</math>, which is <math>x - y</math>, so our total probability is <math>1 - (x - y) = 1 - x + y</math>.
| |
− | | |
− | Let us now find the average of the probability that <math>y + z > x</math> when <math>y < x</math>. Since <math>y</math> is a random number between <math>0</math> and <math>x</math>, its average is <math>\frac{x}{2}</math>. Thus, our average is <math>1 - x + \frac{1}{2} = 1 - \frac{x}{2}</math>.
| |
− | | |
− | Hence, our total probability is equal to
| |
− | <cmath>1(1-x) + \left(1 - \frac{x}{2}\right)(x) = 1 - \frac{1}{2}x^2.</cmath>
| |
− | Now, let us find the probability that three numbers uniformly distributed between <math>0</math> and <math>1</math> sum to more than <math>1</math>.
| |
− | | |
− | Let our three numbers be <math>a</math>, <math>b</math>, and <math>c</math>. Then, the probability that <math>a + b + c > 1</math> is equal to the probability that <math>b + c</math> is greater than <math>1 - a</math>, which is equal to <math>1 - \frac{1}{2}(1 - a)^2</math>.
| |
− | | |
− | To find the total probability, we must average over all values of <math>a</math>. This average is simply equal to the area under the curve <math>1 - \frac{1}{2}(1-x)^2</math> from <math>0</math> to <math>1</math>, all divided by <math>1</math>. We can compute this value using integrals: (for those who don't know calculus, <math>\int_m^n \! f(x) \mathrm{d}x</math> is the area under the curve <math>f(x)</math> from <math>m</math> to <math>n</math>)
| |
− | <cmath>\begin{align*}
| |
− | \frac{\int_0^1 \! 1 - \frac{1}{2}(1 - x)^2 \mathrm{d}x}{1} &= \int_0^1 \! 1 - \frac{1}{2}(1 - x)^2 \mathrm{d}x \\
| |
− | &= 1 - \frac{1}{2}\int_0^1 \! (1 - x)^2 \mathrm{d}x \\
| |
− | &= 1 - \frac{1}{2}\int_0^1 \! x^2 \mathrm{d}x \\
| |
− | &= 1 - \frac{1}{2}\left(\frac{1}{3}\right) \\
| |
− | &= \boxed{\frac{5}{6}}.
| |
− | \end{align*}</cmath>
| |
− | ~mathboy100
| |
− | | |
− | == Video Solution by OmegaLearn Using Geometric Probability ==
| |
− | https://youtu.be/-AqhcVX8mTw
| |
− | | |
− | ~ pi_is_3.14
| |
− | ==Video Solution==
| |
− | | |
− | https://youtu.be/WsA94SmsF5o
| |
− | | |
− | ~ThePuzzlr
| |
− | | |
− | https://youtu.be/qOxnx_c9kVo
| |
− | | |
− | ~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)
| |
− | | |
− | ==See Also==
| |
− | | |
− | {{AMC12 box|year=2022|ab=B|num-b=21|num-a=23}}
| |
− | {{AMC10 box|year=2022|ab=B|num-b=22|num-a=24}}
| |
− | {{MAA Notice}}
| |