2
$\begingroup$

Lilypads numbered $1,2,3,\cdots$ lie in a row in a pond. A frog is initially on pad $1$. From any pad $k$, the frog will jump to either pad number $k+1$ or $k+2$ with equal probability of ${1\over 2}$. The probability that the frog visits pad $7$ is ${m\over n}$ where ($m,n$) = $1$, Evaluate $n-m$.

Well I wanted to know as to how to attack this problem. I mean Probability = Number of favorable outcomes / Total Outcomes. What is the total outcomes here ?? What are the favorable outcomes ?? How to count them ??

$\endgroup$
2
  • 2
    $\begingroup$ I suggest working recursively. A good path to $7$ must either be a good path to $6$ followed by one, or a good path to $5$ followed by two. And so on.. If needs be, you can simply enumerate all the good paths that way. $\endgroup$
    – lulu
    Dec 30 '20 at 12:18
  • $\begingroup$ You have a simple recursive relation of $P(K), P(K-1), P(K-2)$ $\endgroup$
    – Math Lover
    Dec 30 '20 at 12:21
4
$\begingroup$

I might be wrong. It's happened before (once).

$P($ reaches pad $7)$ = $1 - P(6 \to 8 \ | $ reaches pad $6)$

$\color{red}{= 1 - \frac12P(\text{ reaches pad 6 })}$ [because assuming it reaches pad $6,$ it has $\frac12$ chance of landing on $8$.]

$= 1 - \frac12(\ 1 - P(5\to7\ |$ reaches pad $5)\ )$

$\color{red}{ = 1 - \frac12(\ 1 - \frac12 P( \text{reaches pad } 5)\ )}$

$= 1 - \frac12(\ 1 - \frac12(\ 1 - P(4 \to 6|$ reaches pad $4\ )\ )\ )$

$\color{red}{= 1 - \frac12(\ 1 - \frac12(\ 1 - \frac12P(\text{reaches pad 4})\ )\ )}$

$ = ...$

$ \color{red}{= 1 - \frac12\left(\ 1 - \frac12\left(\ 1 - \frac12\left(\ 1 - \frac12\left(\ 1 - \frac12\left(\ 1 - \frac12P\left(\text{reaches pad 1}\ \right)\ \right)\ \right)\ \right)\ \right)\ \right)}$

$ = 1 - \frac12\left(\ 1 - \frac12\left(\ 1 - \frac12\left(\ 1 - \frac12\left(\ 1 - \frac12\left(\ 1 - \frac12 \times 1\ \right)\ \right)\ \right)\ \right)\ \right) $

$ = \frac{43}{64}$.

Since $(n,m) = (64,43) = 1,\ n - m = 64 - 43 = 21.$

$\endgroup$
2
  • $\begingroup$ This would agree with David Quinn's method if David Quinn had done it right. $\endgroup$
    – TonyK
    Dec 30 '20 at 13:31
  • $\begingroup$ Also the same answer as jlammy, the Markov Chain guy. $\endgroup$ Dec 30 '20 at 13:34
1
$\begingroup$

It might help to model the process as a Markov Chain (though this isn't necessary).

Let $p_n$ be the probability that the frog hits lilypad $n$. Then $p_n=\frac{1}{2}\left(p_{n-1}+p_{n-2}\right)$, and $p_1=1$, $p_2=\frac{1}{2}$. At this point, you can either pump the recursion for $n=7$, or solve the relation to get $p_n=\frac{2}{3}+\frac{1}{3}\left(-\frac{1}{2}\right)^{n-1}$. Either way, you get $p_7=\frac{43}{64}$.

$\endgroup$
1
$\begingroup$

We can enumerate the number of pads the frog leaps over to get to pad 7:

Case 1$$1+1+1+1+1+1$$ 1 permutation, $p=(\frac{1}{2})^6$

Case 2 $$1+1+1+1+2$$ 5 permutations, $p=5\times(\frac{1}{2})^5$

Case 3 $$1+1+2+2$$

6 permutations, $p=6\times(\frac{1}{2})^4$

Case 4 $$2+2+2$$

1 permutations, $p=(\frac{1}{2})^3$

Total $=\frac{43}{64}$

$\endgroup$
3
  • $\begingroup$ Case 4 should be $p=4\times(\frac12)^4$, I think. $\endgroup$
    – TonyK
    Dec 30 '20 at 13:08
  • $\begingroup$ More importantly, the total distance from pad $1$ to pad $7$ is $6$, not $7$... $\endgroup$
    – TonyK
    Dec 30 '20 at 13:14
  • $\begingroup$ Thanks @TonyK I will fix it $\endgroup$ Dec 30 '20 at 13:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.