Difference between revisions of "2023 AMC 12A Problems/Problem 17"

Revision as of 17:23, 9 November 2023

Problem

Flora the frog starts at 0 on the number line and makes a sequence of jumps to the right. In any one jump, independent of previous jumps, Flora leaps a positive integer distance $m$ with probability $\frac{1}{2^m}$ .

What is the probability that Flora will eventually land at 10?

$\textbf{(A)}~\frac{5}{512}\qquad\textbf{(B)}~\frac{45}{1024}\qquad\textbf{(C)}~\frac{127}{1024}\qquad\textbf{(D)}~\frac{511}{1024}\qquad\textbf{(E)}~\frac{1}{2}$

Solution 1

Let's denote $f(n)$ as the probability of reaching $n$ from $0$ . We immediately see that $f(0) = 1$ , and $f(1) = \frac{1}{2}$ , since there's only one way to get to 1 from 0. Just jump!

Now, let's write an expression for $f(10)$ . Suppose we know $f(9),f(8),\dotsc,f(2)$ .

The probability of reaching 10 from some integer $k < 10$ will be $\frac{1}{2^{10-k}}$ (use the formula given in the problem!) The probability of reaching that integer $k$ from $0$ is going to be $f(k)$ . Then, the probability of going from $0 \to \underbrace{ k \to 10}_{\text{one jump}}$ will be $\mathbb{P}(\text{Reaching } 10 \text{ from } 0 \text { while passing through } k) = f(k) \cdot \frac{1}{2^{10-k}}$ We want the probability of reaching 10 from anywhere though, so what we can do is sum over all passing points $k$ , i.e. $f(10) = \sum_{k=0}^9 \mathbb{P}(\text{Reaching } 10 \text{ from } 0 \text { while passing through } k) = \sum_{k=0}^9 \frac{1}{2^{10-k}} \cdot f(k)$

Now that we have expressed our problem formally, we can actually start solving it!

Let's calculate $f(9)$ . $f(9) = \sum_{k=0}^8 \frac{1}{2^{9-k}} \cdot f(k)$ $\frac{f(9)}{2} = \sum_{k=0}^8 \frac{1}{2^{10-k}} \cdot f(k)$ Hmm, we see that the first 8 terms of $\frac{f(9)}{2}$ are exactly the first 8 terms of $f(10)$ . Let's substitute it in. $f(10) = \frac{1}{2} \cdot f(9) + \color{red} \sum_{k=0}^8 \frac{1}{2^{10-k}} \cdot f(k)$ $f(10) = \frac{1}{2} \cdot f(9) + \color{red} \frac{1}{2} \cdot f(9)$ $f(10) = f(9)$ Isn't that interesting. Turns out, this reasoning can be extended all the way to $f(10) = f(9) = \dotsc = f(2) = f(1)$ .

It breaks at $f(1) \neq f(0)$ , since $f(1) = \frac{1}{2} f(0)$ . Anyway, with this, we see that the answer is just

$f(10) = f(1) = \boxed{\textbf{(E)} \ \frac{1}{2}}$ ~ $\color{magenta} zoomanTV$

@@ Line 1: / Line 1: @@
-Hey the solutions will be posted after the contest, most likely around a couple weeks afterwords. We are not going to leak the questions to you, best of luck and I hope you get a good score.
+==Problem==
+Flora the frog starts at 0 on the number line and makes a sequence of jumps to the right. In any one jump, independent of previous jumps, Flora leaps a positive integer distance <math>m</math> with probability <math>\frac{1}{2^m}</math>.
--Jonathan Yu
+What is the probability that Flora will eventually land at 10?
+<math>\textbf{(A)}~\frac{5}{512}\qquad\textbf{(B)}~\frac{45}{1024}\qquad\textbf{(C)}~\frac{127}{1024}\qquad\textbf{(D)}~\frac{511}{1024}\qquad\textbf{(E)}~\frac{1}{2}</math>
+== Solution 1 ==
+Let's denote <math>f(n)</math> as the probability of reaching <math>n</math> from <math>0</math>. We immediately see that <math>f(0) = 1</math>, and <math>f(1) = \frac{1}{2}</math>, since there's only one way to get to 1 from 0. Just jump!
+Now, let's write an expression for <math>f(10)</math>. Suppose we know <math>f(9),f(8),\dotsc,f(2)</math>.
+The probability of reaching 10 from some integer <math>k < 10</math> will be <math>\frac{1}{2^{10-k}}</math> (use the formula given in the problem!)
+The probability of reaching that integer <math>k</math> from <math>0</math> is going to be <math>f(k)</math>. Then, the probability of going from <math>0 \to \underbrace{ k \to 10}_{\text{one jump}}</math> will be <cmath>\mathbb{P}(\text{Reaching } 10 \text{ from } 0 \text { while passing through } k) = f(k) \cdot \frac{1}{2^{10-k}}</cmath>
+We want the probability of reaching 10 from anywhere though, so what we can do is sum over all passing points <math>k</math>, i.e.
+<cmath>f(10) = \sum_{k=0}^9 \mathbb{P}(\text{Reaching } 10 \text{ from } 0 \text { while passing through } k) = \sum_{k=0}^9 \frac{1}{2^{10-k}} \cdot f(k)</cmath>
+Now that we have expressed our problem formally, we can actually start solving it!
+Let's calculate <math>f(9)</math>.
+<cmath>f(9) = \sum_{k=0}^8 \frac{1}{2^{9-k}} \cdot f(k)</cmath>
+<cmath>\frac{f(9)}{2} = \sum_{k=0}^8 \frac{1}{2^{10-k}} \cdot f(k)</cmath>
+Hmm, we see that the first 8 terms of <math>\frac{f(9)}{2}</math> are exactly the first 8 terms of <math>f(10)</math>. Let's substitute it in.
+<cmath>f(10) = \frac{1}{2} \cdot f(9) + \color{red} \sum_{k=0}^8 \frac{1}{2^{10-k}} \cdot f(k)</cmath>
+<cmath>f(10) = \frac{1}{2} \cdot f(9) + \color{red} \frac{1}{2} \cdot f(9)</cmath>
+<cmath>f(10) = f(9)</cmath>
+Isn't that interesting. Turns out, this reasoning can be extended all the way to <math>f(10) = f(9) = \dotsc = f(2) = f(1)</math>.
+It breaks at <math>f(1) \neq f(0)</math>, since <math>f(1) = \frac{1}{2} f(0)</math>. Anyway, with this, we see that the answer is just
+<math>f(10) = f(1) = \boxed{\textbf{(E)} \ \frac{1}{2}}</math>
+~ <math>\color{magenta} zoomanTV</math>
+==See also==
+{{AMC12 box|ab=A|year=2023|num-b=16|num-a=18}}
+[[Category:Intermediate Number Theory Problems]]
+{{MAA Notice}}

2023 AMC 12A (Problems • Answer Key • Resources)
Preceded by Problem 16	Followed by Problem 18
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 "2023 AMC 12A Problems/Problem 17"

Revision as of 17:23, 9 November 2023

Problem

Solution 1

See also