Difference between revisions of "2022 AMC 12B Problems/Problem 22"

Revision as of 11:00, 4 December 2022

Problem

Ant Amelia starts on the number line at $0$ and crawls in the following manner. For $n=1,2,3,$ Amelia chooses a time duration $t_n$ and an increment $x_n$ independently and uniformly at random from the interval $(0,1).$ During the $n$ th step of the process, Amelia moves $x_n$ units in the positive direction, using up $t_n$ minutes. If the total elapsed time has exceeded $1$ minute during the $n$ th step, she stops at the end of that step; otherwise, she continues with the next step, taking at most $3$ steps in all. What is the probability that Amelia’s position when she stops will be greater than $1$ ?

$\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}$

Solution 1

We use the following lemma to solve this problem.

Let $y_1, y_2, \cdots, y_n$ be independent random variables that are uniformly distributed on $(0,1)$ . Then for $n = 2$ , $\Bbb P \left( y_1 + y_2 \leq 1 \right) = \frac{1}{2} .$

For $n = 3$ , $\Bbb P \left( y_1 + y_2 + y_3 \leq 1 \right) = \frac{1}{6} . \textrm{ (Check remark for proof)}$

Now, we solve this problem.

We denote by $\tau$ the last step Amelia moves. Thus, $\tau \in \left\{ 2, 3 \right\}$ . We have

$\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*}$

where the second equation follows from the property that $\left\{ x_n \right\}$ and $\left\{ t_n \right\}$ 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 $\frac{1}{2}$ , as stated above, and thus the latter also has a probability of $\frac{1}{2}$ .

The probability that Amelia passes $1$ after two steps is also $\frac{1}{2}$ , as it is symmetric to the probability above.

Thus, if the probability that Amelia passes $1$ after three steps is $x$ , our total probability is $\frac{1}{2} \cdot \frac{1}{2} + \frac{1}{2} \cdot x$ . We know that $0 < x < 1$ , and it is relatively obvious that $x > \frac{1}{2}$ (because the probability that $x > \frac{3}{2}$ is $\frac{1}{2}$ ). This means that our total probability is between $\frac{1}{2}$ and $\frac{3}{4}$ , non-inclusive, so the only answer choice that fits is $\boxed{\textbf{(C) }\frac{2}{3}}$

~mathboy100

Solution 3

Obviously the chance of Amelia stopping after only $1$ step is $0$ .

When Amelia takes $2$ steps, then the sum of the time taken during the steps is greater than $1$ minute. Let the time taken be $x$ and $y$ respectively, then we need $x+y>1$ for $0<x<1, 0<y<1$ , which has a chance of $\frac{1}{2}$ . Let the lengths of steps be $a$ and $b$ respectively, then we need $a+b>1$ for $0<a<1, 0<b<1$ , which has a chance of $\frac{1}{2}$ . Thus the total chance for this case is $\frac{1}{4}$ .

When Amelia takes $3$ steps, then by complementary counting the chance of taking $3$ steps is $1-\frac{1}{2}=\frac{1}{2}$ . Let the lengths of steps be $a$ , $b$ and $c$ respectively, then we need $a+b+c>1$ for $0<a<1, 0<b<1, 0<c<1$ , which has a chance of $\frac{5}{6}$ (Check the Remark section for proof.). Thus the total chance for this case is $\frac{5}{12}$ .

Thus the answer is $\frac{1}{4}+\frac{5}{12}=\frac{2}{3}$ .

Solution 4 (Generalization, Induction)

We can in fact find the probability that any number of randomly distributed numbers on the interval $[0, 1]$ sum to more than $1$ using geometric probability, as shown in the video below.

If we graph the points that satisfy $x + y < 1$ , $0 < x, y < 1$ , we get the triangle with points $(0, 1)$ , $(0, 0)$ , and $(1, 0)$ . If we graph the points that satisfy $x + y + z < 1$ , $0 < x, y, z < 1$ , we get the tetrahedron with points $(0, 1, 0)$ , $(0, 0, 0)$ , $0, 0, 1$ , and $(1, 0, 0)$ .

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 $1$ (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 $n$ numbers using induction.

$\textbf{Claim:}$ The probability that the sum is less than one is $\frac{1}{n!}$ .

$\textbf{Base Case:}$ For just $1$ number, the probability is $1$ .

$\textbf{Induction step:}$ Suppose that the probability for $n$ numbers is $\frac{1}{n!}$ . We will prove that the probability for $n+1$ numbers is $\frac{1}{(n+1)!}$ . To prove this, we consider that the area of an $n+1$ -dimensional tetrahedron is simply the area/volume of the base times the height divided by $n+1$ .

Of course, the area of the base is $\frac{1}{n!}$ , and the height is $1$ , and thus, we obtain $\frac{1}{n! \cdot (n+1)} = \frac{1}{(n+1)!}$ 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 $1$ is $\frac{1}{n!}$ , and the probability of the sum being more than $1$ is $\frac{n!-1}{n!}$ . This trivializes the problem. The answer is $\frac{1}{2} \cdot \frac{2! - 1}{2!} + \frac{1}{2} \cdot \frac{3! - 1}{3!} = \boxed{\textbf{(C) }\frac{2}{3}}.$

~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)

@@ Line 69: / Line 69: @@
 Thus the answer is <math>\frac{1}{4}+\frac{5}{12}=\frac{2}{3}</math>.
-==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)</cmath>
-<cmath> = 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>\frac{\int_0^1 \! 1 - \frac{1}{2}(1 - x)^2 \mathrm{d}x}{1}</cmath>
-<cmath> = \int_0^1 \! 1 - \frac{1}{2}(1 - x)^2 \mathrm{d}x</cmath>
-<cmath> = 1 - \frac{1}{2}\int_0^1 \! (1 - x)^2 \mathrm{d}x</cmath>
-<cmath> = 1 - \frac{1}{2}\int_0^1 \! x^2 \mathrm{d}x</cmath>
-<cmath> = 1 - \frac{1}{2}\left(\frac{1}{3}\right)</cmath>
-<cmath> = \boxed{\frac{5}{6}}.</cmath>
-~mathboy100
 ==Solution 4 (Generalization, Induction)==

2022 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

2022 AMC 10B (Problems • Answer Key • Resources)
Preceded by Problem 22	Followed by Problem 24
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

Page

Toolbox

Search