Can you solve The Frog Problem?
Вставка
- Опубліковано 12 чер 2024
- Check out more fun mathematics problems at Jane Street's Real Numbers.
www.janestreet.com/real-numbers/
If you want to have a guess for a river width of 10 (nine lily pads and the opposite bank) then put your guess with the word "guess" in the comments below. If anyone does work out the average guess: let me know!
If you have a solution: put that below as well. Be sure to like and comments which you think have cracked the problem.
Thanks to Ben Gillott for sharing the puzzle with Timandra.
My show "Humble Pi" had a sold-out run at the Fringe and will now be on tour around the UK. Dates and details: standupmaths.com/shows/
Timandra has a few more dates for "Take a Risk" and also has a podcast by the same name: takeariskshow.com/
Bec Hill is never performing "I'll Be Bec" again but is always doing a million other things: www.bechillcomedian.com/
Rob West will be on tour with "Morgan and West: Unbelievable Science" as well as about a dozen magic shows: www.morganandwest.co.uk/live-d...
Git your code here! github.com/standupmaths/frog_...
We have Think Maths "Frog Jumps" resources for maths teachers.
think-maths.co.uk/standupmaths...
CORRECTIONS
- None yet, let me know if you spot anything!
- Oh, and this is not really a correction, more of an explanation, but you can see some dark stains on my hands in some shots of this video. That is because I helped Morgan and West load their science show out of the theatre at the end of the Fringe and my reward was to get silver nitrate on me.
Thanks as always for Jane Street being my principal sponsor.
www.janestreet.com/
Thanks to my Patreon supporters who help make these videos possible. Here is a random subset:
Bruce Patterson
Glenn Watson
Matthew Holden
Patrick Thiel
Adam Scatchard
William Marple
Support my channel and I can make more maths videos:
/ standupmaths
Filming by Matt Parker
Editing by Alex Glenn-Bash
Music by Howard Carter
Design by Simon Wright
MATT PARKER: Stand-up Mathematician
Website: standupmaths.com/
Maths book: wwwh.umble-pi.com
Nerdy maths toys: mathsgear.co.uk/ - Розваги
![Recursive PowerPoint Presentations [Gone Fractal!]](http://i.ytimg.com/vi/b-Fa6HtvGtQ/mqdefault.jpg)
Matt uses a light themed IDE. That's all you need to know about Matt.
Light theme is better
@@sam2026 brave
All you need to know about him is that he doesnt want to ruin his eyes from using dark mode when surrounded with plenty of light? nah you also need to know about this thing called a Parker Square. . . .
You're a modern day hero.
Wyatt Sheffield /r/unpopularopinions
Why did the frog cross the river 10,000 times? To avoid a probability quiz.
let's add our beloved usual scorpion, it will be more fun... e.g. "frog in a fog", can't see anything, with unknown number of (say equally spaced) leaves to jump - and that carried scorpion is quite odd, so it strikes (and kills the frog) only when the last jump is an odd one (i.e. making the one very long jump a deadly option)... what's the best strategy? (or if it is too easy, then our scorpion is an prime mathematician and stays quiet only when the last jump is a PRIME (bigger than one)
Truth: I was out driving the other day and happened to see in my rearview mirror a chicken crossing the road behind me. I thought, "Who knew they actually did that?"
@@theRealPlaidRabbit did you ask?
the frog crossed the river 2520 times
@@evinliang9814 I made a giant excel spreadsheet to solve up to 1000 lilypads, meaning my frog may have crossed the river 1,000,000 times every time I run it?
Initial reaction: "It's obviously 3"
Make a simulation of just one iteration: get 3.
Leave satisfied
Fall-back plan: Hit the button a couple of times until you get three.
I glanced at your avatar and instantly teared up...
@@pilattebe I've done this. When code testing is more important than immediate results. (Which, come to think of it ...)
It's really important to change it back BEFORE you start running simulations. But it's a really easy error to catch.
strange, my guess was 3 or 4... without even thinking about it...
i wonder why 3 would be so "obvious"...
The answer is the harmonic numbers (a_n = \sum_{i=1}^n{\frac{1}{n}})
Proof: Let a_n be the total number of jumps needed. We are looking for a value for a_10 and a formula for a_n. To jump n leaves the frog does one of the n possible jumps with probability 1/n to any leaf i and then has to jump a number of n - i leaves in a_{n-i} ways.
Thus, we get the recurrence relation: a_1 = 1; a_n = 1/n + 1/n(a_1 + 1) + 1/n(a_2 + 1) + ... 1/n(a_{n-1} + 1) where each +1 comes from the initial jump.
After some algebra, the recurrence is: a_1 = 1; a_n = 1 + 1/n \sum_{i=1}^{n-1}{a_i}. From here, try to get a_n in terms of a_{n-1}:
a_n = 1 + 1/n * (n-1) / (n-1) * \sum_{i=1}^{n-1}{a_i} # multiply by x/x doesn't change result
a_n = 1 + (n-1) / n * (1 / (n - 1)) * \sum{i=1}^{n-1}{a_i} # reorder factors
a_n = 1 + (1 - 1/n) * (1 / (n - 1) * \sum{i=1}^{n-2}{a_i} + a_{n-1} / (n - 1)) # extract the last term of the sum
a_n = 1 + (1 - 1/n) * (a_{n-1} - 1 + a_{n-1} / (n-1)) # use the same formula from the start but for a_{n-1}
a_n = 1/n + a_{n-1} # expand all parantheses, do algebra
But that with a_1 = 1 gives a_n = \sum_{i=1}^n{\frac{1}{n}}, the harmonic numbers.
And indeed, even experimenting we get to the same solution: a_10 = 2.92880931.
I used the following script to simulate:
import random
PRINT_EVERY = 100000
def jump(end=10):
pos = 0
ret = 0
while pos != end:
pos = random.randrange(pos, end) + 1
ret += 1
return ret
sum_jumps = 0
num_tries = 0
while True:
for _ in range(PRINT_EVERY):
sum_jumps += jump()
num_tries += 1
print("Avg {:.8f} ({} / {})".format(
(sum_jumps + 0.0) / num_tries, sum_jumps, num_tries))
And it prints:
...
Avg 2.92880365 (366686217 / 125200000)
Avg 2.92880069 (366978727 / 125300000)
Avg 2.92880195 (367271764 / 125400000)
Avg 2.92880530 (367565065 / 125500000)
Avg 2.92880385 (367857764 / 125600000)
Avg 2.92880500 (368150789 / 125700000)
Avg 2.92880931 (368444211 / 125800000)
I'm thus confident that the solution above is real and works.
I got the same answer but I used expected value
I got the same answer as well.
I just got there too, great job!
He said 10 landing places not lillys, you did it with 11 landing places.
the answer is way eaiser and simple ... if u got 10 steps then each step would either be landed by the frog or skipped .the answer is 2×2×2×2×2×2×2×2×2×2
or simply 2^10
i already tried this method manually with 2 , 3 , 4 and 5 steps and the results perfectly matchs so
the equation is 2^n (n=number of steps)
If there are 0 places in front of the frog, we are already at the end E[0] = 0. If there are n places in front of the frog, then for each of the places (on which we land with probability 1/n) we have the expected number of jumps from there, plus the one jump to get there from the current position.
E[n] = 1 + 1/n sum (i=0..(n-1)) E[i]
Similarly, if there are n-1 places in front, we have:
E[n-1] = 1 + 1/(n-1) sum (i=0..(n-2)) E[i]
If we scale them appropriately and take the difference, we get: n E[n] - (n-1) E[n-1] = n - (n-1) + E[n-1]
Solving for E[n], we obtain: E[n] = E[n-1] + 1/n
This recurrence relation is immediately recognisable as the harmonic series sum (i=1..n) 1/i = 1 + 1/2 + 1/3 + 1/4 + ... + 1/n. The partial sum of this has no closed-form formula. For n=10 though we get the 10th harmonic number which is 7381/2520. It's well known that the harmonic series does not converge, but its growth is incredibly slow. The harmonic numbers can be approximated by ln(n) + 0.5772156649 (where this 0.577... is the Euler-Mascheroni constant). So even with 12000 lily pads there will less than 10 jumps on average. And with 1.5×10⁴³ lily pads there are less than 100 jumps on average.
I also got the partial sum of the harmonic series in a similar way. It was less obvious because I initially expressed it as
E[n] = (1/n)S[n], where S[n] = ((n+1)/n))S[n-1] + 1
but I eventually got there by rearranging the terms in the series to get
S[n] = n!/(n-1)! + ((n!/2!)/((n-1)!/1!)) + ((n!/3!)/((n-1)!/2!)) + .... + ((n!/(n-1)!)/((n-1)!/(n-2)!)) + ((n!/n!)/((n-1)!/(n-1)!))
and then simplifying.
(Hope I didn't make any mistakes copying it over, I wasn't really using proper notation on my scratch paper.)
Nice! I got the exact same solution in a few minutes, but I didn't double check it. But the top comment is always right isn't it? So I'll just accept this as confirmation :)
Edit: wait, this isn't top comment? Is UA-cam lying to me?
That was much easier than my approach, thanks.
I did the exact same thing you did, ended up with the same result: harmonic series. It is so satisfying when you find that kind of stuff by yourself!
@@dominiquefortin5345 But... 1.5 is indeed the second term of the harmonic series (E[2] in the notation above).
The obvious starting point was to solve via recursion. Since landing with any number of pads remaining is the same as a problem starting with that many pads.
For n possible spots, the answer is 1 (the frog must hop once now) plus 1/n * the solution for each smaller problem of i steps between i=1 and i=n-1 (the pads it might land that would require a further solution).
But recursion is inefficient. Solving the same problem multiple times is often unnecessary. That's the case here were we just need to know the solution for each smaller n down to n=1. Instead of recursion, we can just keep a list of previous solutions as we work up. So f(n) = (f(1)+f(2)...f(n-1))/n +1
But again, we don't need each individual solution, just the running sum of solutions. And that sum is ingrained in each solution, so we don't need to keep a separate running total. We just need to know the values of n-1 and f(n-1). We just squash f(1)+f(2)+...f(n-1) into a variable for the running sum r, we get f(n)= r/n+1, and from that can see that r= n*(f(n)-1). Plug that in to get the old running sum from f(n-1) and we get
f(n) = (f(n-1)+((n-1)*(f(n-1)-1)))/n + 1
Simplify
f(n) = (f(n-1)+(n-1)*f(n-1)-(n-1))/n + 1
f(n) = (n*f(n-1)-n+1)/n + 1
f(n) = f(n-1) - n/n +1/n + 1
f(n) = f(n-1) + 1/n
Which is kind of amazing. That's the algebraic notation for the harmonic series. The frog problem is the harmonic series. (n=10 is 7381/2520).
But knowing that it is the harmonic series, we need to re-examine the problem to find the real beauty here. There is a 1/1 chance that the frog reaches the far bank eventually. But there is also a 1/2 chance that the frog visits the last lily pad along his journey. Which makes sense. At any step, no matter how far back the frog is, there are equal chances of landing on that pad or skipping it to the end. There are also chances of landing on a pad before it, but those chances don't matter since no matter where else the frog lands, a jump from that spot also holds to the equal probability of landing on or skipping the last pad. And this continues. For the pad before that, there are 2 chances to skip it and 1 to land on it. 1/3 odds that pad is visited. 1/4 for the pad before that, then 1/5, 1/6, etc. All a clever disguise for the harmonic series in probability.
I did the exact same thing except I included f(0) in the sum, so f(0)+...+f(n-1) and I used sigma notation instead of r, allowing me to isolate the sum, add one more term, and show f(n) + 1/(n+1) = f(n+1). With f(0)=0, f(n) = sum of 1/k from 1 to n
@@anthonyl3065 but why exactly would you need f(0) in this problem? I know it's the classic engineer vs. mathematician dilemma here but 0 is clearly not in the domain.
Eric Marcel I included f(0) because of how I considered the recursive function. I thought about it as the average of f of how many pads left. So on the first move it can jump 1 to n so the pads left are 0 to n-1. As for 0 not being in the domain, it is. Conceptually that means the frog starts where it wants to end, which makes f(0)=0. It also follows the harmonic series as the sum of 0 elements is 0. Of course you can ignore f(0), but personally I find the reasoning more consistent.
That's about what I did as well though I also would use sigma notation for a final solution, and my guess was sqrt(10) so I was only 7.38% off, but I suppose I'll be beaten by everyone who guessed 3 and was only 5.1% off. Also, I did this in only 30 min, and wasn't really trying to go fast. Kinda surprises me that Matt and co didn't solve this while still at the bar.
Ok, lets go with that.
P.S. what did that mean?
My initial guess was that it'd be a little bit over 3, because on average it jumps halfway so you'd expect somewhere around log2 of the number of starting jumps.
Only just seen this puzzle; I wrote a 24-line BBC BASIC program (BEEBEM emulation as a Master 128), and ran it with different loop options e.g. 10 times, 100 times etc. The run of 100,000 times consistently gave an average number of steps between 2.92 -> 2.93 steps per river crossing. The execution time was approximately one hour for each 100,000 loop.
Program available for anybody interested. Let me know via this link.
That's what I thought as well, a couple of seconds after I heard the full description of the problem. However since the end pad is separate I think the general formula is log2(n+1).
Since I'm not a real mathematician, I can't be bothered to actually make a proof though 😅
@@hls6925 Similarly I wrote a javascript simulation of it and let it run a few million times and got an average of about 2.929
@@crjtodd Sounds about right, Chris! BTW how long did your JS run for? Bit faster than my Basic, I'll bet!
I went nearly crazy with this problem until I finally realized it's just the harmonic series... Wow, that was a lot of hours to in the end get to such a simple answer. If it wasn't for your Parker Square video, I might have given up or not even tried though, so thank you Matt.
Somebody else has already posted their answer (much quicker than me) but I'll just write it the way I worked it out (very similar though): Let S(n) = Sum (E(i)), i=1,...,n-1.
Then E(n)=1+1/n * S(n) = 1 + E(n-1)/n + 1/n * S(n-1) = 1 + E(n-1)/n + (n-1)/n * 1/(n-1) * S(n-1) = 1/n + E(n-1)/n + (n-1)/n * (1+1/(n-1)*S(n-1)) = 1/n + E(n-1)
So with every increase of n by 1, we increase E(n) by 1/n, which means E(n) is just 1+1/2+1/3+1/4+...+1/n, i.e. the partial sum of the harmonic series up to the nth term.
@@yagoduppel
So for us not math guys what is the answer for 10 lily pads?
@@presto709About 2.93. So 3.
Problem: ...and do NOT use recurrence relations.
Parker Solution: So I used a recurrence relation.
Technically it was stated that a recurrence relation would not suffice as an explicit formula. Too bad there is no explicit formula for this.
@@alcesmir "Too bad there is no explicit formula for this." Why do you think so? It was already stated in the comments, that the explicit formula is Σ(1/n).
@@GnI1991 I think what alcesmire meant was closed form. like how the summation of an algebraic sequence is n/2(first+last)
@@GnI1991 Yeah, sorry. I meant closed form. It's not that uncommon to use the term explicit formula to mean closed form, but it's probably better to use the more specific term.
10/[1+e] , the general is n/[1+e]
"import random" inside a while loop, that's some classic Parker Python Programming
It won't repeat the import. But it still has to interpret that line of code so you are wasting a few clocks every time
@@myselfremade If you're programming as high level as python, it doesn't really matter how many cycles you wasted, especially for a not so important thing.
@K.D.P. Ross "What a brilliantly designed language"
Well, I think it is, just not in the way you mean. It's brilliantly designed, because it will let someone at Matt's level of knowledge quickly program a thing like this, and have it do exactly what he needs it to do.
I think that is something to be appreciated. But yes, from a language theory point of view, it leaves much to be desired.
@@BoyKissBoy Exactly. Python is a brilliantly designed language for throwing maths and science together. I spend my days writing Rust and have grown to think of it a s brilliantly designed (currently with rough edges) but at no point did I consider reaching for rust when checking my solution! I used to write an awful lot of perl for this so appreciate python's brilliance in this area!
You: Jumping hurdles
I, an intellectual: *_AUTOFROG ENABLED_*
I want an AUTOFROG ENABLED bumper sticker
Matt: Uses python, the king of languages for quick and dirty solutions.
Also Matt: Does analysis in Excel
Well I do feel dirty after having used it, so they fit together.
Not a great choice for simulations given how slow it is.
@@lokedhs Yep. Performance is of the utmost necessity in this instance.
@@lokedhs You can use numba to get some extra performance out if you really need it, but I'm not about to break out Fortran for a frog hopping problem!
Uhm, excuse me, Haskell is amazing.
*Python:*
from random import randint
def jump(s):
s = s - randint(1, s)
return 1 if s==0 else 1 + jump(s)
def doTests(width, loops):
res = 0
for i in range(loops):
res += jump(width)
print("{}: {}".format(width, res/loops))
for i in range(1, 11):
doTests(i, 100000)
*Haskell:*
jump s = 1 + sum [ jump n / s | n
The expected number of jumps required to get to pad 'n' will be, I think, the sum of the harmonic series Hn=Σ(1/n). Matt's simulation also seems to give that result. Here's why I think that's the case:
For n=1, number of expected jumps is, trivially, one.
For n=2, initially the frog has an equal probably of jumping on both pads, thus assigning them a score of half. This means that the frog will jump on each pad 0.5 number of times. Then, on the next step, if it's on pad 2 and not the final pad, expected number of jumps is, again, 1. Thus, total for the last pad is 1+1/2
For n=3, it's 1/3 for the first pad, 1/2+1/3 for the second and 1+1/2+1/3 for the final pad.
For the general case, the total is Σ(1/n)
Edit: I think what I did is a Markov chain.
Thus, for n=10 it's 2.92897
I did it by working back from a recursive relation and got the same answer.
UA-cam comments are not great for math
f(N) = (sum from k=1->N-1 (1+f(k))/N )+ 1*(1/N) (there is an equal chance to jump to any lilypad, or the bank f(k) is the answer for the lilypad k away from the bank (1 jump there plus answer previously calculated), and a 1/N chance to jump to the final space. N is number of spaces to the end.
f(N) = (sum from k=1->N-2 (1+f(k))/(N-1))*((N-1)/N) + (f(N-1)+1)/N = (f(N-1)*(N-1) + (f(N-1)+1))/N = f(N-1)*N/N + 1/N = f(N-1)+1/N
f(N) = sum from k=1->N (1/N)
@@soumilshah1007 This is about the same answer as I'm getting with my simulation. Nice!
I've got 2.929036 through simulation 1 million frogs. That sounds believably correct to me :)
@@tommywareing9234 nice, close enough.
It's the harmonic series.
Let E(n) be the expected number of jumps in where the frog has n possible spaces to jump to at the beginning. (i.e. n-1 lotus leaves and 1 spot for the opposite bank).
There's a 1/n chance that the frog jumps to the very next leaf, which takes another E(n-1) steps to finish.
There's a (n-1)/n chance that the frog jumps to any other spot, which is the same as taking one jump from the very next leaf, since both result in the next jump being to those spots with a uniform probability.
E(n) = 1/n * (1 + E(n-1)) + (n-1)/n * E(n-1)
E(n) = 1/n + E(n-1) / n + (n-1)* E(n-1)/n
E(n) = 1/n + E(n-1)
Putting in E(1) = 1, we get E(n) = 1/n + 1/(n-1) + 1/(n-2) + ... + 1
So yeah, E(n) is exactly the nth partial sum of the harmonic series. It grows like a harmonic series and quacks like a harmonic series.
Exactly!
I worked it out and my numbers were consistent with the harmonic seqence+1, but my f(5) value wasnt. but i reworked it and saw that it is consistent. Good job.
We all know frogs go "La di da di da"
I'm not a mathematician, so please excuse me if I'm asking stupid questions, but that harmonic series thing looks to me like it's recursive? (Not saying it's invalid or anything, just wondering if it's a solution within the restriction of "no recurrence", because I want to learn.)
And regardless: Thanks for sharing!
I did not expect to see an obscure DJ TECHNORCH username in the middle of my math puzzle binge.
I had the same solution too. You might be me from a parallel universe.
I think it's important to figure out what is on the other side. What's the frog's motivation? Is it trying to be stealthy? Is it trying to get to a potential mate before a larger more attractive frog does? Did he wake up late and is rushing into work? I think we need to go deeper into this issue.
5:48 Bec's scrawling reminds me SO much of me, aged about 12, writing out all the possible games of noughts and crosses in a small notebook. Haha!
I'll try with real frogs. Simulations are not precise enough. 😂
I'm happy with my spherical frogs
I know righy😂hopefully you have frogs around
@@mokopa in vacuum?
The formula is simple: 1 + 1/2 + 1/3 + ... + 1/n, if n is the number of options on the first jump (n-1 leaves in the water). The proof: it's obvious for n=1. only one option: one jump; e(1)=1. To go from e(n-1) to e(n), consider this: The chance of jumping to the first leaf is 1/n. From there, the situation is exactly the situation as for n -1, so The expected number of jumps is exactly one more (that first short jump) than the number of expected jumps for n -1. For the remaining case of not jumping to the first leaf (which happens with the remaining probability: (n-1)/n), you have the exact situation as for n -1 with the same expected number of jumps. So taking the weighted average, you get e(n)=1/n (1+ e(n-1)) + (n-1)/n (e(n-1)), which resolves to the pretty formula above. Correct, right? Does it match your experimental data?
@@pilattebe Haha RIGHT!
I'm going with 3. Because that seems right based on the frogs in my head.
that's pretty damn close to what people calculated using Python of 2.928968.... for n=10
I was thinking that it was 3
@@xander1052 The exact value is in fact, 7381/2520 = 3 - 179/2520 = 2.928[968253], where the bracketed part repeats ad infinitum. [ It's ∑[k=1..10] (1/k) ]
A very good rational approximation is 41/14 = 2 & 13/14.
In fact, the exact answer is 41/14 + 1/2520.
Fred
After working this out with my favorite math software, Microsoft Paint, my guess is 4. I wish I could upload my glorious image here, but a boring old number will have to do.
I got the same answer as Binary Agenda, going kind of backwards. First I computed the recurrence relation (same one Matt found) and computed its values. I graphed it and it looked like it was growing logarithmically, and with a little playing around I found it was growing like ln(n) + something. Looking at this difference at n=1000 to get a good estimate for something I found it was 0.577. I recognized 0.577 as a special thing but I couldn't remember what it was! I tried wolfram alpha, which is usually good for giving nearby closed forms for numbers, to no avail. (ln(sqrt(pi)) was my best guess, but it wasn't quite hitting)
Anyway... I just relaxed my mind a minute and thought, out of nowhere, we're dealing with fractions! The harmonic numbers (1/1 + 1/2 + 1/3 + ... + 1/n) grows logarithmically and is a bunch of fractions. So I tried it and it matched exactly. From there it wasn't too hard to prove that the harmonic numbers satisfied this recurrence relation, without using anything too advanced. (But not as elegantly as Binary Agenda)
And of course after this I realized what 0.577 was! The Euler-Macheroni constant -- which is *defined* as the limiting difference between the n'th harmonic number and ln(n). It's definition is exactly the context where it showed up in this problem. Why didn't wolfram alpha catch that! Come on, that's an important one! log(sqrt(pi)), really?!
Anyway, fun problem! I like problems like this where I have to use a combination of empirical investigation and formal thinking to get it. Also kudos to Binary Agenda for their elegant solution.
BTW the exact solution for 10 is 1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 + 1/7 + 1/8 + 1/9 + 1/10 = 7381/2520 = 2.928 968253 968253 ...
No, it’s 4.2.
Oh man. With the end of that simulator, I really hope that the answer for 10 just ends up being Pi for some crazy reason.
My guess is that it would be root 10
My bold claim is that the average number of jumps needed is Pi for any number of water lilies.
Pi does seem to love to pop in on random fields of maths every once in a while, so I'm going to second this.
I was about to say that! hope it is pi!
The number of jumps would be an integer, there's nothing like a 0.1415926... leap. So that would finally prove that pi is exactly 3. 🤐
My guess is: e
This number always appear somewhere where it isn't supposed to
My first answer was “the answer to these questions is always e or 1/e”.
Came out to be 11/6 for 2 lily pads. Shouldn't be e or 1/e or related. It's probably a polynomial in n
@Chris I havent proven it yet but it seems to me, that the average number for n lilly pads is 1 + 1/2 + 1/3 + ... + 1/n . So it doesnt tend to pi
@@standupmaths my guess is pi
@@Paul-rv3rm same result here.
it looks more like e
Thank you for sharing your code and keeping it up years later. It's always helpful.
The answer is: integral from 0 to 1 of (x^10-1)/(x-1) = 7381/2520
That's spot on with the number I get when building it up recursively. Nice one. How did you get this result?
@@jimmythewig3354 I worked it out from the harmonic series posted by others: 1/1+1/2+1/3+...1/10. One way to get that division is through integration of a power of x: I knew that the integral of x^n is x^(n+1)/(n+1). So I thought perhaps the series can be evaluated as x^1/1+x^2/2+x^3/3...+x^10/10 with x set to 1. Working backwards, that expression is the integral of x^0+x^1+...+x^9. Setting the limits to 0 and 1 gives the right value since the first polynomial evaluates to zero when x=0. Playing around a bit allows this second polynomial to be simplified by multiplying by (x-1) giving x^10-1 since all the powers in between cancel. [It's useful to set x=10 to see how this works: (10^10-1)/(10-1) = 9999999999/9 = 1111111111 = 10^9+10^8+...+10^0] So that means the second polynomial is (x^10-1)/(x-1).
@@GeekyNeil I think this vid overhyped the problem. I think of it as at x away from destination, there's a 1/x chance of spending 1 turn to go to position x-1, and a (x-1)/x chance of spending 0.
The expected number of jumps to cross a river of width n is the nth harmonic number, the partial sum of the first n terms of the harmonic series, 1 + 1/2 + 1/3 + ...
The way I think about it goes like this:
Let J(n) be the expected number of jumps to travel a distance n.
1/nth of the time the frog jumps 1 pad and the average number of additional jumps to reach the bank is J(n-1). The remaining (n-1)/nths of the time, the first pad is effectively skipped, so the total number of jumps needed is J(n-1).
This gives J(n)= 1/n (1+J(n-1)) + (n-1)/n J(n-1), which simplifies to J(n) = J(n-1) + 1/n.
As J(1) = 1, this gives the harmonic numbers.
For the 10-wide river, the expected value is 7381/2520 = 2.928968254
This came to me (and I assured myself it was correct) through realising that all the possible ways for the frog to cross the river amounts to finding an ordered sequence of positive integers summing to n, i.e. the compositions of n ( en.wikipedia.org/wiki/Composition_(combinatorics) ), and finding a bijection between the compositions of n and the n-1 digit binary numbers - let the digits represent the lilypads and a 1 represent that pad being jumped on, so 0000 corresponds to jumping straight across a river of width 5, while 1111 corresponds to crossing the same river jumping on every pad. This gives a way to order all the possibilities that I found quite helpful.
Yep, OESIS A001008 divided by OESIS A002805.
it's a matter of subsets indeed
But if the frog jumps half then a third then a forth, etc, then he will never actually reach the other side.
@@stephenbenner4353 I'm not saying that the frog crosses in the those steps, but that the expected numbers of jumps are the partial sums of the harmonic series, and as the frog can only take positive integer jumps, it will cross a river of width n in a minimum of 1 jump and a maximum of n jumps.
Additionally, the harmonic series diverges - if you keep adding terms, the partial sums will increase without bound:
The terms between 1/2^(n-1) and 1/2^n are all >= 1/2^n and there are 2^(n-1) of them, so their sum is at least 2^(n-1)*1/2^n=1/2. The sum of the harmonic series is thus greater than the sum of an infinite number of 1/2's, which is self-evidently a divergent series, and so the harmonic series is itself divergent.
Sam Middleton I was assuming the frog’s name was Achilles, but then there wasn’t a tortoise in the equation. Your working out reminded me of Zeno’s paradox, but of course we know that Zeno’s paradox is false.
My guess is 3
Just feels like 3, of course, that being rounded to the nearest whole number
I was thinking the exact same thing
I started with 3, but that seems to high, so I'm going with e. Just intuition.
@@matthewjohnson3610 I ran 1 billion rounds and got a stable 2.9289
@@precumming I calculated it and you are right. It's 2.928968254
Based On The Results In The Video I'd Probably Put It Around 2.5-2.75, 2 And 3 Seemed The Most Common Results.
Summing the averages going to the next landing location from each position, in turn, should add up to the total average?
1/10 + 1/9 + 1/8 + 1/7 + 1/6 + 1/5 + 1/4 + 1/3 + 1/2 + 1
That's what I was going to say. You beat me to it.
My first attempt at this was to note the recursive solution that if we denote the average number of hops for the n step problem as avg(n), then this is equal to 1 for the first hop plus a 1/n chance of each of avg(i) for i=0 to n-1 for the i steps remaining after the first hop. But then you can readily turn this into an equation for avg(n+1) in terms of avg(n): avg(n+1)=(n(avg(n)-1)+avg(n))/(n+1) which quickly simplifies to avg(n+1)=avg(n)+1/(n+1). Noting that avg(0) = 0 then we have that avg(n) = 1 + 1/2 + 1/3 + ... +1/n. For the 10 step problem this works out to be an average of 7381/2520 hops.
With some tedious calculations by hand an interesting pattern emerges:
The fraction can be expressed as the unsigned stirling numbers of the first kind (A000254) of n divided by n!
1/1 (or 1/1!)
3/2 (or 3/2!)
11/6 (or 11/3!)
25/12 (or 50/4!)
137/60 (or 274/5!)
49/20 (or 1764/6!)
363/140 (or 13068/7!)
This function is given as a(n)=n*a(n-1)+(n-1)!
so the function we are after can be written as c(n)=a(n)/n!
as a bonus here is a small c program to compute it:
float c(int n){
return (float)a(n)/factorial(n);
}
int a(int n){
if(n==0) return 0;
return n*a(n-1) + factorial(n-1);
}
int factorial(int n){
int r = 1;
for(int i=1;i
This isn't too hard to prove with generating functions: Let P(n, t) is the g.f. for the probability that it takes k steps. If P'(n, t) is the same restricted to the case where the first jump is 1 then P'(n, t) = (t/n)(P(n-1, t) and if P''(n, t) is the same restricted to the case where the first jump is >1 then P''(n, t) = ((n-1)/n)(P(n-1, t). Add these to get the recursive formula P(n, t) = (t+n-1)P(n-1, t)/n. An easy induction then gives P(n, t) = (t/1)((t+1)/2)((t+2)/3)...((t+n-1)/n). The numerator is the g.f for the Sterling numbers and the denominator is n! You can get the expected value as a partial sum of the harmonic series (found by numerous other commenters) using logarithmic differentiation on the g.f. I like the way the problem is presented; no solution or even hints but a look at how people actually tackle something like this. Lot's of arcane diagrams and formulas, dead ends and mistakes being scribbled out, and the feeling of accomplishment when all that results in an answer, that's where the fun is, not the dry exposition you get in classrooms and textbooks.
I also discovered this same expression, using A000254.
Guess: log base 2 of 10
Because on average, it’ll go to 5, then 7.5, then 8.75, etc
It can’t be an irrational number. There is a finite number of ways it can get to the end and when you calculate the expected value you’re going to be adding up number of jumps with their associated probabilities. All the probabilities are rational because there is a finite number of ways of getting to the end (a little hand wavey but you get the idea)
If you average out your first two jumps there you get an average jump distance of 3.75. Goal would be achieved or exceeded in 3 jumps. The problem with this answer is assuming that the second jump has a max value of 5 and not 10. If it is 10 the answer would be a 2 jump average.
Im going with 3 since it makes my brain happier.
When you add an Nth space at the front of the queue, it has a 1/N chance of adding 1 to the number of hops taken. So this is the harmonic series.
Genius. The frog has n spot in front of it. That means it has a 1/n chance of jumping to spot n and an (n-1)/n chance of not. In the former case, the expected jumps is 1+a_n because it gets to the nth spot having already done one jump. In the latter case, the expected number of jumps would be a_n because the situation is identical to one in which the frog started at the nth spot. Thus a_(n+1) = 1/n * (1+a_n) + (n-1)/n * a_n = (1 + a_n + n*a_n - a_n)/n = a_n + 1/n.
For a general way to solve this kind of problem in a quick and dirty way : this is a markov chain with an exit condition on reaching the end, build the corresponding transition matrix, calculate the probabilities of getting to the end after exactly n iterations by computing the transition matrix powers, compute the expectation.
For an exact solution in python use the fraction module, for the stated problem you get 7381/2520 (computable because the transition matrix is nilpotent).
thanks for this!
Ben Gillot sounds like penn Gillette in disguise
Even Penn Gillette doesn't believe in magic so every problem does have solution.
It's Penn Jilette
Thanks. I knew something was wrong and I couldn't figure it out so I guessed
I'm glad I'm not the only one who immediately jumped to that.
Penn Gillette, the best a man can get
Auto frog mode enabled.
Don't know why I found this so funny
Autofrogs fight the evil forces of the Deceptitoads.
@@RFC3514 Lol, just waiting for the live action
My code is giving me 2.9... consistently at 10,000 iterations. The second decimal digit is a 2 most of the time at 100,000, but sometimes it is 3.
congrats youre basically right
exactly the same for me, 2.92 with the second decimal being 2 most of the times
Thank you.
I'm getting similar results at 1million iterations. 2.930, 2.929 so I think my code is working, strange feeling.
For a general solution, based on my knowledge of recurrence relations from CS classes:
H(n) is the expected number of crosses if n is the number of lily pads in between (ie, the example shown is H(8).
H(0) = 1 (since the frog will only need one hop).
From any starring position, the frog will do one hop to any pad, then do the expected number of hops from that, so H(n) = 1 + (H(n-1)+H(n-2)+...+H(1)+H(0))/n= 1 + ([S i 1 n-1]{H(i)})/n. (Sorry about the weird summation notation.)
Now compare that to H(n-1), which is 1 + ([S i 1 n-2]{H(i)})/(n-1). We can make these into common terms to get rid of the infinite sum; nH(n)=n+H(n-1)+H(n-2)+...+H(1)+H(0), while (n-1)H(n-1)=n-1+H(n-2)+...+H(1)+H(0). Subtract one from the other, and we get nH(n)-(n-1)H(n-1)=1+H(n-1), so n(H(n)-H(n-1))=1, so H(n)=H(n-1)+1/n.
Thus, H(1) = 1/1, H(2) = 1/1+1/2, and H(n) in general is the sum of the reciprocals of the integers from 1 to n, which some people will remember as the harmonic series.
but does the Frog know that it lives in a simulation??
but don't you know that the frog lives in a simulation inside a simulation??
:) everything makes sense now
It's the sum of the harmonic series!
Proof: Say there are n lilypads total. After the first jump, the frog must be in one of the following scenarios:
A: It is on the very first lilypad. (With probability 1/n)
B: It is on one of the other lilypads. (With probability (n-1)/n)
The first case reduces to the case for n-1 lilypads, but plus a jump. So we can say that E(A) = 1+E(n-1)
The second case, if you think about it, is the same as if the frog had been in an n-1 lilypads situation, but had already taken a jump. We then get E(B) = E(n-1).
E(n) = E(A)/n+ E(B)*(n-1/n) = 1/n + E(n-1).
And E(1) is trivially 1.
Unfortunately, there are no close-formed solutions to the sum of the harmonic series, so the original question can't be solved as intended. Do have an explicit value for E(10), though! which is 2.92896825396825.
MsErfwe same result with my simulation on Python that explore every possible combination of the jumps of the frog! I think is correct!
Actually 3.019877. Since you start off with 11 possible positions to jump (10 lily pads and the opposite shore), you would need to look at the eleventh harmonic number instead of the tenth.
For demonstration, with zero lily pads, the crossing will always be a single jump (the first harmonic number) and for one lily pad it will average 1.5 jumps (the second harmonic number).
@@MWSin1 No, the video is asking for the answer for 10 positions. That's 9 lilypads + the opposite shore.
@@OrchidAlloy You're right. I somehow misunderstood the way the question was presented.
This is what I initially came up with before I took into account the shifting of probabilities. The frog doesn't choose randomly between all possible paths though, it only chooses randomly from its current options:
Every time you add a Lily pad the frog has two options for each sequence of jumps for one less pad. Either add it as a new jump or combine it with the following jump. The average jumps for N+1 pads equals the average for N jumps plus 1 plus the average for N jumps plus zero (no additional jumps if you combine it with the next jump) all over 2. Rearranging you get twice the average for N pads plus 1 all over two or more simply the average for N pads plus a half. If the frog starts out on the pad before the bank it has one way of getting to the bank and that's in one hop. A(1)=1, A(n+1)=A(N)+1/2, A(N)= (N+1)/2
Working on an actual solution now involving adding up reciprocals of permutations of products times the number of terms in that permutation.
I'm so happy, I finally happened to be in the mood and have the time so I figured it out, generalized, and then wrote code to find an answer. Took me a while but I arrived at what I think is actually correct!
E(1)=1 because the frog only has the choice of jumping to the end.
{E(n)= E(n-1) + 1/n} because if we put the extra lilypad right in front of the frog then the frog has a (n-1)/n chance of ignoring the lilypad that leads to an expected amount of jumps that is E(n-1) and a 1/n chance of going in that exact lilypad with an expacted amount of jups of 1+ E(n-1). With a bit of probability you can easily work out the formula between the parenthesis and you can show by induction that E(n)=1+1/2+1/3+...+1/n
It is simple and feels right and I also checked for 3 Lily pads, it's 11/6 =[1+½+⅓] so yeah, should be correct.
@@punya1621 idk if there's a nice closed form
There is, if you use Markov chains and calculate the n-step transition matrices (I've written a much longer comment with the math and a link to a spreadsheet showing the solution)
Was in Edinburgh for the first time in my life and got the information about your show afterwards 😭😭 would have been great to see you live as it might have been the only chance
What are you dying?
Dank Squidge Perhaps he lives far from anywhere Matt has toured his show, or maybe he is on the secret Mars missio... oh wait, forget I mentioned that.
I solved the riddle in several minutes. First I discovered the recurrence relation that you showed in the video, and then I started to calculate for 1, 2 and 3 and saw I got 1, 1½ and 1⅚, which are the first harmonic numbers - the partial sums of the harmonic series. Then I started to check if it's generally true - I plugged the harmonic numbers to the recurrence relation and saw if I indeed get a harmonic number:
1 + 1/n ΣHm = 1 + 1/n ΣΣ1/k = 1 + 1/n Σ(n-k)/k = 1 + 1/n Σ(n/k - 1) = 1 - (n - 1)/n + Σ1/k = 1/n + H(n - 1) = Hn
I'm sorry I don't have limits for my sums, but I didn't know how to insert them nicely.
The first equality is from the definition of the harmonic numbers.
The second is from counting how many times each unit fraction appears in the sum.
The fourth and the fifth are like that because the sum is from one to n-1.
So then the solution for 10 is H10, which is 7381⁄2520, or approximately 2.93.
what does .93 of a jump look like again?
I tried it in python and got 2.93 with simulations.
from random import randint
from statistics import mean
def frogsteps(step_number):
step_count = 0
all_steps = []
while step_number != 0:
all_steps.append(step_number)
step_number = randint(0,step_number-1)
step_count += 1
return step_count
tried = []
for i in range(100000):
tried.append(frogsteps(10))
print(mean(tried))
@@LuigiBrotha I took your code and modified it to crunch the numbers for more jumps. It's currently melting my tablet but here are some results:
for 0, the mean is 0
for 1, the mean is 1
for 2, the mean is 1.500251
for 3, the mean is 1.832828
for 4, the mean is 2.082564
for 5, the mean is 2.283227
for 6, the mean is 2.448204
for 7, the mean is 2.591892
for 8, the mean is 2.716641
for 9, the mean is 2.830429
for 10, the mean is 2.927934
for 11, the mean is 3.021966
for 12, the mean is 3.102178
for 13, the mean is 3.179268
for 14, the mean is 3.249788
for 15, the mean is 3.319182
for 16, the mean is 3.38179
for 17, the mean is 3.43938
for 18, the mean is 3.494447
for 19, the mean is 3.55039
for 20, the mean is 3.595437
for 21, the mean is 3.645943
for 22, the mean is 3.692473
for 23, the mean is 3.73674
for 24, the mean is 3.776979
for 25, the mean is 3.817263
for 26, the mean is 3.85587
for 27, the mean is 3.888344
for 28, the mean is 3.927704
for 29, the mean is 3.960723
for 30, the mean is 3.997292
for 31, the mean is 4.027499
for 32, the mean is 4.05669
for 33, the mean is 4.089136
for 34, the mean is 4.11915
for 35, the mean is 4.146011
for 36, the mean is 4.173906
for 37, the mean is 4.204187
for 38, the mean is 4.22523
for 39, the mean is 4.254671
for 40, the mean is 4.280237
for 41, the mean is 4.302223
for 42, the mean is 4.326161
for 43, the mean is 4.34952
for 44, the mean is 4.37019
for 45, the mean is 4.396291
for 46, the mean is 4.414632
for 47, the mean is 4.436148
for 48, the mean is 4.458545
for 49, the mean is 4.482059
for 50, the mean is 4.50089
I want to know how you wrote math fractions and symbols in a youtube comment
This makes me hoppy. So many great techniques and variety of nerdyness!
CGP Grey, Minutephysics, and Standupmaths are all uploading yeet
My Guess: 2.92896825396825 jumps on average for ten landing places
My coworker Josh had that exact answer to 10 decimals places.
Yeah I got 2.92842592843 approximately
It's exactly 2.928968253, with the last 6 digits repeating.
2.9289682539682533 is the output my python script gave me.
I got 98.5, is this correct?
We shoul ask Leo Moracchioli, he ownsstudios researching this phenomenon
That is the worst joke e... have my upvote
That took me way too long to work out
Guess, it will be proportional to log n (eg log base 2 of n), because at each step it goes on average half of the remaining distance.
Well, if we think of it like rolling a d(remaining spaces) we get 5.5 average movement at first, then 5.5/2=2.75 for a total of 8.25 then 2.75/2=1.375 totals 9.625 + 1.375/2=10.3125 which averages something like 4 jumps (between 3 and 4- which is what I would expect since it's probably close to log base 2 of N where N is total pads and they can jump to any pad)
So, Log base 2 of 10 is about 3.32 which is ~ 3 1/3 which seems about right- while 10 seems to be roughly halfway between 9.625 and 10.3125 on a log base 2 scale you'd have 1/3 being the halfway point...
between 3 and 4 is also the most intuitive answer, well done.
If the frog is capable of jumping 10, and it is on space five, do we limit it's capability to 5 spaces or do we allow it to overjump? So for example, if it's on space 5 does it have 1/5 chance (1, 2, 3 ,4, *5*) of getting to the end on its next jump, or does it have 6/10? (1, 2, 3, 4, *5*, *6*, *7*, *8*, *9*, *10*)
@@billweasley1382 1/5
I got that it is the sum of the harmonic series
I got the same recurrence relation as you did (with the constraint that E(0) = 0) and then I considered E(k+1). I did some manipulations to get this is terms of E(k), so I got E(k+1)=E(k)+1-k/(k+1). By plugging it into itself repeatedly you can get it just in terms of k. My final answer was E(n)=sum from k=1 to n of 1/k
Aww I made it with recursion before he said you can’t :(
But I love how he just went “screw it, let’s Monte Carlo the frogs”.
Closed form solution is : = ln(e^g * n) where is the expectation value of jumps, ln is the natural log, e is Euler's number (i.e. 2.718...), g is the Euler-Mascheroni constant (i.e. 0.577...), and n is the number of choices available to the frog at the start (including the final landing pad)
Solution before watching video.
For length of path L, the expected amount of jumps will be sum (1,L){1/L}.
for example, a length of 10 has an expected jump amount of 1+1/2+1/3+1/4...+1/9+1/10, = 2.929...
Just Thomas : Great answer, I found 2,9289630180776 through analyzing all possible 512 jump sequences, their respective chances and multiplying. Its really close to your answer (2,928968254) - I wonder what causes the difference...
@@mauritswinters866 When i analyzed the 512 possibilities, I came up with 2.92896825396826
Using L in both places seems confusing. I think you mean sum n (1, L) { 1/n }
2:58
Intuitive answer would be:
Frog jumps would average out at somewhere in the middle in terms of distance for each jump, so it would be a progression of halving the remaining distance each time until you hit a value that is lower than one. About four jumps?
Dunno, show me the solution!
El Kudos that was my immediate first thought too, like a binary search, log base 2(n)
Actually it corresponds to H_n, so It is approximately ln(n)
Solution is around 2.928968. Not sure if it goes on forever, this is just as far as C++ double precision goes.
@@cameron7374 got the same answer
@@cameron7374 Windows Calculator (1/10 + 1/9 + ...) goes to = 2.9289682539682539682539682539683
First gut estimate: The expected value for each jump is half the remaining distance. The discrete lily pads prevents Zeno's paradox, so I expect a value near log_2(n).
Second shot:
For 0 pads it jumps to the other side, for a value of 1.
For one lily pad, it either jumps all the way, or jumps to the pad. (0+1)/2+1=3/2.
For two pads, it has an average of (0+1+3/2)/3+1=11/6.
For three pads, it has an average of (0+1+3/2+11/6)/4+1=25/12
For n pads, it has an average of sum( ave(i
I think you're right; I wrote a bit of code and after a million loops the average came out to be 3.0195806, remarkably close to your 83711/27720 (= 3.0198773)
So the answer for N = 10 (9 lily pads) is 7381/2520. More generally, the answer for N (N-1 lily pads) is sum 1/k, k from 1 to N.
The key to solving this problem is realizing that once you solve for one number of lily pads, you can solve for the next highest number of lily pads. For example, P(N) represents the expected number of jumps given N-1 lily pads, then P(N) = 1 + P(N-1)/N + P(N-2)/N + P(N-3)/N + ... + P(2)/N + P(1)/N. The reason for dividing each P(...) by N is that there's a 1 in N chance of landing on any of the possible landing spots. So for example, there's a 1/N chance of there being P(N-1) expected jumps remaining if the frog only jumps to the first lily pad. The reason for the addition of 1 to that sum in that equation is that you have to do one initial jump before the remaining possible jumps are added. So you make one initial jump, and then you add the weighted expected number of jumps from all the possible landing locations.
So if P(N-1) = 1 + [P(N-2) + P(N-3) + P(N-4) + ... + P(2) + P(1)]/(N-1)
and P(N) = 1 + [P(N-1) + P(N-2) + P(N-3) + ... + P(2) + P(1)]/N
we can actually rewrite P(N) in terms of P(N-1)
P(N-2) + P(N-3) + ... + P(2) + P(1) = [P(N-1) - 1]*(N-1)
so P(N) = 1 + {P(N-1) + [P(N-1) - 1]*(N-1)}/N
expanding, we get P(N) = 1 + P(N-1)/N + P(N-1) - P(N-1)/N - 1 + 1/N = P(N-1) + 1/N
So P(N) is just P(N-1) + 1/N
P(1) = P(0) + 1/1 = 1 (P(0) is just 0 because the expected jumps is 0 if you're already on the bank)
P(2) = P(1) + 1/2 = 1 + 1/2
P(3) = P(2) + 1/3 = 1 + 1/2 + 1/3
P(4) = P(3) + 1/4 = 1 + 1/2 + 1/3 + 1/4
etc.. you can see that P(N) is just the sum of 1/k, k from 1 to N.
making P(10) the sum of 1/k, k from 1 to 10, or 7381/2520, approximately 2.929
The result is the harmonic series (H(n)=sum[1/i] from i=1 to i=n) and the proof (although it took me a while to come up with it) is quite simple:
I'll prove it by induction. First we define A(n) as the expected number of jumps if the frog starts in the nth spot with its target being spot 0. We calculate one term A(1)=1 (this is evident). Then we assume it true until A(n-1) and prove it for A(n).
We'll calculate A(n)=(1/n)*p1+((n-1)/n)*p2 where p1 is the expected number of jumps given it lands on the adjacent spot and p2 the expected number of jumps if it doesn't (both including the initial jump).
The frog has a 1/n chance to move only 1 spot which would give it (if it did) an expected number of jumps of 1+A(n-1) (once it's in the n-1 spot it will continue as if it started there no matter where it actually started). So p1=1+A(n-1).
If it jumps to any other spot (with a chance of (n-1)/n)) since they are all equiprobable the result will be the same as if it had started in the n-1 spot (given it doesn't land in the n-1 spot the chance of it landing in any other specific spot is given by Bayes' formula 1*(1/n)/((n-1)/n)=1/(n-1) which is obviously the same probability as if it had started in the n-1 spot. Giving us the second term A(n-1).
Now we add both terms A(n)=(1/n)*(1+A(n-1))+((n-1)/n)*A(n-1)=(1/n)+A(n-1). Since we are proving it by induction we assumed that A(n-1)=H(n-1) and we've proven A(n)=(1/n)+A(n-1)=(1/n)+H(n-1)=H(n). And since we proved A(1)=H(1) we've now also proved that A(n)=H(n) for all n whole number greater or equal to 1.
In case someone wants a more algebraic proof here's one starting from the recurrence relation (which is easy enough to deduce) that Matt shows around 4:18 (in very small steps, same definition of A(n) as before).
A(n)=1+(1/n)*(sum[i=1 to i=n-1] A(i))=
=1+ A(n-1)/n+ (1/n)*(sum[i=1 to i=n-2] A(i))=
=1+ A(n-1)/n+ ((n-1)/n)* (1/(n-1))*(sum[i=1 to i=n-2] A(i))=
=1+ A(n-1)/n+ ((n-1)/n)* (1-1+1/(n-1))*(sum[i=1 to i=n-2] A(i))=
=1-(n-1/n)+ A(n-1)/n+ ((n-1)/n)* (1+1/(n-1))*(sum[i=1 to i=n-2] A(i))= Here the last term "1+1/(n-1))*(sum[i=1 to i=n-2] A(i))" is the definition via the recurrence formula of A(n-1)
=(1/n)+ A(n-1)/n+ ((n-1)/n)* A(n-1)=
=(1/n)+ A(n-1)*(1/n+(n-1)/n)=
=(1/n)+ A(n-1)
And again since we've proven A(1)=1=H(1) this proves that A(n)=H(n) for all n>1 and n being a whole number.
@@wasfas1977 *Now* I find the comments where wveryone's solved it before me in the same way, ;-) .
My guess is 3.3219. I guessed log base 2 of 10.
aka half an order of magnitufe
log base 2 of width was my first instinct too
I tried log base 2 of n, where n is the number of max leaps, it is fairly close when considering small n, but the result diverges from what I get in computer simulation as the n gets bigger. Somehow I managed to pull something like that: log base 2 of n - (log base 10 of n - 0.5) and this spits results very close to computer simulation (checked up to n = 100000) But I honestly don't know where does this log base 10 of n - 0.5 comes from
@Phinehas Priest I couldn't read all of your comment, but I think we did the same kind of thing. I just tried it on numbers of places to jump until 4 places, and then simplified all of the sums to find that for each space added, another number from the harmonic series was added. This essentially meant the answer for n spaces was just the partial sum of the first n numbers in the harmonic series. I graphed every result possible pretty quickly - desmos.com/calculator/jjfcqzuiv5 - and since we're looking at the harmonic series, there is no known formula to find the sum of the first n values without sigma, so I believe this is the best you can get to.
With problems like these, when it's 10pm and you're too tired to think it through, trying each value of n is just the easiest way to do it, and in this case it was the quickest and easiest way to find the pattern. I don't know if it was luck, but I managed to find this in around 15 minutes.
That is my guess too.
LONG GUESS:
If we start with one lilly pad between the start and tge finish we can say that P(finishing) = 0.5. And P(landing on the pad)=0.5.
This means that the expected number of steps is (1+2)/2 = 1.5 steps.
This will always be the expected number of steps when the frog lands one away from the finish.
Now lets assume there are two lilly pads between the start and the finish.
P(finishing) = 0.3...
P(landing one away) =0.3...
P(landing two away) =0.3...
Therefore the expected number of steps is (1+2+(1+1.5))/3=1.83...
Now if there were three lilly pads between the start and the finish we have
Average steps = (1+2+1.5+1+1.5+1+1.83...)/4=2.083...
Now if there were four lillys
Avg steps = (1+2+1+1.5+1+1.83...+1+2.083...)/5=2.283...
Now if there were five lillys
Avg steps = (1+2+1+1.5+1+1.83...+1+2.083...+1+2.283...)/6= 2.45
Now if there were six lillys
Avg steps =(1+2+1+1.5+1+1.83...+1+2.083...+1+2.283...+1+2.45)/7=2.5928...
Now if there were seven lillys
Avg steps = (1+2+1+1.5+1+1.83...+1+2.083...+1+2.283...+1+2.45+1+2.5928...)/8=2.717......
Now if there were eight lillys
Avg steps=(1+2+1+1.5+1+1.83...+1+2.083...+1+2.283...+1+2.45+1+2.5928...+1+2.717...)/9=2.828...
FINALLY if there are 9 lillys between the start and finish
Avg steps=(1+2+1+1.5+1+1.83...+1+2.083...+1+2.283...+1+2.45+1+2.5928...+1+2.717...+1+2.828)/10=2.928...
Or in conplete form
7381/2520
Is this right?
@@Dziaji woohoo
I got the same solution :D
@@DarA-ud4qm nice!
Isn't this what they call a recursive relation?
@@louisheyyyy It is. Still the result is correct, even if it doesn't answer the question of the problem.
I have to go with the partial sum of the harmonic series as well.
I convinced myself by "building" the matrix of jumps.
You can easily solve the 3 steps case by hand.
I did it by constructing the 4 (=2^(steps-1)) x 2 (=number of steps-1, last step is always on the other side of the river). This is a boolean matrix, place a true if the frog lands there.
Call it M_3. Count the jumps in each row (=number of true +1), you get the vector j_3.
Compute each probability, place it in p_3. The expected value is the dot product of the j_3 and p_3.
If you want to do the case 4 (=n), here is a way:
Build the M_4 matrix (8×3). Fill the first column half with 'false' (=the frog did not stop on first stone) and half with true. Fill the remaining top half with M_3. Do the same with the bottom half.
Convince yourself that you actually covered all possible cases.
By doing so, the j_4 vector is essentially j_3 on top and j_3+1 on the bottom. The probabilities vector for the bottom part is as follow: the frog jumps on the 1st pad (1/4 of the time) and then has to solve the previous '3 step problem' (so it is 1/4 of P_3), while the top part is again P_3 but scaled with (1-1/4), because when it is not landing on the 1st stone (3/4 of the times) it is actually solving a '3 step problem'.
So when you do the dot multiplication to get the probability, the top half will be 3/4×E(3), while the second will be (E(3)+1)/4.
Rearrange and you get E(4) = E(3) +1/4.
Do the general case in the same way, and you get that E(N+1)=E(N)+1/(N+1).
Solve for base case 1: E(1)=1.
Realize it is the partial sum of the harmonic series.
I also tried a less recursive approach: while a pattern clearly exists and it is extremely clear and interesting, I was not able to prove it for the general case.
I used a forward trellis, and applying forward probability found P(X=x) where X = number of steps to reach the end. Consequently I got E(X) = 2.929
@Phinehas Priest Can you elaborate?
@@cd265 ignore it, you are correct.
Making a poor little frog jump that path so many times is just mean.
You could just have lots of frogs taking turns. There are so many millions of frogs that if they each just did one or two tries it should be enough...
Rishvic Pushpakaran I think that Matthew Ellisor is referring to the repeated iterations of the frog crossing the river in its entirety over the course of many tries (perhaps millions) in an effort to get a nice average using a computer simulation to run all of those tries, each try with a number of jumps. Even if it only took one jump each try, if you tried it a million times that would be a million jumps, making the poor little frog tired just to satisfy our curiosity.
In a simpler way starting from the case pad#=n, each value can be calculated by
(1+a+b+c+d+...)/n
where the letters are the previous step's values.
Since we know that when there are 0 pads, the number of jumps is 0, the rest can be calculated step by step.
This is true because each nth case consists of the (n-1)th case and the jump from the beginning to the end (hence the adding of 1).
This is also the formula for the nth term of the harmonic series given those previous.
You left out the best part!
The expected number of jumps for n-1 lilypads (n including the bank) is the partial sum of the harmonic series up to n which is such a beautiful result! (i.e. E(n) = 1/1 + 1/2 + 1/3 + 1/4 ... + 1/n)
You can prove this using strong induction and the recurrence relation that Matt presented in the video (E(n) = 1 + ΣE(k) from k=1 to k=n-1).
Therefore the expected number of jumps for 9 lilypads is 1/1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 + 1/7 + 1/8 + 1/9 + 1/10 = 2.9289...
I have a hunch that there's a logarithm in here somewhere, so my guess is for 1+ln(n) jumps.
Just count for 3 or 4 and check the formula
Daan Wilmer you are actually correct (ish) as it does tend to that (almost)
you would be correct
That's a very good approximation in the long run tbh
I think the frog is only allowed to jump to the opposite bank or on the lily pads. Using logs is cheating. :o)
working out the number ways to get each jump for increasing numbers of lily pads like in the video Pascal's triangle shows up. (for instance 6 lily pads:
1 way to get 1 jump
5 ways to get 2 jumps
10 ways to get 3 jumps
10 ways to get 4 jumps
5 ways to get 5 jumps
1 way to get 6 jumps
since all paths are equally likely, 3 or 4 jumps will pop up the most since there are more ways for that to happen. Each lily pad added drops us one more line in pascal's triangle. Since the highest numbers are always found at the median. The formula would be the median of {1,2,3,4,...,n} for n lily pads. (i forget how to make that into an equation, and I have to go)
David Kennon It’s better start then most.
Doesn't fly. For instance, the chance that the first jump will be the entire distance is 1/n. The chance you will make single steps (n jumps) is (1/n)^n. They are not equally likely. So 1 jump has a 1/6 chance, while 6 jumps has a 1/46656 chance.
Michael Timothy Yes I see that the probability of individual paths is not equal.
@@Brooke-rw8rc you right, you right! I corrected myself in another comment, but didn't edit this one. below is my other comment
@@dominiquefortin5345 you right, you right! I corrected myself in another comment, but didn't edit this one. below is my other comment
Since there are 10 spaces, my first intuition is to get the average outcome of rolling a 10-sided dice, giving me a 5.5 which I'll round to 6. I'll be left with 4 more spaces where I'll repeat again, giving me 2.5. I'll round to 3, now I left 1 space. So, my guess is 3 jumps.
Why round during your calculations giving a less precise answer. There is nothing stopping you from having a theoretical four-and-a-half sided die with an average of 2.75, unless you want to verify it with real life experiments :)
If ever there was a problem that needs to be formulated as a recursive problem.... I couldn't be bothered with the algebra, so I set up a tree with the conditions: 10% chance that it takes one leap (to the other shore), 10% chance that it takes one leap to the last lily pad, plus whatever it takes to go from there, etc. And then add up all the ten contributions to the whole. Building from the back, Excel helped out and gave the right solution: approx. 2.93, which fits will with my intuition. The algebraic solution, based on the same reasoning, is of course found in other comments here. Matt clearly has some smart subscribers!
"I wrote some python code"
TIL people still use Python 2 in 2019 when it's EOL for 2020 and Python 3 has been around for over 10 years
i love Matt, but python 2 in 2019 is a crime and should be punished
@@shilangyu Should have used Ruby.
@@DonReba I wrote my code in Fortran 90 :/
But the Raspberry Pi 4 B with 4gb ram just came out and runs python code really nice so it is still relevant and useful to us makers :)
Do it in LUA dudes! Real ones uses LUA.
This was a fun problem! My initial guess was 3, then using theory I came up with a very unforgiving formula for the probability of crossing in n-many hops which relied on nested summations. So then I used a computer to compute the expected number of hops to be about 2.928968. And then, I ran many simulations on my laptop and found the average number of hops to match the expected value I got. As for generalizing, I found that the expected number of hops grows logarithmically and will be about 0.63 + ln(n+1) for n lily pads!
I used almost exactly the same approach! I thought the logarithmic-like function was just some logarithm in some base, or log plus something or times some constant, but then I saw a comment mentioning the harmonic series... And it all made sense
I always found the songs of frogs very harmonic ;)
Fun problem. But what if the frog is climbing a sand dune, such that every time it lands, it slides back one spot?
What would happen at the final spot? Would it slide back in an endless loop or would it end once it reached the final spot?
If you assume that once the frog reaches the final spot, it no longer slides back one space, the formula for the expected number of hops is 1 + sum from k=2 to n (where n is the number of spots on the sand dune) of 1/(k-1). This formula works for values of n > 1. The value for n = 1 is just 1 because the frog cannot slide back once it has reached the end. So, basically, it is just the 1 + the harmonic sum offset by 1.
I think it will be log base two(n), where n is the number of lilypads in the river. Every time it jumps, on average, it halves the distance to the pond.
The expected value will be a decimal, so no need for ceiling. It gives you 3.3 for n=10, which is pretty reasonable.
@@karlmuster263 Yeah, you're right. I knew as soon as I had posted, but I forgot how to edit on mobile.
"A frog can never cross the same river twice." - Heraclitus's frog
Steve the Cat Couch LOL
I was just at fringe, wish I knew you were there! Great video
I'm not a mathematician and I initially tried to calculate the probabilities by hand. Calculating the probability of 1, 2 and 10 jumps was easy, 3, 4 and 9 were much harder and 5-8 got very complicated very quickly so I wasn't able to do these. So I wrote a Python program for 100 million jumps to simulate it. The values I had calculated by hand matched up with the simulation perfectly! 10 jumps ridiculously unlikely: 34 instances in 100 million iterations!
But basically, 3 jumps is the most likely at 32.32% of the time. The actual average is 2.93 jumps but seeing as there's no such thing as a fraction of a jump in real life, I will say the correct answer is 3.
I solved it using a Markov Chain: I got 2.9289682539682538 for n=10.
Yes my simulation gives that result too! 😍
I don't know what 'Markov Chain' is... but I got the exact same result! :D I just used Kotlin instead. XDXD
@@Verrisin I got the equations from modelling it as a Markov chains, I implemented them in kotlin to solve them, too! A "Markov chain" has basically some states and it can change from the current state to any other state with some probability.
2.92896825396826 verified with a program to simply brute force evaluate all 512 jump patterns.
I think you can work it out by starting from the end.
E10 = 0
E9 = 1
E8 = 1 + 1/2*E9
E7 = 1 + 1/3*E9 + 1/3*E8
E6 = 1 + 1/4*E9 + 1/4*E8 + 1/4*E7
and so on all the way to E0 which is the starting position and crunch the numbers.
For 10 jumps this gives about 2.929
geryon oh goodness that’s clever.
geryon This is the method I used as well.
My simulation on Python gives me that result!
With more than hundred milion iters it gives approximatly a value of 2.928ecc..
geryon obv i did a very simple program for Python so it approach that result veeeeeery slowly
I made an interesting discovery! I modeled the problem as a graph using a matrix. Multiplying the matrix with itself gave the answer (or close enough to it) in the bottom left entry of the matrix.
I don't really understand why it works out this way, but I'm fairly confident my formula works from the values I've tested.
Again, I discovered this by modeling the problem as a graph in a square matrix where each entry is the probability of going to spot "m" (corresponding to the column of the matrix) to spot "n" (corresponding to the row of the matrix). The first thing I tried was to multiply the position vector [1, 0, 0, ...] by the matrix a few times and that wasn't very interesting.
The big "Aha!" was when I started multiplying the matrix with itself. I noticed the {col 1, row n} entry looked really familiar. In fact, it was the part of the sum in the recurrence solution corresponding to the immediately previous entry in sequence! Doing a little reverse arithmetic I was able to arrive at the solution for the previous entry using a non-recurring formula. Turns out my formula simplified to exactly the harmonic series.
I have concluded this is the harmonic series so: E[10] = sum 1/j, j=1 to 10 = 7381/2520
E(n) is the expected number of jumps, n is the number of potential banks. n = 2 being the minimum then. So E(n) = 1/(n-1) * Sigma{(lowerbound 1, upperbound n-1) n }. Sorry I couldn't get the right notations in with youtubes comment editor. So for 10 banks, it would be 5, and for 11, 5.5. This comes down to E(n) = 0.5*(n-1) + 0.5
Let E_n be the expected number of jump to goal when the frog is n pads away from the goal
So E_0 = 0 because the frog is already at the goal
E_1 = 1 (1 pad away from the goal, so the only possible move is to jump forward 1)
If the frog has n pads left, then it's equally likely that after 1 jump, he has 0, 1, 2, ... n-1 pads left
So E_n = 1 + average of (E_0, E_1, ..., E_(n-1))
Aka E_n = 1 + sum of (E from 0 to n-1) / n
Also E(n-1) = 1 + sum of (E from 0 to n-2) / (n-1)
so sum of (E from 0 to n-2) = (n-1) * E_(n-1) - (n-1)
So sum of (E from 0 to n-1) = sum of (E from 0 to n-2) + E_(n-1) = n * E_(n-1) - (n-1)
So E_n = 1 + sum of (E from 0 to n-1) / n
= 1 + (n * E_(n-1) + (n-1) ) / n
= 1 + E_(n-1) - (n-1)/n =
= E_(n-1) + 1/n
Using this recurrent relation
E_1 = 1
E_2 = 1 + 1/2
E_3 = 1 + 1/2 + 1/3
...
E_n = sum of 1/i for i = 0 to n-1 = H_n (where H_n is the nth harmonic number)
So E_10 = H_10 = 7381/2520 = about 2.9
"Everyone's packing down" (9:06) -- but in the USofA, they would be packing UP.
And my guess (for 10) is pi + 1. Just because.
I did a bit of figuring and research, and worked backwards a bit: using the fact that the average number of moves went up by 0.5 for every n lily pads, I used that and the number of possible sequences (2^n) to determine that the average number of moves for 10-lily is 6 moves.
I had to consult OEIS to find an equation to get the number of moves by putting in the sequence (1,3,8,20,48,112,256,...) to find a(n) = (n+2) * (2^(n-1)); taking a(n)/2^n gives the average number of moves for n lily pads.
I feel like that's as good of an answer as I'll be able to get. Now I can finally look at the other comments to see what everyone else came up with. I'm kind of proud that I was able to fix my initial notations to realize that 2^n played a part in everything.
I get 2.928968.
The answer for 1 pad is 1 jump, for 2 pads is 1.5 jumps average, for 3 pads is 1.83333 jumps average, for 4 pads 2.0833, etc. The nth term is 1/n more than the (n-1)th term. Or for 10 pads, it's 1+1/2+1/3+...+1/10.
I swear to god my 7'th grade math teacher tried to make us figure this out. I think she was just wondering if we'd get it. We did not :{D
The answer for 9 intermediate points is 2.92896825396825.
For n intermediate points the answer is:
The sum of first n + 1 terms in the harmonic series.
1+(1/2)+(1/3)+...+(1/n+1)
Answer for 10 landings = 5.5
consider a case where there were 3 landings, n =3, to complete the task by 1 jump, there is only 1 possibility, to complete jump by 3 jumps, there is only 1 possibility and to complete the task by 2 jumps, there are 2 possibilities by skipping 1 landing each time.
Hence read the smaller problem as if given n landings, to complete the task by j number of jumps: the frog needs to choose "j-1" landing points among n landings or skip "j"landing points among n landings. this giving me a simple formula:
number of possibilities for "j"jumps = P = n C (j-1) or n C (j), whichever is lesser
So for average number of jumps: sum of possibilities for j jumps x j / sum of all possibilities
= Summation of [P * J ] / Summation of P
Average for 10 landings = [ sum {j from 1 to 10} Min (10 C j, 10 C (j-1) * j ] / sum {j from 1 to 10} Min (10 C j, 10 C (j-1)]
J (P ) (P x j)
1 1 1
2 10 20
3 45 135
4 120 480
5 210 1050
6 210 1260
7 120 840
8 45 360
9 10 90
10 1 10
Summation of P x j = 4246
Total possibilities = sum (P) = 772
Average = Sum(P x J) / Sum (P) = 5.5
Using same formula, average possibilities for 100 landings = 50.5
Somehow, after few tries, I have found that the expected number of jumps for n landings is n/2 + 0.5
7:10 This is the second time I can recall seeing them at least mentioned; first time was on Penn & Teller: Fool Us
"We had an amazing time. We were all doing it on the bar. People gathered around and shouted out which angle to concentrate on next. "
This is exactly what I expected Edinburgh would be like.
My guess is 5.5 (or in this case 5 and 6 jumps have the same probability of happening). I started drawing out the jumps and for any number of Lilly pads and started to notice the pascal triangle showing up as well, and after a few "simulations" on paper, I came up with the non recursive formula. f(n) = (n+1)/2 where the n is the number of jumps
For the formula, I've got to it by summing all the jumps of every possible combination (using the Pascal triangle) and dividing by the numbers of tries (given by the triangle as well). This gave me a mean jump estimate, and after a few tries with different lillypad configurations, it always got me to the same solution as given by the formula
I also got 5.5, but I solved it as an expected value problem: I found the probabilities p(x) of each number of jumps x (by brute force counting) and summed the products x*p(x) for x=1,...,10.
I made the same mistake: I took every possible combination, calculated number of jumps for each, summed them together and divided by total number of combinations. But this would be right only if probability of every combination is the same, which isn't!! It can be easily seen fo the n=3. There are 4 possible combinations: 3, 2+1, 1+2, 1+1+1. There are 2 cases that start with 1, so the probability of jumping to first leaf is 1/2 and probability of jumping to second and third is 1/4. But the task says the probability of jumping to any leaf is the same, 1/3 for n=3.
define En as the expected number of frog jumps until the end, where there are n pads in front of him.
then we get that En = 1 + Sum of (1/n * Ei) for all i from 1 to n-1 = 1 + 1 / n * Sum (Ei) for all i from 1 ton-1
define Dn = n * En, and then Dn - D(n-1) = n * En - (n-1) * E(n-1) = (n + Sum (Ei) for all i from 1 to n-1) - (n-1 + Sum (Ei) for all i from 1 to n-2) = 1 + E(n-1)
which means, Dn = 1 + E(n-1) + D(n-1) = 1 + E(n-1) + (n-1) * E(n-1) = 1 + n * E(n-1).
dividing both sides by n leaves us with En = Dn / n = E(n-1) + 1/n
and this is simply the harmonic series (notice that E1 = 1).
thus for 10 it is simply E10 = 1 + 1/2 + 1/3 + 1/4 +1/5 + 1/6 + 1/7 + 1/8 + 1/9 + 1/10 = 2.9289682539...
Here is my recursion solution in Python (extra brackets for order of operations emphasis):
def jumper(n=10):
return 1 if n == 1 else (1/n) + ((1 - (1/n)) * (1 + jumper(n-1)))
My guess is 7381/2520 for 10 pads
I've never dug around the OEIS so much before in my life
Or 1 + 1/2 + 1/3 + ...... 1/(n-1) + 1/n
@@DekarNL I got the 11th element of A000254 over 10 factorial, which reduces to the answer you gave. What OEIS sequence did you end up at?
It is Slightly higher than that.
Help please:
I've been searching for this one video about a mathematical game.
In the game, we toss a coin and bet some money on the outcome.
If we predict the outcome correctly we get a reward and if predicted incorrectly we lose the money we bet.
I seem to recall the optimum %age of money to be bet (for 2x reward and x bet) was something like 10% of total money available for betting (and there was some equation to it all)
Does anyone know what video this was or anything similar?
Thanks.
Maybe something on Vsauce2?
@@mbrozzo This is my guess too.
I [𝐻]ate that you posted this. I've put days into it.
My initial thought is to kinda go with something like Zeno's Paradox where the frog will jump halfway across and then do so again and again until it reaches the far bank. So for ten, first it jumps to six, then it jumps to eight, then nine and finally ten.
I'm guessing with the assumption that there were ten spots in total with one being the bank it started on and ten being the far bank I might have missed if the ten jumps wasn't including the banks in the video.
Then look at that number of jumps for the average. But thinking about it a little more it's also likely to take it in thirds, or fourths or just about any fraction. So for a very rough guess(probably unworkably rough) would be to take the number of jumps from the frog going half the way, a third of the way a fourth of the way, all of the way to an Nth of the way and then averaging that out into a number.
Here is what I got when doing it quickly with notepad and the windows calculator I may have made some mistakes in counting the number of jumps. and Like I said I assumed that the frog started at one and ended at ten. If that wasn't what the problem was then well all of my numbers are gonna be off.
Halves: 4
Thirds: 6
Fourths: 8
Fifths: 8
Sixths: 9
Sevenths: 9
Eights: 9
Ninths: 9
and the average I calculated was 7.8888888888888888888888888888889
I would guess for 10 spots, it would be 4 jumps. If the frog is equally likely to hop on any spot in front of it, that can be averaged out to hopping 5 spots forward, which is half way. Then it would jump half as many spots (rounded up) again, so it hops 3 spots. There are only 2 spots left, so it hops half as many spots to the last pad, then it hops again to the bank.
So yea, I would guess 4 jumps on average.
WaywardBrigand my thoughts exactly
The average works out to ln(n) + 0.5772156649 where n = the number of pads. approximately. It's the harmonic number series and there is no exact formula.
Your heuristic was not terrible, but a little bit off.
The main reason you are a bit off is that your average jump is the median of zero and the max jump when one is the smallest available jump. So the first jump average is 5.5 not 5. When there are two options it’s 1.5 not 1.
Those are good points
"and thennn AUTO FROG"
-Man with the Most Awesome Moustache in England
ITYM Man with the Most Awesome Moustache in England Speaking From Scotland. Maybe there are more awesome facial hair configurations on a non-zero integer number of Scotsmen...?
I’d be willing to accept that axiomatically :)
I was thrilled to see GameMaker Studio, because this how I do all my arithmetic simulations (not as pretty as he did, but still).
Consider any path the frog could take. For example, it could land on the second, sixth, and seventh lilypads.
There is a corresponding opposite path in which the frog lands on none of these but instead lands on all the other lilypads. In this case, lilypads #1, 3, 4, 5, 8, and 9.
Between these two paths the frog lands on exactly 9 lilypads, and lands on the opposite bank twice, for a total of 11 jumps. The average number of jumps is 5.5
This is true for ANY path. There is always an opposite path such that the two average to 5.5 jumps. Even the path of taking the maximum 10 hops has an opposite: the single leap all the way across.
The set of possible paths is made up of pairs that each average 5.5. Therefore the overall average is 5.5.
And for a river of width N (containing N-1 lilypads), the average number of hops is (N+1)/2.