Can you solve The Frog Problem?

[@SteveMould]

Matt uses a light themed IDE. That's all you need to know about Matt.

[@sam2026]

Light theme is better

[@wyattsheffield6130]

@@sam2026 brave

[@a_guy_in_orange7230]

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. . . .

[@CoconutJones_]

You're a modern day hero.

[@sam2026]

Wyatt Sheffield /r/unpopularopinions

[@binaryagenda]

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.

[@gwendolynprovost191]

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

[@CheaterCodes]

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 KZbin lying to me?

[@AnonYmous-rw6un]

That was much easier than my approach, thanks.

[@VincentZalzal]

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!

[@VincentZalzal]

​@@dominiquefortin5345 But... 1.5 is indeed the second term of the harmonic series (E[2] in the notation above).

[@davidhendrickson9550]

Why did the frog cross the river 10,000 times? To avoid a probability quiz.

[@budesmatpicu3992]

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)

[@theRealPlaidRabbit]

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?"

[@thinboxdictator6720]

@@theRealPlaidRabbit did you ask?

[@evinliang9814]

the frog crossed the river 2520 times

[@benh8312]

@@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?

[@callbackspanner]

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.

[@anthonyl3065]

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

[@EricBliesener]

@@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.

[@anthonyl3065]

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.

[@Yull-Rete]

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.

[@rescuecatHQ]

Ok, lets go with that. P.S. what did that mean?

[@mihaimaruseac]

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.

[@nicholasfrieler5005]

I got the same answer but I used expected value

[@jackhanke343]

I got the same answer as well.

[@shawnsatterthwaite7968]

I just got there too, great job!

[@oliverpackham6278]

He said 10 landing places not lillys, you did it with 11 landing places.

[@lordknight4391]

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)

[@karibui494]

Initial reaction: "It's obviously 3" Make a simulation of just one iteration: get 3. Leave satisfied

[@HollywoodF1]

Fall-back plan: Hit the button a couple of times until you get three.

[@Atlessa]

I glanced at your avatar and instantly teared up...

[@sighthoundman]

@@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.

[@deSolAxe]

strange, my guess was 3 or 4... without even thinking about it... i wonder why 3 would be so "obvious"...

[@soumilshah1007]

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.

[@soumilshah1007]

Thus, for n=10 it's 2.92897

[@michael_betts]

I did it by working back from a recursive relation and got the same answer. KZbin 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)

[@Victor4X]

@@soumilshah1007 This is about the same answer as I'm getting with my simulation. Nice!

[@tommywareing9234]

I've got 2.929036 through simulation 1 million frogs. That sounds believably correct to me :)

[@soumilshah1007]

@@tommywareing9234 nice, close enough.

[@alexgabel4379]

Problem: ...and do NOT use recurrence relations. Parker Solution: So I used a recurrence relation.

[@alcesmir]

Technically it was stated that a recurrence relation would not suffice as an explicit formula. Too bad there is no explicit formula for this.

[@GnI1991]

@@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).

[@DDvargas123]

@@GnI1991 I think what alcesmire meant was closed form. like how the summation of an algebraic sequence is n/2(first+last)

[@alcesmir]

@@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.

[@carly09et]

10/[1+e] , the general is n/[1+e]

[@yagoduppel]

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.

[@yagoduppel]

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.

[@presto709]

@@yagoduppel So for us not math guys what is the answer for 10 lily pads?

[@wbfaulk]

​@@presto709About 2.93. So 3.

[@benconnor901]

Oh wow. I used a spreadsheet to find the approximation ln(n+1/2) + γ which is close but doesn't match exactly for small values. I can't believe it's just the harmonic series.

[@ten.seconds]

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.

[@casperycghost]

Exactly!

[@franchello1105]

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.

[@zaraimpala3962]

We all know frogs go "La di da di da"

[@BoyKissBoy]

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!

[@CauchyIntegralFormula]

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.

[@lolledopke]

"import random" inside a while loop, that's some classic Parker Python Programming

[@GvinahGui]

​@Andrew Crews 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.

[@BoyKissBoy]

@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.

[@dansheppard2965]

@@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!

[@toddgerdy2465]

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.

[@12tone]

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.

[@hls6925]

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.

[@theaxer3751]

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 😅

[@crjtodd]

@@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

[@hls6925]

@@crjtodd Sounds about right, Chris! BTW how long did your JS run for? Bit faster than my Basic, I'll bet!

[@LactatingBadger]

Matt: Uses python, the king of languages for quick and dirty solutions. Also Matt: Does analysis in Excel

[@SenselessUsername]

Well I do feel dirty after having used it, so they fit together.

[@lokedhs]

Not a great choice for simulations given how slow it is.

[@distantignition]

@@lokedhs Yep. Performance is of the utmost necessity in this instance.

[@LactatingBadger]

@@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!

[@Huntracony]

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

[@smergthedargon8974]

You: Jumping hurdles I, an intellectual: *_AUTOFROG ENABLED_*

[@daminox]

I want an AUTOFROG ENABLED bumper sticker

[@Jones12ax7]

I'll try with real frogs. Simulations are not precise enough. 😂

[@mokopa]

I'm happy with my spherical frogs

[@oximas]

I know righy😂hopefully you have frogs around

[@Elnadrius]

@@mokopa in vacuum?

[@texdrieschner2012]

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?

[@texdrieschner2012]

@@pilattebe Haha RIGHT!

[@-nepherim]

I'm going with 3. Because that seems right based on the frogs in my head.

[@xander1052]

that's pretty damn close to what people calculated using Python of 2.928968.... for n=10

[@tobiasgingerich5731]

I was thinking that it was 3

[@ffggddss]

@@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

[@LukePalmer]

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 ...

[@mantisbog]

No, it’s 4.2.

[@sammiddleton7663]

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.

[@lockaltube]

Yep, OESIS A001008 divided by OESIS A002805.

[@firstnamelastname307]

it's a matter of subsets indeed

[@stephenbenner4353]

But if the frog jumps half then a third then a forth, etc, then he will never actually reach the other side.

[@sammiddleton7663]

@@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.

[@stephenbenner4353]

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.

[@muratsaglam9671]

My guess is: e This number always appear somewhere where it isn't supposed to

[@standupmaths]

My first answer was “the answer to these questions is always e or 1/e”.

[@punya1621]

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

[@Paul-rv3rm]

@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

[@Xnoob545]

@@standupmaths my guess is pi

[@thinboxdictator6720]

@@Paul-rv3rm same result here. it looks more like e

[@macronencer]

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!

[@MrQuickLine]

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.

[@jerry3790]

My guess is that it would be root 10

[@herrzog602]

My bold claim is that the average number of jumps needed is Pi for any number of water lilies.

[@bitequation314]

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.

[@Beanlipe]

I was about to say that! hope it is pi!

[@chiprock804]

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. 🤐

[@krokkoguy]

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

[@rdbury507]

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.

[@MrBrain4]

I also discovered this same expression, using A000254.

[@stephenbenner4353]

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.

[@Aubreyously]

Guess: log base 2 of 10 Because on average, it’ll go to 5, then 7.5, then 8.75, etc

[@peterkframe]

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)

[@captainyager4701]

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.

[@Wommyo]

My guess is 3 Just feels like 3, of course, that being rounded to the nearest whole number

[@gavincupps8121]

I was thinking the exact same thing

[@matthewjohnson3610]

I started with 3, but that seems to high, so I'm going with e. Just intuition.

[@skylark.kraken]

@@matthewjohnson3610 I ran 1 billion rounds and got a stable 2.9289

[@user-zz6fk8bc8u]

@@skylark.kraken I calculated it and you are right. It's 2.928968254

[@rateeightx]

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.

[@GeekyNeil]

The answer is: integral from 0 to 1 of (x^10-1)/(x-1) = 7381/2520

[@jimmythewig3354]

That's spot on with the number I get when building it up recursively. Nice one. How did you get this result?

[@GeekyNeil]

@@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).

[@kaidatong1704]

@@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.

[@Tentin.Quarantino]

Auto frog mode enabled. Don't know why I found this so funny

[@RFC3514]

Autofrogs fight the evil forces of the Deceptitoads.

[@Twinster20]

@@RFC3514 Lol, just waiting for the live action

[@ludomine7746]

Ben Gillot sounds like penn Gillette in disguise

[@LIBICU812]

Even Penn Gillette doesn't believe in magic so every problem does have solution.

[@csongorzih5094]

It's Penn Jilette

[@CeilingNinja]

Thanks. I knew something was wrong and I couldn't figure it out so I guessed

[@callumstewart5891]

I'm glad I'm not the only one who immediately jumped to that.

[@mikailvandartel]

Penn Gillette, the best a man can get

[@bummerlord]

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

[@mattsmart4220]

That's what I was going to say. You beat me to it.

[@poco2s]

but does the Frog know that it lives in a simulation??

[@bookslug2919]

but don't you know that the frog lives in a simulation inside a simulation??

[@poco2s]

:) everything makes sense now

[@ThomasPlaysTheGames]

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...

[@mauritswinters866]

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...

[@lsj8]

@@mauritswinters866 When i analyzed the 512 possibilities, I came up with 2.92896825396826

[@lsj8]

Using L in both places seems confusing. I think you mean sum n (1, L) { 1/n }

[@tomzdotorg]

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)

[@catradar]

My Guess: 2.92896825396825 jumps on average for ten landing places

[@paulylewis8512]

My coworker Josh had that exact answer to 10 decimals places.

[@eroticpandaz1524]

Yeah I got 2.92842592843 approximately

[@ben.woodworth]

It's exactly 2.928968253, with the last 6 digits repeating.

[@sureshpatil4615]

2.9289682539682533 is the output my python script gave me.

[@manueloribe9153]

I got 98.5, is this correct?

[@livintolearn7053]

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.

[@evinliang9814]

congrats youre basically right

[@ollib4330]

exactly the same for me, 2.92 with the second decimal being 2 most of the times

[@kricsek]

Thank you.

[@GeminiSimulator]

I'm getting similar results at 1million iterations. 2.930, 2.929 so I think my code is working, strange feeling.

[@BrianMoore-gp8ot]

Its much easier to just actually simulate it. I will try doing it with rationals instead of doubles next.

[@jeanf6295]

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

[@idontwantahandlethough]

thanks for this!

[@roeesi-personal]

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.

[@mizinoinovermyhead.7523]

what does .93 of a jump look like again?

[@LuigiBrotha]

I tried it in python and got 2.93 with simulations.

[@LuigiBrotha]

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

[@hootyoo]

@@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

[@marlenedietrich2468]

I want to know how you wrote math fractions and symbols in a youtube comment

[@glarynth]

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.

[@dillongrannis8279]

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.

[@KnakuanaRka]

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.

[@elimiuzu]

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.

[@theaxer3751]

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

[@cd265]

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

[@cd265]

@Phinehas Priest Can you elaborate?

[@pauloat]

@@cd265 ignore it, you are correct.

[@paulgrimshaw6301]

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.

[@marcozagaria6696]

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

[@punya1621]

It is simple and feels right and I also checked for 3 Lily pads, it's 11/6 =[1+½+⅓] so yeah, should be correct.

[@marcozagaria6696]

@@punya1621 idk if there's a nice closed form

[@peterjamesfinn]

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)

[@matthewholmes1864]

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!

[@PaoloLammens]

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

[@ParadoxProblems]

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.

[@elkudos6262]

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!

[@Roeming]

El Kudos that was my immediate first thought too, like a binary search, log base 2(n)

[@massimogasparini1827]

Actually it corresponds to H_n, so It is approximately ln(n)

[@cameron7374]

Solution is around 2.928968. Not sure if it goes on forever, this is just as far as C++ double precision goes.

[@NaifAlqahtani]

@@cameron7374 got the same answer

[@LightDhampire]

@@cameron7374 Windows Calculator (1/10 + 1/9 + ...) goes to = 2.9289682539682539682539682539683

[@MsErfwe]

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.

[@Pier_Py]

MsErfwe same result with my simulation on Python that explore every possible combination of the jumps of the frog! I think is correct!

[@MWSin1]

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

[@OrchidAlloy]

@@MWSin1 No, the video is asking for the answer for 10 positions. That's 9 lilypads + the opposite shore.

[@MWSin1]

@@OrchidAlloy You're right. I somehow misunderstood the way the question was presented.

[@CrayyyCrayyy]

From a Psychology point of view with no math involved my answer is: It all depends on the mood, frame of mind and physical condition of the frog at the time of the crossing. On average If the frog is in Perfect Health and Not Distracted and as they say Able to Jump the Span in Only One Hop then it Will do it in Only One Hop since nature always takes the path of least resistance, BUT If the frog is say injured them it will make many short jumps or if the from is distracted by say a fly on one of the lily pads then it will make the appropriate number of jumps to get close enough to strike and if the frog is ill or weakened in some way it will also make more shorter jumps :)

[@kuro13wolf]

These random capital letters are driving me insane

[@kykk3365]

I don't think the physical condition of the frog has anything to do with Psychology.

[@alexwang982]

CGP Grey, Minutephysics, and Standupmaths are all uploading yeet

[@panda4247]

We shoul ask Leo Moracchioli, he ownsstudios researching this phenomenon

[@mauritz3912]

That is the worst joke e... have my upvote

[@jacobfife7273]

That took me way too long to work out

[@PsychoSavager289]

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.

[@Halosty45]

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...

[@Hamatabo]

between 3 and 4 is also the most intuitive answer, well done.

[@billweasley1382]

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

[@jetison333]

@@billweasley1382 1/5

[@linusnox]

I solved it using a Markov Chain: I got 2.9289682539682538 for n=10.

[@Pier_Py]

Yes my simulation gives that result too! 😍

[@Verrisin]

I don't know what 'Markov Chain' is... but I got the exact same result! :D I just used Kotlin instead. XDXD

[@linusnox]

@@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.

[@lsj8]

2.92896825396826 verified with a program to simply brute force evaluate all 512 jump patterns.

[@Danicker]

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...

[@talroitberg5913]

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.

[@Utesfan100]

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

[@legitgopnik8431]

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)

[@peterandersson3812]

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!

[@daanwilmer]

I have a hunch that there's a logarithm in here somewhere, so my guess is for 1+ln(n) jumps.

[@punya1621]

Just count for 3 or 4 and check the formula

[@henryginn7490]

Daan Wilmer you are actually correct (ish) as it does tend to that (almost)

[@marcozagaria6696]

you would be correct

[@Sahil-oq8ki]

That's a very good approximation in the long run tbh

[@mescad]

I think the frog is only allowed to jump to the opposite bank or on the lily pads. Using logs is cheating. :o)

[@wasfas1977]

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.

[@wasfas1977]

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.

[@dansheppard2965]

@@wasfas1977 *Now* I find the comments where wveryone's solved it before me in the same way, ;-) .

[@UsuallyUnique]

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

[@davidkennon1883]

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)

[@dominiquefortin5345]

David Kennon It’s better start then most.

[@Brooke-rw8rc]

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.

[@dominiquefortin5345]

Michael Timothy Yes I see that the probability of individual paths is not equal.

[@davidkennon1883]

@@Brooke-rw8rc you right, you right! I corrected myself in another comment, but didn't edit this one. below is my other comment

[@davidkennon1883]

@@dominiquefortin5345 you right, you right! I corrected myself in another comment, but didn't edit this one. below is my other comment

[@Martmists]

"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

[@shilangyu]

i love Matt, but python 2 in 2019 is a crime and should be punished

[@DonReba]

@@shilangyu Should have used Ruby.

[@CrushOfSiel]

@@DonReba I wrote my code in Fortran 90 :/

[@CrayyyCrayyy]

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

[@samueldevulder]

Do it in LUA dudes! Real ones uses LUA.

[@paulfoss5385]

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.

[@pmcgee003]

"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.

[@jweipjklawe4766]

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

[@c.j.3184]

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

[@geryon]

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

[@Caleb-zj9xi]

geryon oh goodness that’s clever.

[@tombryan7725]

geryon This is the method I used as well.

[@Pier_Py]

My simulation on Python gives me that result!

[@Pier_Py]

With more than hundred milion iters it gives approximatly a value of 2.928ecc..

[@Pier_Py]

geryon obv i did a very simple program for Python so it approach that result veeeeeery slowly

[@rbr4784]

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?

[@rbr4784]

@@Dziaji woohoo

[@DarA-ud4qm]

I got the same solution :D

[@rbr4784]

@@DarA-ud4qm nice!

[@louisheyyyy]

Isn't this what they call a recursive relation?

[@anneaunyme]

@@louisheyyyy It is. Still the result is correct, even if it doesn't answer the question of the problem.

[@marshallposner]

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.

[@Syncromatic]

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”.

[@HoTag]

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

[@simiansam5179]

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.

[@jaroslavzeman8959]

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.

[@aeonsiege1806]

By making a probability tree, the closed form equation I got was (Unsigned Stirling numbers of the first kind)/n!, that it in turn simplifies to a harmonic number which is just the sum of 1/k from 1 to n 2 lily pads = 1/1 + 1/2 = 3/2 average jumps 3 lily pads = 3/2 + 1/3 = 11/6 average jumps 4 lily pads = 11/6 + 1/4 = 50/24 average jumps 10 lily pads = 2.928968... average jumps

[@aeonsiege1806]

Input this in Wolframalpha Abs(StirlingS1[n+1, 2])/fact(n)

[@murmurmerman]

Fun problem. But what if the frog is climbing a sand dune, such that every time it lands, it slides back one spot?

[@nicholasfrieler5005]

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?

[@nicholasfrieler5005]

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.

[@henryginn7490]

I got that it is the sum of the harmonic series

[@henryginn7490]

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

[@sylvar81]

Great problem! Average number of jump for n spaces is sum from i=1 to N of1/i Demonstration For N possible spaces, result Rn is 1x1/n + sum(1+Ri) with i from 1 to n-1 Similar expression for R_n-1 By subtracting, the big sums mainly delete each other and we obtain R_n - R_n-1 = 1/n

[@Bealz709]

My guess is 3.3219. I guessed log base 2 of 10.

[@xyz39808]

aka half an order of magnitufe

[@1992jamo]

log base 2 of width was my first instinct too

[@XenoksPL]

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

[@GGGaming-Dooby]

@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.

[@luke1876]

That is my guess too.

[@mortenrl1946]

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

[@versacebroccoli7238]

Thank you for sharing your code and keeping it up years later. It's always helpful.

[@WaywardBrigand]

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.

[@tabbytacocat]

WaywardBrigand my thoughts exactly

[@sadrien]

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.

[@markstanbrook5578]

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.

[@WaywardBrigand]

Those are good points

[@anuraaggad]

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)

[@PanicProvisions]

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

[@dabeamer42]

"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.

[@rateeightx]

*Ponders The Question For A Few Moments* "Yeah This Is Pretty Hard, Especially For Someone With Basically No Understanding Of Maths."

[@spawnofspaun]

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

[@themathhatter5290]

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.

[@karlmuster263]

The expected value will be a decimal, so no need for ceiling. It gives you 3.3 for n=10, which is pretty reasonable.

[@themathhatter5290]

@@karlmuster263 Yeah, you're right. I knew as soon as I had posted, but I forgot how to edit on mobile.

[@stevethecatcouch6532]

"A frog can never cross the same river twice." - Heraclitus's frog

[@Mdmsaturnia]

Steve the Cat Couch LOL

[@akabret]

I got 2.928952, using "poor man's recursion" in Excel -- meaning I figured out the average number for 1 pad (1 hop) then for 2 (1.5 hops), then 3 hops...where each one references the earlier numbers. It felt legit, but then I saw on the video (at 3:38) the author shows his monte carlo simulations and his number was 2.92844 -- super close to my 2.928952, and his numbers for 1-9 pads were crazy close, too. (Bear in mind that he's approximating, and so will necessarily have a little bit of "noise".) Finding the generalizable equation was trickier, but I have that, too! I looked at the average number of hops for 1-10 pads, and after 20 minutes of flailing, I stumbled upon the answer. By accident, actually! It started because I noticed that for while all of the average hops were different, that the average difference between 9 pads (2.828951587 ) and 10 pads (2.928951587) was exactly .1. Then I noticed that the difference between 8 pads to 9 pads was .111 = 1/9th. And the difference between 7 pads to 8 pads is .125 = 1/8th. Amazingly, that's the answer. Specifically: For n lily pads, the average number of hops is the summation of reciprocals from 1 to n. Hence, for 10 pads it's 1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 + 1/7 + 1/8 + 1/9 + 1/10 = 2.929. To give you an idea, for 50 pads the average is 4.492, and for 100 pads is 5.18.

[@michaels4340]

Whoa, nice!

[@akabret]

Michael S I read like the first few comments and for a moment was like “I’m the only one to get the answer!!” ...and then I read further and saw that quite a few people got the answer, with distressingly/despairingly casual offhand comments like it hardly took them any thought at all. Lesson learned: No matter how smart you might think you are, there are people online who are twice as smart. That being said, thanks for the encouragement, Michael! :P

[@Cliff86]

My guess is 7381/2520 for 10 pads I've never dug around the OEIS so much before in my life

[@DekarNL]

Or 1 + 1/2 + 1/3 + ...... 1/(n-1) + 1/n

[@UmberGryphon]

@@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?

[@pauld7806]

It is Slightly higher than that.

[@simono.899]

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

[@user-vo9xo8hq9x]

What are you dying?

[@Bin216]

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.

[@nirshahar9884]

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

[@nirshahar9884]

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...

[@matthewellisor5835]

Making a poor little frog jump that path so many times is just mean.

[@nymalous3428]

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...

[@nymalous3428]

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.

[@geocarey]

Excel spreadsheet simulation. Average of 50,000 goes = 2.928

[@JohnMiller-it7yy]

So much fun! For the problem as initially given, the average number of jumps needed would be 5.5 jumps. The formula for determining the average number of jumps required for a river of any given width would be (n + 1)/2, where ‘n’ is the number of landing places.

[@mekvanthoff4775]

Yes, (n + 1) / 2

[@Olivier-C]

Superb timing at 00:20 :)

[@idjles]

This is absolutely typical Matt Parker. Watch the timings in the video he made where he chats with himself between Sydney Harbour and London's Big Ben. kzbin.info/www/bejne/ppWwi52pqNd0os0

[@standupmaths]

Thank you! I take my comedy timing very seriously.

[@gurjassinghbatra5758]

Upon iterating the same process for 1-30 no. of leaves, I ran a logarithmic regression analysis on the observations and found the answer for n no. of expected jumps to be y = 0.9146*ln(x) + 0.8523 with an R-squared value of 0.99, where x is the no. of leaves in front of the frog. Upon putting in 10, we get the answer as 2.9582.

[@TophTheMelonLord]

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.

[@sachinsahay1113]

My guess is 7381/2520 (that is, 1+1/2+1/3+...+1/10)

[@andreyshapiro3676]

wait, I think that's actually right, I tested it up to 5 and the pattern holds

[@UnssenX]

Correct! 7381/2520 (1+1/2+1/3+...+1/10) is the answer, which is 2,92896825396825 ... according to excel.

[@TheDesasterer]

seems correct, my simulation approximated 2.92891028 for 10^8 executions

[@JJordanob123]

I've got the same answer!

[@stevemcpherson3122]

This is correct. I gave a full inductive proof in my comment.

[@IsYitzach]

My guess is 5.5. Further my guess for n landing places is (n+1)/2.

[@Veggie13]

I thought I solved the problem and this is exactly what I got. If we're right, good guess!

[@martinpaulsen1592]

When I worked it out, I also got 5.5 - I didn't try generalizing. On the other hand, now my gut distrusts my methodology, because it feels like logarithms should come into it somewhere.

[@thekeytoairpower]

I think you guys calculated the average landing point of the first jump, not the number of jumps.... (having read this I worked out that this is what my girlfriend did when I showed her the video). The expected landing point of the frog is always half the remaining distance. On the first jump that is half way between the 5th and 6th lillypad. It is a good start and from an engineering point of view if you round to the nearest pad you will get three jumps, which again from a real world engineering as opposed to a statistics point of view is the correct answer. If you don't use rounding I think you end up with an answer of infinity because you fall into the Zeno's paradoxes (specifically the dichotomy problem and to a lesser extent Achilles and the tortoise).

[@RaveScratch]

Just as a guess, I want to say 3 for ten jumps. I assume it has something to do with: Given a(j) integer, 1 =< aj =< n; P[ sum(j=1 -> m)[a(j)] >= n] = (sum(i=1 -> n)[i^m])/(n^m)) Then find m, an integer, which maximizes the probabilty depending on n. Essentially, f(n)=m then find n0 s.t. f(n) =< f(n0). Also, when coming up with that formula, I had to deal with lattice points, so someone with a better background in complex variables and/or abstract algebra could probably figure this out without the formula.

[@pyglik2296]

Me watching this video: Oh, I know what frog problem it's gonna be! No, it's probably that other frog problem I know. Ok, how many frog problems are there in maths?!

[@nilen]

Pyglik about 10