Matt uses a light themed IDE. That's all you need to know about Matt.
@sam20265 жыл бұрын
Light theme is better
@wyattsheffield61305 жыл бұрын
@@sam2026 brave
@a_guy_in_orange72305 жыл бұрын
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_5 жыл бұрын
You're a modern day hero.
@sam20265 жыл бұрын
Wyatt Sheffield /r/unpopularopinions
@binaryagenda5 жыл бұрын
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.
@gwendolynprovost1915 жыл бұрын
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.)
@CheaterCodes5 жыл бұрын
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-rw6un5 жыл бұрын
That was much easier than my approach, thanks.
@VincentZalzal5 жыл бұрын
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!
@VincentZalzal5 жыл бұрын
@@dominiquefortin5345 But... 1.5 is indeed the second term of the harmonic series (E[2] in the notation above).
@davidhendrickson95505 жыл бұрын
Why did the frog cross the river 10,000 times? To avoid a probability quiz.
@budesmatpicu39925 жыл бұрын
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)
@theRealPlaidRabbit5 жыл бұрын
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?"
@thinboxdictator67205 жыл бұрын
@@theRealPlaidRabbit did you ask?
@evinliang98144 жыл бұрын
the frog crossed the river 2520 times
@benh83124 жыл бұрын
@@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?
@callbackspanner5 жыл бұрын
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.
@anthonyl30655 жыл бұрын
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
@EricBliesener5 жыл бұрын
@@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.
@anthonyl30655 жыл бұрын
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-Rete5 жыл бұрын
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.
@rescuecatHQ5 жыл бұрын
Ok, lets go with that. P.S. what did that mean?
@mihaimaruseac5 жыл бұрын
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.
@nicholasfrieler50054 жыл бұрын
I got the same answer but I used expected value
@jackhanke3434 жыл бұрын
I got the same answer as well.
@shawnsatterthwaite79684 жыл бұрын
I just got there too, great job!
@oliverpackham62783 жыл бұрын
He said 10 landing places not lillys, you did it with 11 landing places.
@lordknight43912 жыл бұрын
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)
@karibui4945 жыл бұрын
Initial reaction: "It's obviously 3" Make a simulation of just one iteration: get 3. Leave satisfied
@HollywoodF15 жыл бұрын
Fall-back plan: Hit the button a couple of times until you get three.
@Atlessa5 жыл бұрын
I glanced at your avatar and instantly teared up...
@sighthoundman4 жыл бұрын
@@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.
@deSolAxe4 жыл бұрын
strange, my guess was 3 or 4... without even thinking about it... i wonder why 3 would be so "obvious"...
@soumilshah10075 жыл бұрын
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.
@soumilshah10075 жыл бұрын
Thus, for n=10 it's 2.92897
@michael_betts5 жыл бұрын
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)
@Victor4X5 жыл бұрын
@@soumilshah1007 This is about the same answer as I'm getting with my simulation. Nice!
@tommywareing92345 жыл бұрын
I've got 2.929036 through simulation 1 million frogs. That sounds believably correct to me :)
@soumilshah10075 жыл бұрын
@@tommywareing9234 nice, close enough.
@alexgabel43795 жыл бұрын
Problem: ...and do NOT use recurrence relations. Parker Solution: So I used a recurrence relation.
@alcesmir5 жыл бұрын
Technically it was stated that a recurrence relation would not suffice as an explicit formula. Too bad there is no explicit formula for this.
@GnI19915 жыл бұрын
@@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).
@DDvargas1235 жыл бұрын
@@GnI1991 I think what alcesmire meant was closed form. like how the summation of an algebraic sequence is n/2(first+last)
@alcesmir5 жыл бұрын
@@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.
@carly09et5 жыл бұрын
10/[1+e] , the general is n/[1+e]
@yagoduppel5 жыл бұрын
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.
@yagoduppel5 жыл бұрын
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.
@presto70911 ай бұрын
@@yagoduppel So for us not math guys what is the answer for 10 lily pads?
@wbfaulk8 ай бұрын
@@presto709About 2.93. So 3.
@benconnor90123 күн бұрын
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.seconds5 жыл бұрын
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.
@casperycghost5 жыл бұрын
Exactly!
@franchello11055 жыл бұрын
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.
@zaraimpala39625 жыл бұрын
We all know frogs go "La di da di da"
@BoyKissBoy5 жыл бұрын
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!
@CauchyIntegralFormula5 жыл бұрын
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.
@lolledopke5 жыл бұрын
"import random" inside a while loop, that's some classic Parker Python Programming
@GvinahGui5 жыл бұрын
@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.
@BoyKissBoy5 жыл бұрын
@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.
@dansheppard29655 жыл бұрын
@@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!
@toddgerdy24655 жыл бұрын
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.
@12tone5 жыл бұрын
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.
@hls69253 жыл бұрын
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.
@theaxer37513 жыл бұрын
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 😅
@crjtodd2 жыл бұрын
@@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
@hls69252 жыл бұрын
@@crjtodd Sounds about right, Chris! BTW how long did your JS run for? Bit faster than my Basic, I'll bet!
@LactatingBadger5 жыл бұрын
Matt: Uses python, the king of languages for quick and dirty solutions. Also Matt: Does analysis in Excel
@SenselessUsername5 жыл бұрын
Well I do feel dirty after having used it, so they fit together.
@lokedhs5 жыл бұрын
Not a great choice for simulations given how slow it is.
@distantignition5 жыл бұрын
@@lokedhs Yep. Performance is of the utmost necessity in this instance.
@LactatingBadger5 жыл бұрын
@@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!
@Huntracony4 жыл бұрын
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
@smergthedargon89744 жыл бұрын
You: Jumping hurdles I, an intellectual: *_AUTOFROG ENABLED_*
@daminox4 жыл бұрын
I want an AUTOFROG ENABLED bumper sticker
@Jones12ax75 жыл бұрын
I'll try with real frogs. Simulations are not precise enough. 😂
@mokopa5 жыл бұрын
I'm happy with my spherical frogs
@oximas5 жыл бұрын
I know righy😂hopefully you have frogs around
@Elnadrius5 жыл бұрын
@@mokopa in vacuum?
@texdrieschner20125 жыл бұрын
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?
@texdrieschner20125 жыл бұрын
@@pilattebe Haha RIGHT!
@-nepherim5 жыл бұрын
I'm going with 3. Because that seems right based on the frogs in my head.
@xander10525 жыл бұрын
that's pretty damn close to what people calculated using Python of 2.928968.... for n=10
@tobiasgingerich57315 жыл бұрын
I was thinking that it was 3
@ffggddss5 жыл бұрын
@@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
@LukePalmer4 жыл бұрын
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.
@sammiddleton76635 жыл бұрын
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.
@lockaltube5 жыл бұрын
Yep, OESIS A001008 divided by OESIS A002805.
@firstnamelastname3075 жыл бұрын
it's a matter of subsets indeed
@stephenbenner43535 жыл бұрын
But if the frog jumps half then a third then a forth, etc, then he will never actually reach the other side.
@sammiddleton76635 жыл бұрын
@@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.
@stephenbenner43535 жыл бұрын
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.
@muratsaglam96715 жыл бұрын
My guess is: e This number always appear somewhere where it isn't supposed to
@standupmaths5 жыл бұрын
My first answer was “the answer to these questions is always e or 1/e”.
@punya16215 жыл бұрын
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-rv3rm5 жыл бұрын
@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
@Xnoob5455 жыл бұрын
@@standupmaths my guess is pi
@thinboxdictator67205 жыл бұрын
@@Paul-rv3rm same result here. it looks more like e
@macronencer5 жыл бұрын
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!
@MrQuickLine5 жыл бұрын
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.
@jerry37905 жыл бұрын
My guess is that it would be root 10
@herrzog6025 жыл бұрын
My bold claim is that the average number of jumps needed is Pi for any number of water lilies.
@bitequation3145 жыл бұрын
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.
@Beanlipe5 жыл бұрын
I was about to say that! hope it is pi!
@chiprock8045 жыл бұрын
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. 🤐
@krokkoguy5 жыл бұрын
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
@rdbury5075 жыл бұрын
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.
@MrBrain45 жыл бұрын
I also discovered this same expression, using A000254.
@stephenbenner43535 жыл бұрын
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.
@Aubreyously5 жыл бұрын
Guess: log base 2 of 10 Because on average, it’ll go to 5, then 7.5, then 8.75, etc
@peterkframe5 жыл бұрын
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)
@captainyager47015 жыл бұрын
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.
@Wommyo5 жыл бұрын
My guess is 3 Just feels like 3, of course, that being rounded to the nearest whole number
@gavincupps81215 жыл бұрын
I was thinking the exact same thing
@matthewjohnson36105 жыл бұрын
I started with 3, but that seems to high, so I'm going with e. Just intuition.
@skylark.kraken5 жыл бұрын
@@matthewjohnson3610 I ran 1 billion rounds and got a stable 2.9289
@user-zz6fk8bc8u5 жыл бұрын
@@skylark.kraken I calculated it and you are right. It's 2.928968254
@rateeightx5 жыл бұрын
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.
@GeekyNeil5 жыл бұрын
The answer is: integral from 0 to 1 of (x^10-1)/(x-1) = 7381/2520
@jimmythewig33545 жыл бұрын
That's spot on with the number I get when building it up recursively. Nice one. How did you get this result?
@GeekyNeil5 жыл бұрын
@@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).
@kaidatong17045 жыл бұрын
@@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.Quarantino5 жыл бұрын
Auto frog mode enabled. Don't know why I found this so funny
@RFC35144 жыл бұрын
Autofrogs fight the evil forces of the Deceptitoads.
@Twinster204 жыл бұрын
@@RFC3514 Lol, just waiting for the live action
@ludomine77465 жыл бұрын
Ben Gillot sounds like penn Gillette in disguise
@LIBICU8125 жыл бұрын
Even Penn Gillette doesn't believe in magic so every problem does have solution.
@csongorzih50945 жыл бұрын
It's Penn Jilette
@CeilingNinja5 жыл бұрын
Thanks. I knew something was wrong and I couldn't figure it out so I guessed
@callumstewart58915 жыл бұрын
I'm glad I'm not the only one who immediately jumped to that.
@mikailvandartel5 жыл бұрын
Penn Gillette, the best a man can get
@bummerlord5 жыл бұрын
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
@mattsmart42205 жыл бұрын
That's what I was going to say. You beat me to it.
@poco2s5 жыл бұрын
but does the Frog know that it lives in a simulation??
@bookslug29195 жыл бұрын
but don't you know that the frog lives in a simulation inside a simulation??
@poco2s5 жыл бұрын
:) everything makes sense now
@ThomasPlaysTheGames5 жыл бұрын
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...
@mauritswinters8665 жыл бұрын
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...
@lsj85 жыл бұрын
@@mauritswinters866 When i analyzed the 512 possibilities, I came up with 2.92896825396826
@lsj85 жыл бұрын
Using L in both places seems confusing. I think you mean sum n (1, L) { 1/n }
@tomzdotorg5 жыл бұрын
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)
@catradar5 жыл бұрын
My Guess: 2.92896825396825 jumps on average for ten landing places
@paulylewis85125 жыл бұрын
My coworker Josh had that exact answer to 10 decimals places.
@eroticpandaz15245 жыл бұрын
Yeah I got 2.92842592843 approximately
@ben.woodworth5 жыл бұрын
It's exactly 2.928968253, with the last 6 digits repeating.
@sureshpatil46155 жыл бұрын
2.9289682539682533 is the output my python script gave me.
@manueloribe91535 жыл бұрын
I got 98.5, is this correct?
@livintolearn70535 жыл бұрын
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.
@evinliang98144 жыл бұрын
congrats youre basically right
@ollib43303 жыл бұрын
exactly the same for me, 2.92 with the second decimal being 2 most of the times
@kricsek3 жыл бұрын
Thank you.
@GeminiSimulator3 жыл бұрын
I'm getting similar results at 1million iterations. 2.930, 2.929 so I think my code is working, strange feeling.
@BrianMoore-gp8ot15 күн бұрын
Its much easier to just actually simulate it. I will try doing it with rationals instead of doubles next.
@jeanf62953 жыл бұрын
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).
@idontwantahandlethough3 жыл бұрын
thanks for this!
@roeesi-personal5 жыл бұрын
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.75234 жыл бұрын
what does .93 of a jump look like again?
@LuigiBrotha4 жыл бұрын
I tried it in python and got 2.93 with simulations.
@LuigiBrotha4 жыл бұрын
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))
@hootyoo4 жыл бұрын
@@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
@marlenedietrich24684 жыл бұрын
I want to know how you wrote math fractions and symbols in a youtube comment
@glarynth5 жыл бұрын
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.
@dillongrannis82792 жыл бұрын
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.
@KnakuanaRka4 жыл бұрын
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.
@elimiuzu5 жыл бұрын
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.
@theaxer37513 жыл бұрын
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 :)
@cd2655 жыл бұрын
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
@cd2655 жыл бұрын
@Phinehas Priest Can you elaborate?
@pauloat5 жыл бұрын
@@cd265 ignore it, you are correct.
@paulgrimshaw63017 ай бұрын
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.
@marcozagaria66965 жыл бұрын
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
@punya16215 жыл бұрын
It is simple and feels right and I also checked for 3 Lily pads, it's 11/6 =[1+½+⅓] so yeah, should be correct.
@marcozagaria66965 жыл бұрын
@@punya1621 idk if there's a nice closed form
@peterjamesfinn5 жыл бұрын
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)
@matthewholmes18645 жыл бұрын
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
@ParadoxProblems4 жыл бұрын
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.
@elkudos62625 жыл бұрын
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!
@Roeming5 жыл бұрын
El Kudos that was my immediate first thought too, like a binary search, log base 2(n)
@massimogasparini18275 жыл бұрын
Actually it corresponds to H_n, so It is approximately ln(n)
@cameron73745 жыл бұрын
Solution is around 2.928968. Not sure if it goes on forever, this is just as far as C++ double precision goes.
@NaifAlqahtani5 жыл бұрын
@@cameron7374 got the same answer
@LightDhampire5 жыл бұрын
@@cameron7374 Windows Calculator (1/10 + 1/9 + ...) goes to = 2.9289682539682539682539682539683
@MsErfwe5 жыл бұрын
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_Py5 жыл бұрын
MsErfwe same result with my simulation on Python that explore every possible combination of the jumps of the frog! I think is correct!
@MWSin15 жыл бұрын
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).
@OrchidAlloy5 жыл бұрын
@@MWSin1 No, the video is asking for the answer for 10 positions. That's 9 lilypads + the opposite shore.
@MWSin15 жыл бұрын
@@OrchidAlloy You're right. I somehow misunderstood the way the question was presented.
@CrayyyCrayyy5 жыл бұрын
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 :)
@kuro13wolf5 жыл бұрын
These random capital letters are driving me insane
@kykk33655 жыл бұрын
I don't think the physical condition of the frog has anything to do with Psychology.
@alexwang9825 жыл бұрын
CGP Grey, Minutephysics, and Standupmaths are all uploading yeet
@panda42475 жыл бұрын
We shoul ask Leo Moracchioli, he ownsstudios researching this phenomenon
@mauritz39125 жыл бұрын
That is the worst joke e... have my upvote
@jacobfife72735 жыл бұрын
That took me way too long to work out
@PsychoSavager2894 жыл бұрын
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.
@Halosty455 жыл бұрын
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...
@Hamatabo5 жыл бұрын
between 3 and 4 is also the most intuitive answer, well done.
@billweasley13825 жыл бұрын
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*)
@jetison3335 жыл бұрын
@@billweasley1382 1/5
@linusnox5 жыл бұрын
I solved it using a Markov Chain: I got 2.9289682539682538 for n=10.
@Pier_Py5 жыл бұрын
Yes my simulation gives that result too! 😍
@Verrisin5 жыл бұрын
I don't know what 'Markov Chain' is... but I got the exact same result! :D I just used Kotlin instead. XDXD
@linusnox5 жыл бұрын
@@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.
@lsj85 жыл бұрын
2.92896825396826 verified with a program to simply brute force evaluate all 512 jump patterns.
@Danicker5 жыл бұрын
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...
@talroitberg59135 жыл бұрын
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.
@Utesfan1004 жыл бұрын
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
@legitgopnik84314 жыл бұрын
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)
@peterandersson38125 жыл бұрын
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!
@daanwilmer5 жыл бұрын
I have a hunch that there's a logarithm in here somewhere, so my guess is for 1+ln(n) jumps.
@punya16215 жыл бұрын
Just count for 3 or 4 and check the formula
@henryginn74905 жыл бұрын
Daan Wilmer you are actually correct (ish) as it does tend to that (almost)
@marcozagaria66965 жыл бұрын
you would be correct
@Sahil-oq8ki5 жыл бұрын
That's a very good approximation in the long run tbh
@mescad5 жыл бұрын
I think the frog is only allowed to jump to the opposite bank or on the lily pads. Using logs is cheating. :o)
@wasfas19775 жыл бұрын
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.
@wasfas19775 жыл бұрын
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.
@dansheppard29655 жыл бұрын
@@wasfas1977 *Now* I find the comments where wveryone's solved it before me in the same way, ;-) .
@UsuallyUnique5 жыл бұрын
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
@davidkennon18835 жыл бұрын
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)
@dominiquefortin53455 жыл бұрын
David Kennon It’s better start then most.
@Brooke-rw8rc5 жыл бұрын
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.
@dominiquefortin53455 жыл бұрын
Michael Timothy Yes I see that the probability of individual paths is not equal.
@davidkennon18835 жыл бұрын
@@Brooke-rw8rc you right, you right! I corrected myself in another comment, but didn't edit this one. below is my other comment
@davidkennon18835 жыл бұрын
@@dominiquefortin5345 you right, you right! I corrected myself in another comment, but didn't edit this one. below is my other comment
@Martmists5 жыл бұрын
"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
@shilangyu5 жыл бұрын
i love Matt, but python 2 in 2019 is a crime and should be punished
@DonReba5 жыл бұрын
@@shilangyu Should have used Ruby.
@CrushOfSiel5 жыл бұрын
@@DonReba I wrote my code in Fortran 90 :/
@CrayyyCrayyy5 жыл бұрын
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 :)
@samueldevulder5 жыл бұрын
Do it in LUA dudes! Real ones uses LUA.
@paulfoss53855 жыл бұрын
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.
@pmcgee0035 жыл бұрын
"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.
@jweipjklawe47665 жыл бұрын
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.31845 жыл бұрын
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
@geryon5 жыл бұрын
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-zj9xi5 жыл бұрын
geryon oh goodness that’s clever.
@tombryan77255 жыл бұрын
geryon This is the method I used as well.
@Pier_Py5 жыл бұрын
My simulation on Python gives me that result!
@Pier_Py5 жыл бұрын
With more than hundred milion iters it gives approximatly a value of 2.928ecc..
@Pier_Py5 жыл бұрын
geryon obv i did a very simple program for Python so it approach that result veeeeeery slowly
@rbr47845 жыл бұрын
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?
@rbr47845 жыл бұрын
@@Dziaji woohoo
@DarA-ud4qm5 жыл бұрын
I got the same solution :D
@rbr47845 жыл бұрын
@@DarA-ud4qm nice!
@louisheyyyy5 жыл бұрын
Isn't this what they call a recursive relation?
@anneaunyme5 жыл бұрын
@@louisheyyyy It is. Still the result is correct, even if it doesn't answer the question of the problem.
@marshallposner5 жыл бұрын
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.
@Syncromatic5 жыл бұрын
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”.
@HoTag5 жыл бұрын
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
@simiansam51795 жыл бұрын
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.
@jaroslavzeman89594 жыл бұрын
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.
@aeonsiege18065 жыл бұрын
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
@aeonsiege18065 жыл бұрын
Input this in Wolframalpha Abs(StirlingS1[n+1, 2])/fact(n)
@murmurmerman5 жыл бұрын
Fun problem. But what if the frog is climbing a sand dune, such that every time it lands, it slides back one spot?
@nicholasfrieler50054 жыл бұрын
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?
@nicholasfrieler50054 жыл бұрын
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.
@henryginn74905 жыл бұрын
I got that it is the sum of the harmonic series
@henryginn74905 жыл бұрын
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
@sylvar815 жыл бұрын
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
@Bealz7095 жыл бұрын
My guess is 3.3219. I guessed log base 2 of 10.
@xyz398085 жыл бұрын
aka half an order of magnitufe
@1992jamo5 жыл бұрын
log base 2 of width was my first instinct too
@XenoksPL4 жыл бұрын
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-Dooby4 жыл бұрын
@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.
@luke18764 жыл бұрын
That is my guess too.
@mortenrl19465 жыл бұрын
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.
@WaywardBrigand5 жыл бұрын
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.
@tabbytacocat5 жыл бұрын
WaywardBrigand my thoughts exactly
@sadrien5 жыл бұрын
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.
@markstanbrook55785 жыл бұрын
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.
@WaywardBrigand5 жыл бұрын
Those are good points
@anuraaggad5 жыл бұрын
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)
@PanicProvisions5 жыл бұрын
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)))
@dabeamer425 жыл бұрын
"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.
@rateeightx5 жыл бұрын
*Ponders The Question For A Few Moments* "Yeah This Is Pretty Hard, Especially For Someone With Basically No Understanding Of Maths."
@spawnofspaun5 жыл бұрын
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
@themathhatter52905 жыл бұрын
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.
@karlmuster2635 жыл бұрын
The expected value will be a decimal, so no need for ceiling. It gives you 3.3 for n=10, which is pretty reasonable.
@themathhatter52905 жыл бұрын
@@karlmuster263 Yeah, you're right. I knew as soon as I had posted, but I forgot how to edit on mobile.
@stevethecatcouch65325 жыл бұрын
"A frog can never cross the same river twice." - Heraclitus's frog
@Mdmsaturnia5 жыл бұрын
Steve the Cat Couch LOL
@akabret5 жыл бұрын
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.
@michaels43405 жыл бұрын
Whoa, nice!
@akabret5 жыл бұрын
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
@Cliff865 жыл бұрын
My guess is 7381/2520 for 10 pads I've never dug around the OEIS so much before in my life
@DekarNL5 жыл бұрын
Or 1 + 1/2 + 1/3 + ...... 1/(n-1) + 1/n
@UmberGryphon5 жыл бұрын
@@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?
@pauld78065 жыл бұрын
It is Slightly higher than that.
@simono.8995 жыл бұрын
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-vo9xo8hq9x5 жыл бұрын
What are you dying?
@Bin2165 жыл бұрын
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.
@nirshahar98845 жыл бұрын
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).
@nirshahar98845 жыл бұрын
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...
@matthewellisor58355 жыл бұрын
Making a poor little frog jump that path so many times is just mean.
@nymalous34285 жыл бұрын
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...
@nymalous34285 жыл бұрын
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.
@geocarey5 жыл бұрын
Excel spreadsheet simulation. Average of 50,000 goes = 2.928
@JohnMiller-it7yy5 жыл бұрын
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.
@mekvanthoff47755 жыл бұрын
Yes, (n + 1) / 2
@Olivier-C5 жыл бұрын
Superb timing at 00:20 :)
@idjles5 жыл бұрын
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
@standupmaths5 жыл бұрын
Thank you! I take my comedy timing very seriously.
@gurjassinghbatra57585 жыл бұрын
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.
@TophTheMelonLord5 жыл бұрын
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.
@sachinsahay11135 жыл бұрын
My guess is 7381/2520 (that is, 1+1/2+1/3+...+1/10)
@andreyshapiro36765 жыл бұрын
wait, I think that's actually right, I tested it up to 5 and the pattern holds
@UnssenX5 жыл бұрын
Correct! 7381/2520 (1+1/2+1/3+...+1/10) is the answer, which is 2,92896825396825 ... according to excel.
@TheDesasterer5 жыл бұрын
seems correct, my simulation approximated 2.92891028 for 10^8 executions
@JJordanob1235 жыл бұрын
I've got the same answer!
@stevemcpherson31225 жыл бұрын
This is correct. I gave a full inductive proof in my comment.
@IsYitzach5 жыл бұрын
My guess is 5.5. Further my guess for n landing places is (n+1)/2.
@Veggie135 жыл бұрын
I thought I solved the problem and this is exactly what I got. If we're right, good guess!
@martinpaulsen15925 жыл бұрын
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.
@thekeytoairpower5 жыл бұрын
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).
@RaveScratch4 жыл бұрын
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.
@pyglik22965 жыл бұрын
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?!