AIME 2019 II · 第 2 题

Solution (Probability States)

Let $P_n$ be the probability the frog visits pad $7$ starting from pad $n$. Then $P_7 = 1$, $P_6 = \frac12$, and $P_n = \frac12(P_{n + 1} + P_{n + 2})$ for all integers $1 \leq n \leq 5$. Working our way down, we find

$$P_5 = \frac{3}{4}$$ $$P_4 = \frac{5}{8}$$ $$P_3 = \frac{11}{16}$$ $$P_2 = \frac{21}{32}$$ $$P_1 = \frac{43}{64}$$ $43 + 64 = \boxed{107}$.

Solution 2 (Casework)

Define a one jump to be a jump from $k$ to $k + 1$ and a two jump to be a jump from $k$ to $k + 2$.

Case 1: (6 one jumps) $\left (\frac{1}{2} \right)^6 = \frac{1}{64}$

Case 2: (4 one jumps and 1 two jumps) $\binom{5}{1} \cdot \left(\frac{1}{2}\right)^5 = \frac{5}{32}$

Case 3: (2 one jumps and 2 two jumps) $\binom{4}{2} \cdot \left(\frac{1}{2}\right)^4 = \frac{3}{8}$

Case 4: (3 two jumps) $\left(\frac{1}{2}\right)^3 = \frac{1}{8}$

Summing the probabilities gives us $\frac{43}{64}$ so the answer is $\boxed{107}$.

- pi_is_3.14

Solution 3

Let $P_n$ be the probability that the frog lands on lily pad $n$. The probability that the frog never lands on pad $n$ is $\frac{1}{2}P_{n-1}$, so $1-P_n=\frac{1}{2}P_{n-1}$. This rearranges to $P_n=1-\frac{1}{2}P_{n-1}$, and we know that $P_1=1$, so we can compute $P_7$.

$$\begin{aligned} P_1&=1\\ P_2&=1-\dfrac{1}{2} \cdot 1=\dfrac{1}{2}\\ P_3&=1-\dfrac{1}{2} \cdot \dfrac{1}{2}=\dfrac{3}{4}\\ P_4&=\dfrac{5}{8}\\ P_5&=\dfrac{11}{16}\\ P_6&=\dfrac{21}{32}\\ P_7&=\dfrac{43}{64}\\ \end{aligned}$$ We calculate $P_7$ to be $\frac{43}{64}$, meaning that our answer is $\boxed{107}$.

Solution 4

For any point $n$, let the probability that the frog lands on lily pad $n$ be $P_n$. The frog can land at lily pad $n$ with either a double jump from lily pad $n-2$ or a single jump from lily pad $n-1$. Since the probability when the frog is at $n-2$ to make a double jump is $\frac{1}{2}$ and same for when it's at $n-1$, the recursion is just $P_n = \frac{P_{n-2}+P_{n-1}}{2}$. Using the fact that $P_1 = 1$, and $P_2 = \frac{1}{2}$, we find that $P_7 = \frac{43}{64}$. $43 + 64 = \boxed{107}$

-bradleyguo

Solution 5

Let $a$ represent the number of two-step jumps (hopping over two lily pads) and $b$ represent the number of one-step jumps (hopping over one lily pad). We get the equation $2a + b = 6$, which has 4 integer solutions: $(3,0)$, $(2,2)$, $(1,4)$, and $(0,6)$. For $(2,2)$, there are $\frac{4!}{2!2!} = 6$ ways to permute the jumps, and for $(1,4)$ there are $\frac{5!}{1!4!} = 5$ ways. So we get:

$$\frac{1}{2^{3+0}} + 6 \cdot \frac{1}{2^{2 + 2}} + 5 \cdot \frac{1}{2^{1 +4}} + \frac{1}{2^{0 + 6}} = \frac{43}{64}$$ $43 + 64 = \boxed{107}$

~grogg007

Solution 6 (Rigorous Caseworks)

Let $a$ be the number of 2-unit jumps and $b$ the number of 1-unit jumps. In this context, note that the total distance from 1 to 7 must be $7 - 1 = 6$, yielding the equation $2a + b = 6$ (i) in the process. On the other hand, we must establish a minimum and maximum limit for the jumps; thus, $a + b = m$ (ii), where $m \in \mathbb{Z}^+$. From there, we see:

$\begin{cases} 2a + b = 6 \\ a + b = m \end{cases} \Rightarrow \boxed{S = \{a = 6 - m, b = 2m - 6\}}$

Since $a, b \in \mathbb{N}$, it follows that the interval for $m$ is $3 \le m \le 6$. Therefore, there are 4 cases to consider when the frog jumps. Let's illustrate them:

(i) $m = 3$: We will have $a = 3$ and $b = 0$, indicating that there is only one possible path for it to travel. Thus, the probability is $P_1 = \left(\frac{1}{2}\right)^3 = \frac{1}{8}$.

(ii) $m = 4$: We will have $a = 2$ and $b = 2$, indicating that $\binom{4}{2} = 6$ possible paths for it to travel. Thus, the probability is $P_2 = \left(\frac{1}{2}\right)^4 \times 6 = \frac{6}{16}$.

(iii) $m = 5$: We will have $a = 1$ and $b = 4$, indicating that $\binom{5}{1} = 5$ possible paths for it to travel. Thus, the probability is $P_3 = \left(\frac{1}{2}\right)^5 \times 5 = \frac{5}{32}$.

(iv) $m = 6$: We will have $a = 0$ and $b = 6$, indicating that there is only one possible path for it to travel. Thus, the probability is $P_4 = \left(\frac{1}{2}\right)^6 = \frac{1}{64}$.

Thus, we have:

$\frac{p}{q} = P_1 + P_2 + P_3 + P_4 \implies \frac{p}{q} = \frac{1}{8} + \frac{5}{32} + \frac{6}{16} + \frac{1}{64} \implies \frac{p}{q} = \frac{43}{64}$

Therefore, $p + q = 43 + 64 \therefore \boxed{\mathbf{p + q = 107}}$.

~Fernando Meira

Solution 7 (Recursion)

We can solve this problem by looking at the probabilities of landing on each individual lily pad. Lily pad number one has a probability of 1, lily pad number 2 has a probability of 1/2. We can see from quick casework on lily pad number 3(yielding 3/4) that the probability for any lily pad N is $\frac{N_{n-2}}{2}+\frac{N_{n-1}}{2}$. Quickly working this out, we see that the probability is $\frac{43}{64}$, so the answer is $\boxed{107}$. .

Solution in portuguese

~ Post in instagram for fmeira_math:[1]

Video Solution (2 Solutions)

https://youtu.be/wopflrvUN2c?t=652

~ pi_is_3.14 aka the GOAT Sohil Rathi or Lebron James!!!! go king go!