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. . . .
If there are 0 places in front of the frog, we are already at the end E[0] = 0. If there are n places in front of the frog, then for each of the places (on which we land with probability 1/n) we have the expected number of jumps from there, plus the one jump to get there from the current position. E[n] = 1 + 1/n sum (i=0..(n-1)) E[i] Similarly, if there are n-1 places in front, we have: E[n-1] = 1 + 1/(n-1) sum (i=0..(n-2)) E[i] If we scale them appropriately and take the difference, we get: n E[n] - (n-1) E[n-1] = n - (n-1) + E[n-1] Solving for E[n], we obtain: E[n] = E[n-1] + 1/n This recurrence relation is immediately recognisable as the harmonic series sum (i=1..n) 1/i = 1 + 1/2 + 1/3 + 1/4 + ... + 1/n. The partial sum of this has no closed-form formula. For n=10 though we get the 10th harmonic number which is 7381/2520. It's well known that the harmonic series does not converge, but its growth is incredibly slow. The harmonic numbers can be approximated by ln(n) + 0.5772156649 (where this 0.577... is the Euler-Mascheroni constant). So even with 12000 lily pads there will less than 10 jumps on average. And with 1.5×10⁴³ lily pads there are less than 100 jumps on average.
I also got the partial sum of the harmonic series in a similar way. It was less obvious because I initially expressed it as E[n] = (1/n)S[n], where S[n] = ((n+1)/n))S[n-1] + 1 but I eventually got there by rearranging the terms in the series to get S[n] = n!/(n-1)! + ((n!/2!)/((n-1)!/1!)) + ((n!/3!)/((n-1)!/2!)) + .... + ((n!/(n-1)!)/((n-1)!/(n-2)!)) + ((n!/n!)/((n-1)!/(n-1)!)) and then simplifying. (Hope I didn't make any mistakes copying it over, I wasn't really using proper notation on my scratch paper.)
Nice! I got the exact same solution in a few minutes, but I didn't double check it. But the top comment is always right isn't it? So I'll just accept this as confirmation :) Edit: wait, this isn't top comment? Is UA-cam lying to me?
let's add our beloved usual scorpion, it will be more fun... e.g. "frog in a fog", can't see anything, with unknown number of (say equally spaced) leaves to jump - and that carried scorpion is quite odd, so it strikes (and kills the frog) only when the last jump is an odd one (i.e. making the one very long jump a deadly option)... what's the best strategy? (or if it is too easy, then our scorpion is an prime mathematician and stays quiet only when the last jump is a PRIME (bigger than one)
Truth: I was out driving the other day and happened to see in my rearview mirror a chicken crossing the road behind me. I thought, "Who knew they actually did that?"
@@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?
The obvious starting point was to solve via recursion. Since landing with any number of pads remaining is the same as a problem starting with that many pads. For n possible spots, the answer is 1 (the frog must hop once now) plus 1/n * the solution for each smaller problem of i steps between i=1 and i=n-1 (the pads it might land that would require a further solution). But recursion is inefficient. Solving the same problem multiple times is often unnecessary. That's the case here were we just need to know the solution for each smaller n down to n=1. Instead of recursion, we can just keep a list of previous solutions as we work up. So f(n) = (f(1)+f(2)...f(n-1))/n +1 But again, we don't need each individual solution, just the running sum of solutions. And that sum is ingrained in each solution, so we don't need to keep a separate running total. We just need to know the values of n-1 and f(n-1). We just squash f(1)+f(2)+...f(n-1) into a variable for the running sum r, we get f(n)= r/n+1, and from that can see that r= n*(f(n)-1). Plug that in to get the old running sum from f(n-1) and we get f(n) = (f(n-1)+((n-1)*(f(n-1)-1)))/n + 1 Simplify f(n) = (f(n-1)+(n-1)*f(n-1)-(n-1))/n + 1 f(n) = (n*f(n-1)-n+1)/n + 1 f(n) = f(n-1) - n/n +1/n + 1 f(n) = f(n-1) + 1/n Which is kind of amazing. That's the algebraic notation for the harmonic series. The frog problem is the harmonic series. (n=10 is 7381/2520). But knowing that it is the harmonic series, we need to re-examine the problem to find the real beauty here. There is a 1/1 chance that the frog reaches the far bank eventually. But there is also a 1/2 chance that the frog visits the last lily pad along his journey. Which makes sense. At any step, no matter how far back the frog is, there are equal chances of landing on that pad or skipping it to the end. There are also chances of landing on a pad before it, but those chances don't matter since no matter where else the frog lands, a jump from that spot also holds to the equal probability of landing on or skipping the last pad. And this continues. For the pad before that, there are 2 chances to skip it and 1 to land on it. 1/3 odds that pad is visited. 1/4 for the pad before that, then 1/5, 1/6, etc. All a clever disguise for the harmonic series in probability.
I did the exact same thing except I included f(0) in the sum, so f(0)+...+f(n-1) and I used sigma notation instead of r, allowing me to isolate the sum, add one more term, and show f(n) + 1/(n+1) = f(n+1). With f(0)=0, f(n) = sum of 1/k from 1 to n
@@anthonyl3065 but why exactly would you need f(0) in this problem? I know it's the classic engineer vs. mathematician dilemma here but 0 is clearly not in the domain.
Eric Marcel I included f(0) because of how I considered the recursive function. I thought about it as the average of f of how many pads left. So on the first move it can jump 1 to n so the pads left are 0 to n-1. As for 0 not being in the domain, it is. Conceptually that means the frog starts where it wants to end, which makes f(0)=0. It also follows the harmonic series as the sum of 0 elements is 0. Of course you can ignore f(0), but personally I find the reasoning more consistent.
That's about what I did as well though I also would use sigma notation for a final solution, and my guess was sqrt(10) so I was only 7.38% off, but I suppose I'll be beaten by everyone who guessed 3 and was only 5.1% off. Also, I did this in only 30 min, and wasn't really trying to go fast. Kinda surprises me that Matt and co didn't solve this while still at the bar.
@@alcesmir "Too bad there is no explicit formula for this." Why do you think so? It was already stated in the comments, that the explicit formula is Σ(1/n).
@@GnI1991 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.
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.
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)
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.
I did it by working back from a recursive relation and got the same answer. UA-cam comments are not great for math f(N) = (sum from k=1->N-1 (1+f(k))/N )+ 1*(1/N) (there is an equal chance to jump to any lilypad, or the bank f(k) is the answer for the lilypad k away from the bank (1 jump there plus answer previously calculated), and a 1/N chance to jump to the final space. N is number of spaces to the end. f(N) = (sum from k=1->N-2 (1+f(k))/(N-1))*((N-1)/N) + (f(N-1)+1)/N = (f(N-1)*(N-1) + (f(N-1)+1))/N = f(N-1)*N/N + 1/N = f(N-1)+1/N f(N) = sum from k=1->N (1/N)
@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.
@K.D.P. Ross "What a brilliantly designed language" Well, I think it is, just not in the way you mean. It's brilliantly designed, because it will let someone at Matt's level of knowledge quickly program a thing like this, and have it do exactly what he needs it to do. I think that is something to be appreciated. But yes, from a language theory point of view, it leaves much to be desired.
@@BoyKissBoy Exactly. Python is a brilliantly designed language for throwing maths and science together. I spend my days writing Rust and have grown to think of it a s brilliantly designed (currently with rough edges) but at no point did I consider reaching for rust when checking my solution! I used to write an awful lot of perl for this so appreciate python's brilliance in this area!
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.
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.
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.
I'm not a mathematician, so please excuse me if I'm asking stupid questions, but that harmonic series thing looks to me like it's recursive? (Not saying it's invalid or anything, just wondering if it's a solution within the restriction of "no recurrence", because I want to learn.) And regardless: Thanks for sharing!
I did not expect to see an obscure DJ TECHNORCH username in the middle of my math puzzle binge. I had the same solution too. You might be me from a parallel universe.
@@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.
My initial guess was that it'd be a little bit over 3, because on average it jumps halfway so you'd expect somewhere around log2 of the number of starting jumps.
Only just seen this puzzle; I wrote a 24-line BBC BASIC program (BEEBEM emulation as a Master 128), and ran it with different loop options e.g. 10 times, 100 times etc. The run of 100,000 times consistently gave an average number of steps between 2.92 -> 2.93 steps per river crossing. The execution time was approximately one hour for each 100,000 loop. Program available for anybody interested. Let me know via this link.
That's what I thought as well, a couple of seconds after I heard the full description of the problem. However since the end pad is separate I think the general formula is log2(n+1). Since I'm not a real mathematician, I can't be bothered to actually make a proof though 😅
I went nearly crazy with this problem until I finally realized it's just the harmonic series... Wow, that was a lot of hours to in the end get to such a simple answer. If it wasn't for your Parker Square video, I might have given up or not even tried though, so thank you Matt.
Somebody else has already posted their answer (much quicker than me) but I'll just write it the way I worked it out (very similar though): Let S(n) = Sum (E(i)), i=1,...,n-1. Then E(n)=1+1/n * S(n) = 1 + E(n-1)/n + 1/n * S(n-1) = 1 + E(n-1)/n + (n-1)/n * 1/(n-1) * S(n-1) = 1/n + E(n-1)/n + (n-1)/n * (1+1/(n-1)*S(n-1)) = 1/n + E(n-1) So with every increase of n by 1, we increase E(n) by 1/n, which means E(n) is just 1+1/2+1/3+1/4+...+1/n, i.e. the partial sum of the harmonic series up to the nth term.
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.
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?
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.
@@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
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 ...
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.
@@stephenbenner4353 I'm not saying that the frog crosses in the those steps, but that the expected numbers of jumps are the partial sums of the harmonic series, and as the frog can only take positive integer jumps, it will cross a river of width n in a minimum of 1 jump and a maximum of n jumps. Additionally, the harmonic series diverges - if you keep adding terms, the partial sums will increase without bound: The terms between 1/2^(n-1) and 1/2^n are all >= 1/2^n and there are 2^(n-1) of them, so their sum is at least 2^(n-1)*1/2^n=1/2. The sum of the harmonic series is thus greater than the sum of an infinite number of 1/2's, which is self-evidently a divergent series, and so the harmonic series is itself divergent.
Sam Middleton I was assuming the frog’s name was Achilles, but then there wasn’t a tortoise in the equation. Your working out reminded me of Zeno’s paradox, but of course we know that Zeno’s paradox is false.
It can’t be an irrational number. There is a finite number of ways it can get to the end and when you calculate the expected value you’re going to be adding up number of jumps with their associated probabilities. All the probabilities are rational because there is a finite number of ways of getting to the end (a little hand wavey but you get the idea)
If you average out your first two jumps there you get an average jump distance of 3.75. Goal would be achieved or exceeded in 3 jumps. The problem with this answer is assuming that the second jump has a max value of 5 and not 10. If it is 10 the answer would be a 2 jump average. Im going with 3 since it makes my brain happier.
With some tedious calculations by hand an interesting pattern emerges: The fraction can be expressed as the unsigned stirling numbers of the first kind (A000254) of n divided by n! 1/1 (or 1/1!) 3/2 (or 3/2!) 11/6 (or 11/3!) 25/12 (or 50/4!) 137/60 (or 274/5!) 49/20 (or 1764/6!) 363/140 (or 13068/7!) This function is given as a(n)=n*a(n-1)+(n-1)! so the function we are after can be written as c(n)=a(n)/n! as a bonus here is a small c program to compute it: float c(int n){ return (float)a(n)/factorial(n); } int a(int n){ if(n==0) return 0; return n*a(n-1) + factorial(n-1); } int factorial(int n){ int r = 1; for(int i=1;i
This isn't too hard to prove with generating functions: Let P(n, t) is the g.f. for the probability that it takes k steps. If P'(n, t) is the same restricted to the case where the first jump is 1 then P'(n, t) = (t/n)(P(n-1, t) and if P''(n, t) is the same restricted to the case where the first jump is >1 then P''(n, t) = ((n-1)/n)(P(n-1, t). Add these to get the recursive formula P(n, t) = (t+n-1)P(n-1, t)/n. An easy induction then gives P(n, t) = (t/1)((t+1)/2)((t+2)/3)...((t+n-1)/n). The numerator is the g.f for the Sterling numbers and the denominator is n! You can get the expected value as a partial sum of the harmonic series (found by numerous other commenters) using logarithmic differentiation on the g.f. I like the way the problem is presented; no solution or even hints but a look at how people actually tackle something like this. Lot's of arcane diagrams and formulas, dead ends and mistakes being scribbled out, and the feeling of accomplishment when all that results in an answer, that's where the fun is, not the dry exposition you get in classrooms and textbooks.
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.
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
@@jimmythewig3354 I worked it out from the harmonic series posted by others: 1/1+1/2+1/3+...1/10. One way to get that division is through integration of a power of x: I knew that the integral of x^n is x^(n+1)/(n+1). So I thought perhaps the series can be evaluated as x^1/1+x^2/2+x^3/3...+x^10/10 with x set to 1. Working backwards, that expression is the integral of x^0+x^1+...+x^9. Setting the limits to 0 and 1 gives the right value since the first polynomial evaluates to zero when x=0. Playing around a bit allows this second polynomial to be simplified by multiplying by (x-1) giving x^10-1 since all the powers in between cancel. [It's useful to set x=10 to see how this works: (10^10-1)/(10-1) = 9999999999/9 = 1111111111 = 10^9+10^8+...+10^0] So that means the second polynomial is (x^10-1)/(x-1).
@@GeekyNeil I think this vid overhyped the problem. I think of it as at x away from destination, there's a 1/x chance of spending 1 turn to go to position x-1, and a (x-1)/x chance of spending 0.
Solution before watching video. For length of path L, the expected amount of jumps will be sum (1,L){1/L}. for example, a length of 10 has an expected jump amount of 1+1/2+1/3+1/4...+1/9+1/10, = 2.929...
Just Thomas : Great answer, I found 2,9289630180776 through analyzing all possible 512 jump sequences, their respective chances and multiplying. Its really close to your answer (2,928968254) - I wonder what causes the difference...
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)
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...
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*)
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!
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).
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.
from random import randint from statistics import mean def frogsteps(step_number): step_count = 0 all_steps = [] while step_number != 0: all_steps.append(step_number) step_number = randint(0,step_number-1) step_count += 1 return step_count tried = [] for i in range(100000): tried.append(frogsteps(10)) print(mean(tried))
@@LuigiBrotha I took your code and modified it to crunch the numbers for more jumps. It's currently melting my tablet but here are some results: for 0, the mean is 0 for 1, the mean is 1 for 2, the mean is 1.500251 for 3, the mean is 1.832828 for 4, the mean is 2.082564 for 5, the mean is 2.283227 for 6, the mean is 2.448204 for 7, the mean is 2.591892 for 8, the mean is 2.716641 for 9, the mean is 2.830429 for 10, the mean is 2.927934 for 11, the mean is 3.021966 for 12, the mean is 3.102178 for 13, the mean is 3.179268 for 14, the mean is 3.249788 for 15, the mean is 3.319182 for 16, the mean is 3.38179 for 17, the mean is 3.43938 for 18, the mean is 3.494447 for 19, the mean is 3.55039 for 20, the mean is 3.595437 for 21, the mean is 3.645943 for 22, the mean is 3.692473 for 23, the mean is 3.73674 for 24, the mean is 3.776979 for 25, the mean is 3.817263 for 26, the mean is 3.85587 for 27, the mean is 3.888344 for 28, the mean is 3.927704 for 29, the mean is 3.960723 for 30, the mean is 3.997292 for 31, the mean is 4.027499 for 32, the mean is 4.05669 for 33, the mean is 4.089136 for 34, the mean is 4.11915 for 35, the mean is 4.146011 for 36, the mean is 4.173906 for 37, the mean is 4.204187 for 38, the mean is 4.22523 for 39, the mean is 4.254671 for 40, the mean is 4.280237 for 41, the mean is 4.302223 for 42, the mean is 4.326161 for 43, the mean is 4.34952 for 44, the mean is 4.37019 for 45, the mean is 4.396291 for 46, the mean is 4.414632 for 47, the mean is 4.436148 for 48, the mean is 4.458545 for 49, the mean is 4.482059 for 50, the mean is 4.50089
You left out the best part! The expected number of jumps for n-1 lilypads (n including the bank) is the partial sum of the harmonic series up to n which is such a beautiful result! (i.e. E(n) = 1/1 + 1/2 + 1/3 + 1/4 ... + 1/n) You can prove this using strong induction and the recurrence relation that Matt presented in the video (E(n) = 1 + ΣE(k) from k=1 to k=n-1). Therefore the expected number of jumps for 9 lilypads is 1/1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 + 1/7 + 1/8 + 1/9 + 1/10 = 2.9289...
I 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
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
Since there are 10 spaces, my first intuition is to get the average outcome of rolling a 10-sided dice, giving me a 5.5 which I'll round to 6. I'll be left with 4 more spaces where I'll repeat again, giving me 2.5. I'll round to 3, now I left 1 space. So, my guess is 3 jumps.
Why round during your calculations giving a less precise answer. There is nothing stopping you from having a theoretical four-and-a-half sided die with an average of 2.75, unless you want to verify it with real life experiments :)
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.
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.
The result is the harmonic series (H(n)=sum[1/i] from i=1 to i=n) and the proof (although it took me a while to come up with it) is quite simple: I'll prove it by induction. First we define A(n) as the expected number of jumps if the frog starts in the nth spot with its target being spot 0. We calculate one term A(1)=1 (this is evident). Then we assume it true until A(n-1) and prove it for A(n). We'll calculate A(n)=(1/n)*p1+((n-1)/n)*p2 where p1 is the expected number of jumps given it lands on the adjacent spot and p2 the expected number of jumps if it doesn't (both including the initial jump). The frog has a 1/n chance to move only 1 spot which would give it (if it did) an expected number of jumps of 1+A(n-1) (once it's in the n-1 spot it will continue as if it started there no matter where it actually started). So p1=1+A(n-1). If it jumps to any other spot (with a chance of (n-1)/n)) since they are all equiprobable the result will be the same as if it had started in the n-1 spot (given it doesn't land in the n-1 spot the chance of it landing in any other specific spot is given by Bayes' formula 1*(1/n)/((n-1)/n)=1/(n-1) which is obviously the same probability as if it had started in the n-1 spot. Giving us the second term A(n-1). Now we add both terms A(n)=(1/n)*(1+A(n-1))+((n-1)/n)*A(n-1)=(1/n)+A(n-1). Since we are proving it by induction we assumed that A(n-1)=H(n-1) and we've proven A(n)=(1/n)+A(n-1)=(1/n)+H(n-1)=H(n). And since we proved A(1)=H(1) we've now also proved that A(n)=H(n) for all n whole number greater or equal to 1.
In case someone wants a more algebraic proof here's one starting from the recurrence relation (which is easy enough to deduce) that Matt shows around 4:18 (in very small steps, same definition of A(n) as before). A(n)=1+(1/n)*(sum[i=1 to i=n-1] A(i))= =1+ A(n-1)/n+ (1/n)*(sum[i=1 to i=n-2] A(i))= =1+ A(n-1)/n+ ((n-1)/n)* (1/(n-1))*(sum[i=1 to i=n-2] A(i))= =1+ A(n-1)/n+ ((n-1)/n)* (1-1+1/(n-1))*(sum[i=1 to i=n-2] A(i))= =1-(n-1/n)+ A(n-1)/n+ ((n-1)/n)* (1+1/(n-1))*(sum[i=1 to i=n-2] A(i))= Here the last term "1+1/(n-1))*(sum[i=1 to i=n-2] A(i))" is the definition via the recurrence formula of A(n-1) =(1/n)+ A(n-1)/n+ ((n-1)/n)* A(n-1)= =(1/n)+ A(n-1)*(1/n+(n-1)/n)= =(1/n)+ A(n-1) And again since we've proven A(1)=1=H(1) this proves that A(n)=H(n) for all n>1 and n being a whole number.
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!
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
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)
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.
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
This was a fun problem! My initial guess was 3, then using theory I came up with a very unforgiving formula for the probability of crossing in n-many hops which relied on nested summations. So then I used a computer to compute the expected number of hops to be about 2.928968. And then, I ran many simulations on my laptop and found the average number of hops to match the expected value I got. As for generalizing, I found that the expected number of hops grows logarithmically and will be about 0.63 + ln(n+1) for n lily pads!
I used almost exactly the same approach! I thought the logarithmic-like function was just some logarithm in some base, or log plus something or times some constant, but then I saw a comment mentioning the harmonic series... And it all made sense
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
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)
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)))
First gut estimate: The expected value for each jump is half the remaining distance. The discrete lily pads prevents Zeno's paradox, so I expect a value near log_2(n). Second shot: For 0 pads it jumps to the other side, for a value of 1. For one lily pad, it either jumps all the way, or jumps to the pad. (0+1)/2+1=3/2. For two pads, it has an average of (0+1+3/2)/3+1=11/6. For three pads, it has an average of (0+1+3/2+11/6)/4+1=25/12 For n pads, it has an average of sum( ave(i
I think you're right; I wrote a bit of code and after a million loops the average came out to be 3.0195806, remarkably close to your 83711/27720 (= 3.0198773)
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?
E(n) is the expected number of jumps, n is the number of potential banks. n = 2 being the minimum then. So E(n) = 1/(n-1) * Sigma{(lowerbound 1, upperbound n-1) n }. Sorry I couldn't get the right notations in with youtubes comment editor. So for 10 banks, it would be 5, and for 11, 5.5. This comes down to E(n) = 0.5*(n-1) + 0.5
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
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)
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.
I have to go with the partial sum of the harmonic series as well. I convinced myself by "building" the matrix of jumps. You can easily solve the 3 steps case by hand. I did it by constructing the 4 (=2^(steps-1)) x 2 (=number of steps-1, last step is always on the other side of the river). This is a boolean matrix, place a true if the frog lands there. Call it M_3. Count the jumps in each row (=number of true +1), you get the vector j_3. Compute each probability, place it in p_3. The expected value is the dot product of the j_3 and p_3. If you want to do the case 4 (=n), here is a way: Build the M_4 matrix (8×3). Fill the first column half with 'false' (=the frog did not stop on first stone) and half with true. Fill the remaining top half with M_3. Do the same with the bottom half. Convince yourself that you actually covered all possible cases. By doing so, the j_4 vector is essentially j_3 on top and j_3+1 on the bottom. The probabilities vector for the bottom part is as follow: the frog jumps on the 1st pad (1/4 of the time) and then has to solve the previous '3 step problem' (so it is 1/4 of P_3), while the top part is again P_3 but scaled with (1-1/4), because when it is not landing on the 1st stone (3/4 of the times) it is actually solving a '3 step problem'. So when you do the dot multiplication to get the probability, the top half will be 3/4×E(3), while the second will be (E(3)+1)/4. Rearrange and you get E(4) = E(3) +1/4. Do the general case in the same way, and you get that E(N+1)=E(N)+1/(N+1). Solve for base case 1: E(1)=1. Realize it is the partial sum of the harmonic series. I also tried a less recursive approach: while a pattern clearly exists and it is extremely clear and interesting, I was not able to prove it for the general case.
My guess is 5.5 (or in this case 5 and 6 jumps have the same probability of happening). I started drawing out the jumps and for any number of Lilly pads and started to notice the pascal triangle showing up as well, and after a few "simulations" on paper, I came up with the non recursive formula. f(n) = (n+1)/2 where the n is the number of jumps For the formula, I've got to it by summing all the jumps of every possible combination (using the Pascal triangle) and dividing by the numbers of tries (given by the triangle as well). This gave me a mean jump estimate, and after a few tries with different lillypad configurations, it always got me to the same solution as given by the formula
I also got 5.5, but I solved it as an expected value problem: I found the probabilities p(x) of each number of jumps x (by brute force counting) and summed the products x*p(x) for x=1,...,10.
I made the same mistake: I took every possible combination, calculated number of jumps for each, summed them together and divided by total number of combinations. But this would be right only if probability of every combination is the same, which isn't!! It can be easily seen fo the n=3. There are 4 possible combinations: 3, 2+1, 1+2, 1+1+1. There are 2 cases that start with 1, so the probability of jumping to first leaf is 1/2 and probability of jumping to second and third is 1/4. But the task says the probability of jumping to any leaf is the same, 1/3 for n=3.
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
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.
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).
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 :)
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.
The average works out to ln(n) + 0.5772156649 where n = the number of pads. approximately. It's the harmonic number series and there is no exact formula. Your heuristic was not terrible, but a little bit off.
The main reason you are a bit off is that your average jump is the median of zero and the max jump when one is the smallest available jump. So the first jump average is 5.5 not 5. When there are two options it’s 1.5 not 1.
* Spoiler for the solution possibly * After going through way more paper than I thought I would need, I've come to the solution that this is just a partial sum of the harmonic numbers? I went about solving it the same way you'd solve the coupon collector's problem in that it involved the expected value of a geometric series. I might be missing something obvious and I'm completely wrong, but my answer for a river of 10 jumps is 2.928968, and for a river of k jumps I got the sum of (1/i) for i from 1 to k, or (1/1)+(1/2)+(1/3)+...+(1/k)
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.
I initially paused the video and did what Matt did: write a program to simulate the frog loads and loads of times (although I wrote mine in Chipmunk BASIC and not Python). Over 100000 attempts, I got an average of about 2.93. Then my wife made me got to bed so I lay in bed trying to work it out in my head. I realised it would be easier to start from n=1 and work my way up and see if any pattern emerged. Fortunately, one did. For n=1, the result was obviously 1. For n=2, it was 1 and 1/2 and for n=3, it was 1 and 5/6. So the pattern seemed to indicate that for every increase of n+1, the average number of jumps increased by 1/n. My wife had fallen asleep at this point, so I quietly snuck my phone in under my pillow and opened Excel and typed it in for n=1 to 12 to see if the value for n=10 would match what my earlier program had output and it showed a very satisfying 2.928968 which, of course, pleased me immensely. :-)
I tried log base 2 of n, where n is the number of max leaps, it is fairly close when considering small n, but the result diverges from what I get in computer simulation as the n gets bigger. Somehow I managed to pull something like that: log base 2 of n - (log base 10 of n - 0.5) and this spits results very close to computer simulation (checked up to n = 100000) But I honestly don't know where does this log base 10 of n - 0.5 comes from
@Phinehas Priest I couldn't read all of your comment, but I think we did the same kind of thing. I just tried it on numbers of places to jump until 4 places, and then simplified all of the sums to find that for each space added, another number from the harmonic series was added. This essentially meant the answer for n spaces was just the partial sum of the first n numbers in the harmonic series. I graphed every result possible pretty quickly - desmos.com/calculator/jjfcqzuiv5 - and since we're looking at the harmonic series, there is no known formula to find the sum of the first n values without sigma, so I believe this is the best you can get to. With problems like these, when it's 10pm and you're too tired to think it through, trying each value of n is just the easiest way to do it, and in this case it was the quickest and easiest way to find the pattern. I don't know if it was luck, but I managed to find this in around 15 minutes.
This is what I initially came up with before I took into account the shifting of probabilities. The frog doesn't choose randomly between all possible paths though, it only chooses randomly from its current options: Every time you add a Lily pad the frog has two options for each sequence of jumps for one less pad. Either add it as a new jump or combine it with the following jump. The average jumps for N+1 pads equals the average for N jumps plus 1 plus the average for N jumps plus zero (no additional jumps if you combine it with the next jump) all over 2. Rearranging you get twice the average for N pads plus 1 all over two or more simply the average for N pads plus a half. If the frog starts out on the pad before the bank it has one way of getting to the bank and that's in one hop. A(1)=1, A(n+1)=A(N)+1/2, A(N)= (N+1)/2 Working on an actual solution now involving adding up reciprocals of permutations of products times the number of terms in that permutation.
I 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
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.
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
Dank Squidge Perhaps he lives far from anywhere Matt has toured his show, or maybe he is on the secret Mars missio... oh wait, forget I mentioned that.
I 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.
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. ua-cam.com/video/pdMZjssrAlk/v-deo.html
Guess: My answer it's three or 2.9something, but I don't know a lot of math so I just played with simple probability. You start with all the leaves having 10% chance of being chosen, but one of them is going to the other side, then if the frog goes to the last leaf it has a 100% probability of going to the other side in the next jump, as you go down the probability also goes down so for the 8th leaf it has a 50% of either going to the 9th leaf or the other side, then the 7th has 33% and so on. That ends up going to 100% combined or at least really close(I don't know how to explain it) and then you have 3 possibilities of getting 100%, meaning the average is 3 or a little less than 3, I dont know if it makes any sense at all but that's how I thought about it.
The expected number of jumps on a river of width n is just the harmonic series up to 1/n. For example if n=3, the expected number of jumps is 1 + 1/2 + 1/3. If n=10 then it's 1 + 1/2 + 1/3 + ... + 1/10, which equals 2.9289...
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.
@@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.
guess: 2.928968253968 The solution idea is as follows: first, lets enumerate the possible positions where we can be, but in reverse order, i.e. let the frog start at n and end at 0 (this makes the math slightly easier). Now we can define a function dp: N -> R, such that dp(i) gives us the expected number of jumps to get from position i to the end(position 0). We know at least the first two values of our function: dp(0) = 0, as we already are where we want to go, and dp(1) = 1, we can only jump to 0 When we are at a position i>1, there are i possible positions where we can jump to (including 0), i.e. the probability to jump to any one of them is 1/i. If we now know the expected number of jumps to get from j (with 0
I made a simulation script in python and this is almost the exact value my code was converging on after 1 million trials (2.92994892994893 was my result) script is below import random average_hops = 0 total_hops = 0 num_trials = 1000000 for trial in range(num_trials): remaining_pads = 10 hops = 0 while remaining_pads > 0: hop_length = random.randint(1,remaining_pads) #print(hop_length) remaining_pads -= hop_length hops += 1 #print(remaining_pads) total_hops += hops average_hops = total_hops/(trial+1) print(average_hops)
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.
@@zanfur But not all of this ways are equally likely. This holds only for every moment and the NEXT jump. In your example the frog has three options in the first step. So the propability for only one jump is 1/3 for the way "straight to the end". In contrast if he first hops to lily 1 (with a propability of 1/3), there are still two options for the second step each now with propability 1/2. So the way "lily 1 then skip to end" has only a propability of 1/3*1/2=1/6.
"We had an amazing time. We were all doing it on the bar. People gathered around and shouted out which angle to concentrate on next. " This is exactly what I expected Edinburgh would be like.
My simulations seem to suggest E(n) is approximated by Log(n+0.5)+γ , where γ is the Euler-Mascheroni constant. In other words, simply the sum of a finite harmonic series. Code below. import random nstart = 1 nend = 200 samplesize = 1000000 def Leap(nsteps): frog = 0 leaps = 0 while frog < nsteps: frog = random.randrange(frog+1, nsteps+1) leaps +=1 return leaps for n in range(nstart,nend+1): leaplist =[] for i in range(samplesize): leaplist.append(Leap(n)) print(n, sum(leaplist)/len(leaplist))
If you assume that once the frog reaches the final spot, it no longer slides back one space, the formula for the expected number of hops is 1 + sum from k=2 to n (where n is the number of spots on the sand dune) of 1/(k-1). This formula works for values of n > 1. The value for n = 1 is just 1 because the frog cannot slide back once it has reached the end. So, basically, it is just the 1 + the harmonic sum offset by 1.
I did a bit of figuring and research, and worked backwards a bit: using the fact that the average number of moves went up by 0.5 for every n lily pads, I used that and the number of possible sequences (2^n) to determine that the average number of moves for 10-lily is 6 moves. I had to consult OEIS to find an equation to get the number of moves by putting in the sequence (1,3,8,20,48,112,256,...) to find a(n) = (n+2) * (2^(n-1)); taking a(n)/2^n gives the average number of moves for n lily pads. I feel like that's as good of an answer as I'll be able to get. Now I can finally look at the other comments to see what everyone else came up with. I'm kind of proud that I was able to fix my initial notations to realize that 2^n played a part in everything.
Matt uses a light themed IDE. That's all you need to know about Matt.
Light theme is better
@@sam2026 brave
All you need to know about him is that he doesnt want to ruin his eyes from using dark mode when surrounded with plenty of light? nah you also need to know about this thing called a Parker Square. . . .
You're a modern day hero.
Wyatt Sheffield /r/unpopularopinions
If there are 0 places in front of the frog, we are already at the end E[0] = 0. If there are n places in front of the frog, then for each of the places (on which we land with probability 1/n) we have the expected number of jumps from there, plus the one jump to get there from the current position.
E[n] = 1 + 1/n sum (i=0..(n-1)) E[i]
Similarly, if there are n-1 places in front, we have:
E[n-1] = 1 + 1/(n-1) sum (i=0..(n-2)) E[i]
If we scale them appropriately and take the difference, we get: n E[n] - (n-1) E[n-1] = n - (n-1) + E[n-1]
Solving for E[n], we obtain: E[n] = E[n-1] + 1/n
This recurrence relation is immediately recognisable as the harmonic series sum (i=1..n) 1/i = 1 + 1/2 + 1/3 + 1/4 + ... + 1/n. The partial sum of this has no closed-form formula. For n=10 though we get the 10th harmonic number which is 7381/2520. It's well known that the harmonic series does not converge, but its growth is incredibly slow. The harmonic numbers can be approximated by ln(n) + 0.5772156649 (where this 0.577... is the Euler-Mascheroni constant). So even with 12000 lily pads there will less than 10 jumps on average. And with 1.5×10⁴³ lily pads there are less than 100 jumps on average.
I also got the partial sum of the harmonic series in a similar way. It was less obvious because I initially expressed it as
E[n] = (1/n)S[n], where S[n] = ((n+1)/n))S[n-1] + 1
but I eventually got there by rearranging the terms in the series to get
S[n] = n!/(n-1)! + ((n!/2!)/((n-1)!/1!)) + ((n!/3!)/((n-1)!/2!)) + .... + ((n!/(n-1)!)/((n-1)!/(n-2)!)) + ((n!/n!)/((n-1)!/(n-1)!))
and then simplifying.
(Hope I didn't make any mistakes copying it over, I wasn't really using proper notation on my scratch paper.)
Nice! I got the exact same solution in a few minutes, but I didn't double check it. But the top comment is always right isn't it? So I'll just accept this as confirmation :)
Edit: wait, this isn't top comment? Is UA-cam lying to me?
That was much easier than my approach, thanks.
I did the exact same thing you did, ended up with the same result: harmonic series. It is so satisfying when you find that kind of stuff by yourself!
@@dominiquefortin5345 But... 1.5 is indeed the second term of the harmonic series (E[2] in the notation above).
Why did the frog cross the river 10,000 times? To avoid a probability quiz.
let's add our beloved usual scorpion, it will be more fun... e.g. "frog in a fog", can't see anything, with unknown number of (say equally spaced) leaves to jump - and that carried scorpion is quite odd, so it strikes (and kills the frog) only when the last jump is an odd one (i.e. making the one very long jump a deadly option)... what's the best strategy? (or if it is too easy, then our scorpion is an prime mathematician and stays quiet only when the last jump is a PRIME (bigger than one)
Truth: I was out driving the other day and happened to see in my rearview mirror a chicken crossing the road behind me. I thought, "Who knew they actually did that?"
@@theRealPlaidRabbit did you ask?
the frog crossed the river 2520 times
@@evinliang9814 I made a giant excel spreadsheet to solve up to 1000 lilypads, meaning my frog may have crossed the river 1,000,000 times every time I run it?
The obvious starting point was to solve via recursion. Since landing with any number of pads remaining is the same as a problem starting with that many pads.
For n possible spots, the answer is 1 (the frog must hop once now) plus 1/n * the solution for each smaller problem of i steps between i=1 and i=n-1 (the pads it might land that would require a further solution).
But recursion is inefficient. Solving the same problem multiple times is often unnecessary. That's the case here were we just need to know the solution for each smaller n down to n=1. Instead of recursion, we can just keep a list of previous solutions as we work up. So f(n) = (f(1)+f(2)...f(n-1))/n +1
But again, we don't need each individual solution, just the running sum of solutions. And that sum is ingrained in each solution, so we don't need to keep a separate running total. We just need to know the values of n-1 and f(n-1). We just squash f(1)+f(2)+...f(n-1) into a variable for the running sum r, we get f(n)= r/n+1, and from that can see that r= n*(f(n)-1). Plug that in to get the old running sum from f(n-1) and we get
f(n) = (f(n-1)+((n-1)*(f(n-1)-1)))/n + 1
Simplify
f(n) = (f(n-1)+(n-1)*f(n-1)-(n-1))/n + 1
f(n) = (n*f(n-1)-n+1)/n + 1
f(n) = f(n-1) - n/n +1/n + 1
f(n) = f(n-1) + 1/n
Which is kind of amazing. That's the algebraic notation for the harmonic series. The frog problem is the harmonic series. (n=10 is 7381/2520).
But knowing that it is the harmonic series, we need to re-examine the problem to find the real beauty here. There is a 1/1 chance that the frog reaches the far bank eventually. But there is also a 1/2 chance that the frog visits the last lily pad along his journey. Which makes sense. At any step, no matter how far back the frog is, there are equal chances of landing on that pad or skipping it to the end. There are also chances of landing on a pad before it, but those chances don't matter since no matter where else the frog lands, a jump from that spot also holds to the equal probability of landing on or skipping the last pad. And this continues. For the pad before that, there are 2 chances to skip it and 1 to land on it. 1/3 odds that pad is visited. 1/4 for the pad before that, then 1/5, 1/6, etc. All a clever disguise for the harmonic series in probability.
I did the exact same thing except I included f(0) in the sum, so f(0)+...+f(n-1) and I used sigma notation instead of r, allowing me to isolate the sum, add one more term, and show f(n) + 1/(n+1) = f(n+1). With f(0)=0, f(n) = sum of 1/k from 1 to n
@@anthonyl3065 but why exactly would you need f(0) in this problem? I know it's the classic engineer vs. mathematician dilemma here but 0 is clearly not in the domain.
Eric Marcel I included f(0) because of how I considered the recursive function. I thought about it as the average of f of how many pads left. So on the first move it can jump 1 to n so the pads left are 0 to n-1. As for 0 not being in the domain, it is. Conceptually that means the frog starts where it wants to end, which makes f(0)=0. It also follows the harmonic series as the sum of 0 elements is 0. Of course you can ignore f(0), but personally I find the reasoning more consistent.
That's about what I did as well though I also would use sigma notation for a final solution, and my guess was sqrt(10) so I was only 7.38% off, but I suppose I'll be beaten by everyone who guessed 3 and was only 5.1% off. Also, I did this in only 30 min, and wasn't really trying to go fast. Kinda surprises me that Matt and co didn't solve this while still at the bar.
Ok, lets go with that.
P.S. what did that mean?
Problem: ...and do NOT use recurrence relations.
Parker Solution: So I used a recurrence relation.
Technically it was stated that a recurrence relation would not suffice as an explicit formula. Too bad there is no explicit formula for this.
@@alcesmir "Too bad there is no explicit formula for this." Why do you think so? It was already stated in the comments, that the explicit formula is Σ(1/n).
@@GnI1991 I think what alcesmire meant was closed form. like how the summation of an algebraic sequence is n/2(first+last)
@@GnI1991 Yeah, sorry. I meant closed form. It's not that uncommon to use the term explicit formula to mean closed form, but it's probably better to use the more specific term.
10/[1+e] , the general is n/[1+e]
The answer is the harmonic numbers (a_n = \sum_{i=1}^n{\frac{1}{n}})
Proof: Let a_n be the total number of jumps needed. We are looking for a value for a_10 and a formula for a_n. To jump n leaves the frog does one of the n possible jumps with probability 1/n to any leaf i and then has to jump a number of n - i leaves in a_{n-i} ways.
Thus, we get the recurrence relation: a_1 = 1; a_n = 1/n + 1/n(a_1 + 1) + 1/n(a_2 + 1) + ... 1/n(a_{n-1} + 1) where each +1 comes from the initial jump.
After some algebra, the recurrence is: a_1 = 1; a_n = 1 + 1/n \sum_{i=1}^{n-1}{a_i}. From here, try to get a_n in terms of a_{n-1}:
a_n = 1 + 1/n * (n-1) / (n-1) * \sum_{i=1}^{n-1}{a_i} # multiply by x/x doesn't change result
a_n = 1 + (n-1) / n * (1 / (n - 1)) * \sum{i=1}^{n-1}{a_i} # reorder factors
a_n = 1 + (1 - 1/n) * (1 / (n - 1) * \sum{i=1}^{n-2}{a_i} + a_{n-1} / (n - 1)) # extract the last term of the sum
a_n = 1 + (1 - 1/n) * (a_{n-1} - 1 + a_{n-1} / (n-1)) # use the same formula from the start but for a_{n-1}
a_n = 1/n + a_{n-1} # expand all parantheses, do algebra
But that with a_1 = 1 gives a_n = \sum_{i=1}^n{\frac{1}{n}}, the harmonic numbers.
And indeed, even experimenting we get to the same solution: a_10 = 2.92880931.
I used the following script to simulate:
import random
PRINT_EVERY = 100000
def jump(end=10):
pos = 0
ret = 0
while pos != end:
pos = random.randrange(pos, end) + 1
ret += 1
return ret
sum_jumps = 0
num_tries = 0
while True:
for _ in range(PRINT_EVERY):
sum_jumps += jump()
num_tries += 1
print("Avg {:.8f} ({} / {})".format(
(sum_jumps + 0.0) / num_tries, sum_jumps, num_tries))
And it prints:
...
Avg 2.92880365 (366686217 / 125200000)
Avg 2.92880069 (366978727 / 125300000)
Avg 2.92880195 (367271764 / 125400000)
Avg 2.92880530 (367565065 / 125500000)
Avg 2.92880385 (367857764 / 125600000)
Avg 2.92880500 (368150789 / 125700000)
Avg 2.92880931 (368444211 / 125800000)
I'm thus confident that the solution above is real and works.
I got the same answer but I used expected value
I got the same answer as well.
I just got there too, great job!
He said 10 landing places not lillys, you did it with 11 landing places.
the answer is way eaiser and simple ... if u got 10 steps then each step would either be landed by the frog or skipped .the answer is 2×2×2×2×2×2×2×2×2×2
or simply 2^10
i already tried this method manually with 2 , 3 , 4 and 5 steps and the results perfectly matchs so
the equation is 2^n (n=number of steps)
The expected number of jumps required to get to pad 'n' will be, I think, the sum of the harmonic series Hn=Σ(1/n). Matt's simulation also seems to give that result. Here's why I think that's the case:
For n=1, number of expected jumps is, trivially, one.
For n=2, initially the frog has an equal probably of jumping on both pads, thus assigning them a score of half. This means that the frog will jump on each pad 0.5 number of times. Then, on the next step, if it's on pad 2 and not the final pad, expected number of jumps is, again, 1. Thus, total for the last pad is 1+1/2
For n=3, it's 1/3 for the first pad, 1/2+1/3 for the second and 1+1/2+1/3 for the final pad.
For the general case, the total is Σ(1/n)
Edit: I think what I did is a Markov chain.
Thus, for n=10 it's 2.92897
I did it by working back from a recursive relation and got the same answer.
UA-cam comments are not great for math
f(N) = (sum from k=1->N-1 (1+f(k))/N )+ 1*(1/N) (there is an equal chance to jump to any lilypad, or the bank f(k) is the answer for the lilypad k away from the bank (1 jump there plus answer previously calculated), and a 1/N chance to jump to the final space. N is number of spaces to the end.
f(N) = (sum from k=1->N-2 (1+f(k))/(N-1))*((N-1)/N) + (f(N-1)+1)/N = (f(N-1)*(N-1) + (f(N-1)+1))/N = f(N-1)*N/N + 1/N = f(N-1)+1/N
f(N) = sum from k=1->N (1/N)
@@soumilshah1007 This is about the same answer as I'm getting with my simulation. Nice!
I've got 2.929036 through simulation 1 million frogs. That sounds believably correct to me :)
@@tommywareing9234 nice, close enough.
"import random" inside a while loop, that's some classic Parker Python Programming
@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.
@K.D.P. Ross "What a brilliantly designed language"
Well, I think it is, just not in the way you mean. It's brilliantly designed, because it will let someone at Matt's level of knowledge quickly program a thing like this, and have it do exactly what he needs it to do.
I think that is something to be appreciated. But yes, from a language theory point of view, it leaves much to be desired.
@@BoyKissBoy Exactly. Python is a brilliantly designed language for throwing maths and science together. I spend my days writing Rust and have grown to think of it a s brilliantly designed (currently with rough edges) but at no point did I consider reaching for rust when checking my solution! I used to write an awful lot of perl for this so appreciate python's brilliance in this area!
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.
It's the harmonic series.
Let E(n) be the expected number of jumps in where the frog has n possible spaces to jump to at the beginning. (i.e. n-1 lotus leaves and 1 spot for the opposite bank).
There's a 1/n chance that the frog jumps to the very next leaf, which takes another E(n-1) steps to finish.
There's a (n-1)/n chance that the frog jumps to any other spot, which is the same as taking one jump from the very next leaf, since both result in the next jump being to those spots with a uniform probability.
E(n) = 1/n * (1 + E(n-1)) + (n-1)/n * E(n-1)
E(n) = 1/n + E(n-1) / n + (n-1)* E(n-1)/n
E(n) = 1/n + E(n-1)
Putting in E(1) = 1, we get E(n) = 1/n + 1/(n-1) + 1/(n-2) + ... + 1
So yeah, E(n) is exactly the nth partial sum of the harmonic series. It grows like a harmonic series and quacks like a harmonic series.
Exactly!
I worked it out and my numbers were consistent with the harmonic seqence+1, but my f(5) value wasnt. but i reworked it and saw that it is consistent. Good job.
We all know frogs go "La di da di da"
I'm not a mathematician, so please excuse me if I'm asking stupid questions, but that harmonic series thing looks to me like it's recursive? (Not saying it's invalid or anything, just wondering if it's a solution within the restriction of "no recurrence", because I want to learn.)
And regardless: Thanks for sharing!
I did not expect to see an obscure DJ TECHNORCH username in the middle of my math puzzle binge.
I had the same solution too. You might be me from a parallel universe.
Initial reaction: "It's obviously 3"
Make a simulation of just one iteration: get 3.
Leave satisfied
Fall-back plan: Hit the button a couple of times until you get three.
I glanced at your avatar and instantly teared up...
@@pilattebe I've done this. When code testing is more important than immediate results. (Which, come to think of it ...)
It's really important to change it back BEFORE you start running simulations. But it's a really easy error to catch.
strange, my guess was 3 or 4... without even thinking about it...
i wonder why 3 would be so "obvious"...
My initial guess was that it'd be a little bit over 3, because on average it jumps halfway so you'd expect somewhere around log2 of the number of starting jumps.
Only just seen this puzzle; I wrote a 24-line BBC BASIC program (BEEBEM emulation as a Master 128), and ran it with different loop options e.g. 10 times, 100 times etc. The run of 100,000 times consistently gave an average number of steps between 2.92 -> 2.93 steps per river crossing. The execution time was approximately one hour for each 100,000 loop.
Program available for anybody interested. Let me know via this link.
That's what I thought as well, a couple of seconds after I heard the full description of the problem. However since the end pad is separate I think the general formula is log2(n+1).
Since I'm not a real mathematician, I can't be bothered to actually make a proof though 😅
@@hls6925 Similarly I wrote a javascript simulation of it and let it run a few million times and got an average of about 2.929
@@crjtodd Sounds about right, Chris! BTW how long did your JS run for? Bit faster than my Basic, I'll bet!
I went nearly crazy with this problem until I finally realized it's just the harmonic series... Wow, that was a lot of hours to in the end get to such a simple answer. If it wasn't for your Parker Square video, I might have given up or not even tried though, so thank you Matt.
Somebody else has already posted their answer (much quicker than me) but I'll just write it the way I worked it out (very similar though): Let S(n) = Sum (E(i)), i=1,...,n-1.
Then E(n)=1+1/n * S(n) = 1 + E(n-1)/n + 1/n * S(n-1) = 1 + E(n-1)/n + (n-1)/n * 1/(n-1) * S(n-1) = 1/n + E(n-1)/n + (n-1)/n * (1+1/(n-1)*S(n-1)) = 1/n + E(n-1)
So with every increase of n by 1, we increase E(n) by 1/n, which means E(n) is just 1+1/2+1/3+1/4+...+1/n, i.e. the partial sum of the harmonic series up to the nth term.
@@yagoduppel
So for us not math guys what is the answer for 10 lily pads?
@@presto709About 2.93. So 3.
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.
@@presto709 Exactly 7381/2520 or 2.93ish
I'll try with real frogs. Simulations are not precise enough. 😂
I'm happy with my spherical frogs
I know righy😂hopefully you have frogs around
@@mokopa in vacuum?
The formula is simple: 1 + 1/2 + 1/3 + ... + 1/n, if n is the number of options on the first jump (n-1 leaves in the water). The proof: it's obvious for n=1. only one option: one jump; e(1)=1. To go from e(n-1) to e(n), consider this: The chance of jumping to the first leaf is 1/n. From there, the situation is exactly the situation as for n -1, so The expected number of jumps is exactly one more (that first short jump) than the number of expected jumps for n -1. For the remaining case of not jumping to the first leaf (which happens with the remaining probability: (n-1)/n), you have the exact situation as for n -1 with the same expected number of jumps. So taking the weighted average, you get e(n)=1/n (1+ e(n-1)) + (n-1)/n (e(n-1)), which resolves to the pretty formula above. Correct, right? Does it match your experimental data?
@@pilattebe Haha RIGHT!
I 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.
My guess is: e
This number always appear somewhere where it isn't supposed to
My first answer was “the answer to these questions is always e or 1/e”.
Came out to be 11/6 for 2 lily pads. Shouldn't be e or 1/e or related. It's probably a polynomial in n
@Chris I havent proven it yet but it seems to me, that the average number for n lilly pads is 1 + 1/2 + 1/3 + ... + 1/n . So it doesnt tend to pi
@@standupmaths my guess is pi
@@Paul-rv3rm same result here.
it looks more like e
I'm going with 3. Because that seems right based on the frogs in my head.
that's pretty damn close to what people calculated using Python of 2.928968.... for n=10
I was thinking that it was 3
@@xander1052 The exact value is in fact, 7381/2520 = 3 - 179/2520 = 2.928[968253], where the bracketed part repeats ad infinitum. [ It's ∑[k=1..10] (1/k) ]
A very good rational approximation is 41/14 = 2 & 13/14.
In fact, the exact answer is 41/14 + 1/2520.
Fred
I got the same answer as Binary Agenda, going kind of backwards. First I computed the recurrence relation (same one Matt found) and computed its values. I graphed it and it looked like it was growing logarithmically, and with a little playing around I found it was growing like ln(n) + something. Looking at this difference at n=1000 to get a good estimate for something I found it was 0.577. I recognized 0.577 as a special thing but I couldn't remember what it was! I tried wolfram alpha, which is usually good for giving nearby closed forms for numbers, to no avail. (ln(sqrt(pi)) was my best guess, but it wasn't quite hitting)
Anyway... I just relaxed my mind a minute and thought, out of nowhere, we're dealing with fractions! The harmonic numbers (1/1 + 1/2 + 1/3 + ... + 1/n) grows logarithmically and is a bunch of fractions. So I tried it and it matched exactly. From there it wasn't too hard to prove that the harmonic numbers satisfied this recurrence relation, without using anything too advanced. (But not as elegantly as Binary Agenda)
And of course after this I realized what 0.577 was! The Euler-Macheroni constant -- which is *defined* as the limiting difference between the n'th harmonic number and ln(n). It's definition is exactly the context where it showed up in this problem. Why didn't wolfram alpha catch that! Come on, that's an important one! log(sqrt(pi)), really?!
Anyway, fun problem! I like problems like this where I have to use a combination of empirical investigation and formal thinking to get it. Also kudos to Binary Agenda for their elegant solution.
BTW the exact solution for 10 is 1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 + 1/7 + 1/8 + 1/9 + 1/10 = 7381/2520 = 2.928 968253 968253 ...
No, it’s 4.2.
The expected number of jumps to cross a river of width n is the nth harmonic number, the partial sum of the first n terms of the harmonic series, 1 + 1/2 + 1/3 + ...
The way I think about it goes like this:
Let J(n) be the expected number of jumps to travel a distance n.
1/nth of the time the frog jumps 1 pad and the average number of additional jumps to reach the bank is J(n-1). The remaining (n-1)/nths of the time, the first pad is effectively skipped, so the total number of jumps needed is J(n-1).
This gives J(n)= 1/n (1+J(n-1)) + (n-1)/n J(n-1), which simplifies to J(n) = J(n-1) + 1/n.
As J(1) = 1, this gives the harmonic numbers.
For the 10-wide river, the expected value is 7381/2520 = 2.928968254
This came to me (and I assured myself it was correct) through realising that all the possible ways for the frog to cross the river amounts to finding an ordered sequence of positive integers summing to n, i.e. the compositions of n ( en.wikipedia.org/wiki/Composition_(combinatorics) ), and finding a bijection between the compositions of n and the n-1 digit binary numbers - let the digits represent the lilypads and a 1 represent that pad being jumped on, so 0000 corresponds to jumping straight across a river of width 5, while 1111 corresponds to crossing the same river jumping on every pad. This gives a way to order all the possibilities that I found quite helpful.
Yep, OESIS A001008 divided by OESIS A002805.
it's a matter of subsets indeed
But if the frog jumps half then a third then a forth, etc, then he will never actually reach the other side.
@@stephenbenner4353 I'm not saying that the frog crosses in the those steps, but that the expected numbers of jumps are the partial sums of the harmonic series, and as the frog can only take positive integer jumps, it will cross a river of width n in a minimum of 1 jump and a maximum of n jumps.
Additionally, the harmonic series diverges - if you keep adding terms, the partial sums will increase without bound:
The terms between 1/2^(n-1) and 1/2^n are all >= 1/2^n and there are 2^(n-1) of them, so their sum is at least 2^(n-1)*1/2^n=1/2. The sum of the harmonic series is thus greater than the sum of an infinite number of 1/2's, which is self-evidently a divergent series, and so the harmonic series is itself divergent.
Sam Middleton I was assuming the frog’s name was Achilles, but then there wasn’t a tortoise in the equation. Your working out reminded me of Zeno’s paradox, but of course we know that Zeno’s paradox is false.
My guess is 3
Just feels like 3, of course, that being rounded to the nearest whole number
I was thinking the exact same thing
I started with 3, but that seems to high, so I'm going with e. Just intuition.
@@matthewjohnson3610 I ran 1 billion rounds and got a stable 2.9289
@@skylark.kraken I calculated it and you are right. It's 2.928968254
Based On The Results In The Video I'd Probably Put It Around 2.5-2.75, 2 And 3 Seemed The Most Common Results.
You: Jumping hurdles
I, an intellectual: *_AUTOFROG ENABLED_*
I want an AUTOFROG ENABLED bumper sticker
Guess: log base 2 of 10
Because on average, it’ll go to 5, then 7.5, then 8.75, etc
It can’t be an irrational number. There is a finite number of ways it can get to the end and when you calculate the expected value you’re going to be adding up number of jumps with their associated probabilities. All the probabilities are rational because there is a finite number of ways of getting to the end (a little hand wavey but you get the idea)
If you average out your first two jumps there you get an average jump distance of 3.75. Goal would be achieved or exceeded in 3 jumps. The problem with this answer is assuming that the second jump has a max value of 5 and not 10. If it is 10 the answer would be a 2 jump average.
Im going with 3 since it makes my brain happier.
With some tedious calculations by hand an interesting pattern emerges:
The fraction can be expressed as the unsigned stirling numbers of the first kind (A000254) of n divided by n!
1/1 (or 1/1!)
3/2 (or 3/2!)
11/6 (or 11/3!)
25/12 (or 50/4!)
137/60 (or 274/5!)
49/20 (or 1764/6!)
363/140 (or 13068/7!)
This function is given as a(n)=n*a(n-1)+(n-1)!
so the function we are after can be written as c(n)=a(n)/n!
as a bonus here is a small c program to compute it:
float c(int n){
return (float)a(n)/factorial(n);
}
int a(int n){
if(n==0) return 0;
return n*a(n-1) + factorial(n-1);
}
int factorial(int n){
int r = 1;
for(int i=1;i
This isn't too hard to prove with generating functions: Let P(n, t) is the g.f. for the probability that it takes k steps. If P'(n, t) is the same restricted to the case where the first jump is 1 then P'(n, t) = (t/n)(P(n-1, t) and if P''(n, t) is the same restricted to the case where the first jump is >1 then P''(n, t) = ((n-1)/n)(P(n-1, t). Add these to get the recursive formula P(n, t) = (t+n-1)P(n-1, t)/n. An easy induction then gives P(n, t) = (t/1)((t+1)/2)((t+2)/3)...((t+n-1)/n). The numerator is the g.f for the Sterling numbers and the denominator is n! You can get the expected value as a partial sum of the harmonic series (found by numerous other commenters) using logarithmic differentiation on the g.f. I like the way the problem is presented; no solution or even hints but a look at how people actually tackle something like this. Lot's of arcane diagrams and formulas, dead ends and mistakes being scribbled out, and the feeling of accomplishment when all that results in an answer, that's where the fun is, not the dry exposition you get in classrooms and textbooks.
I also discovered this same expression, using A000254.
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.
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!
Summing the averages going to the next landing location from each position, in turn, should add up to the total average?
1/10 + 1/9 + 1/8 + 1/7 + 1/6 + 1/5 + 1/4 + 1/3 + 1/2 + 1
That's what I was going to say. You beat me to it.
The answer is: integral from 0 to 1 of (x^10-1)/(x-1) = 7381/2520
That's spot on with the number I get when building it up recursively. Nice one. How did you get this result?
@@jimmythewig3354 I worked it out from the harmonic series posted by others: 1/1+1/2+1/3+...1/10. One way to get that division is through integration of a power of x: I knew that the integral of x^n is x^(n+1)/(n+1). So I thought perhaps the series can be evaluated as x^1/1+x^2/2+x^3/3...+x^10/10 with x set to 1. Working backwards, that expression is the integral of x^0+x^1+...+x^9. Setting the limits to 0 and 1 gives the right value since the first polynomial evaluates to zero when x=0. Playing around a bit allows this second polynomial to be simplified by multiplying by (x-1) giving x^10-1 since all the powers in between cancel. [It's useful to set x=10 to see how this works: (10^10-1)/(10-1) = 9999999999/9 = 1111111111 = 10^9+10^8+...+10^0] So that means the second polynomial is (x^10-1)/(x-1).
@@GeekyNeil I think this vid overhyped the problem. I think of it as at x away from destination, there's a 1/x chance of spending 1 turn to go to position x-1, and a (x-1)/x chance of spending 0.
Solution before watching video.
For length of path L, the expected amount of jumps will be sum (1,L){1/L}.
for example, a length of 10 has an expected jump amount of 1+1/2+1/3+1/4...+1/9+1/10, = 2.929...
Just Thomas : Great answer, I found 2,9289630180776 through analyzing all possible 512 jump sequences, their respective chances and multiplying. Its really close to your answer (2,928968254) - I wonder what causes the difference...
@@mauritswinters866 When i analyzed the 512 possibilities, I came up with 2.92896825396826
Using L in both places seems confusing. I think you mean sum n (1, L) { 1/n }
My code is giving me 2.9... consistently at 10,000 iterations. The second decimal digit is a 2 most of the time at 100,000, but sometimes it is 3.
congrats youre basically right
exactly the same for me, 2.92 with the second decimal being 2 most of the times
Thank you.
I'm getting similar results at 1million iterations. 2.930, 2.929 so I think my code is working, strange feeling.
Its much easier to just actually simulate it. I will try doing it with rationals instead of doubles next.
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)
Well, if we think of it like rolling a d(remaining spaces) we get 5.5 average movement at first, then 5.5/2=2.75 for a total of 8.25 then 2.75/2=1.375 totals 9.625 + 1.375/2=10.3125 which averages something like 4 jumps (between 3 and 4- which is what I would expect since it's probably close to log base 2 of N where N is total pads and they can jump to any pad)
So, Log base 2 of 10 is about 3.32 which is ~ 3 1/3 which seems about right- while 10 seems to be roughly halfway between 9.625 and 10.3125 on a log base 2 scale you'd have 1/3 being the halfway point...
between 3 and 4 is also the most intuitive answer, well done.
If the frog is capable of jumping 10, and it is on space five, do we limit it's capability to 5 spaces or do we allow it to overjump? So for example, if it's on space 5 does it have 1/5 chance (1, 2, 3 ,4, *5*) of getting to the end on its next jump, or does it have 6/10? (1, 2, 3, 4, *5*, *6*, *7*, *8*, *9*, *10*)
@@billweasley1382 1/5
2:58
Intuitive answer would be:
Frog jumps would average out at somewhere in the middle in terms of distance for each jump, so it would be a progression of halving the remaining distance each time until you hit a value that is lower than one. About four jumps?
Dunno, show me the solution!
El Kudos that was my immediate first thought too, like a binary search, log base 2(n)
Actually it corresponds to H_n, so It is approximately ln(n)
Solution is around 2.928968. Not sure if it goes on forever, this is just as far as C++ double precision goes.
@@cameron7374 got the same answer
@@cameron7374 Windows Calculator (1/10 + 1/9 + ...) goes to = 2.9289682539682539682539682539683
For a general way to solve this kind of problem in a quick and dirty way : this is a markov chain with an exit condition on reaching the end, build the corresponding transition matrix, calculate the probabilities of getting to the end after exactly n iterations by computing the transition matrix powers, compute the expectation.
For an exact solution in python use the fraction module, for the stated problem you get 7381/2520 (computable because the transition matrix is nilpotent).
thanks for this!
I solved the riddle in several minutes. First I discovered the recurrence relation that you showed in the video, and then I started to calculate for 1, 2 and 3 and saw I got 1, 1½ and 1⅚, which are the first harmonic numbers - the partial sums of the harmonic series. Then I started to check if it's generally true - I plugged the harmonic numbers to the recurrence relation and saw if I indeed get a harmonic number:
1 + 1/n ΣHm = 1 + 1/n ΣΣ1/k = 1 + 1/n Σ(n-k)/k = 1 + 1/n Σ(n/k - 1) = 1 - (n - 1)/n + Σ1/k = 1/n + H(n - 1) = Hn
I'm sorry I don't have limits for my sums, but I didn't know how to insert them nicely.
The first equality is from the definition of the harmonic numbers.
The second is from counting how many times each unit fraction appears in the sum.
The fourth and the fifth are like that because the sum is from one to n-1.
So then the solution for 10 is H10, which is 7381⁄2520, or approximately 2.93.
what does .93 of a jump look like again?
I tried it in python and got 2.93 with simulations.
from random import randint
from statistics import mean
def frogsteps(step_number):
step_count = 0
all_steps = []
while step_number != 0:
all_steps.append(step_number)
step_number = randint(0,step_number-1)
step_count += 1
return step_count
tried = []
for i in range(100000):
tried.append(frogsteps(10))
print(mean(tried))
@@LuigiBrotha I took your code and modified it to crunch the numbers for more jumps. It's currently melting my tablet but here are some results:
for 0, the mean is 0
for 1, the mean is 1
for 2, the mean is 1.500251
for 3, the mean is 1.832828
for 4, the mean is 2.082564
for 5, the mean is 2.283227
for 6, the mean is 2.448204
for 7, the mean is 2.591892
for 8, the mean is 2.716641
for 9, the mean is 2.830429
for 10, the mean is 2.927934
for 11, the mean is 3.021966
for 12, the mean is 3.102178
for 13, the mean is 3.179268
for 14, the mean is 3.249788
for 15, the mean is 3.319182
for 16, the mean is 3.38179
for 17, the mean is 3.43938
for 18, the mean is 3.494447
for 19, the mean is 3.55039
for 20, the mean is 3.595437
for 21, the mean is 3.645943
for 22, the mean is 3.692473
for 23, the mean is 3.73674
for 24, the mean is 3.776979
for 25, the mean is 3.817263
for 26, the mean is 3.85587
for 27, the mean is 3.888344
for 28, the mean is 3.927704
for 29, the mean is 3.960723
for 30, the mean is 3.997292
for 31, the mean is 4.027499
for 32, the mean is 4.05669
for 33, the mean is 4.089136
for 34, the mean is 4.11915
for 35, the mean is 4.146011
for 36, the mean is 4.173906
for 37, the mean is 4.204187
for 38, the mean is 4.22523
for 39, the mean is 4.254671
for 40, the mean is 4.280237
for 41, the mean is 4.302223
for 42, the mean is 4.326161
for 43, the mean is 4.34952
for 44, the mean is 4.37019
for 45, the mean is 4.396291
for 46, the mean is 4.414632
for 47, the mean is 4.436148
for 48, the mean is 4.458545
for 49, the mean is 4.482059
for 50, the mean is 4.50089
I want to know how you wrote math fractions and symbols in a youtube comment
I used a forward trellis, and applying forward probability found P(X=x) where X = number of steps to reach the end. Consequently I got E(X) = 2.929
@Phinehas Priest Can you elaborate?
@@cd265 ignore it, you are correct.
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...
Ben Gillot sounds like penn Gillette in disguise
Even Penn Gillette doesn't believe in magic so every problem does have solution.
It's Penn Jilette
Thanks. I knew something was wrong and I couldn't figure it out so I guessed
I'm glad I'm not the only one who immediately jumped to that.
Penn Gillette, the best a man can get
I think you can work it out by starting from the end.
E10 = 0
E9 = 1
E8 = 1 + 1/2*E9
E7 = 1 + 1/3*E9 + 1/3*E8
E6 = 1 + 1/4*E9 + 1/4*E8 + 1/4*E7
and so on all the way to E0 which is the starting position and crunch the numbers.
For 10 jumps this gives about 2.929
geryon oh goodness that’s clever.
geryon This is the method I used as well.
My simulation on Python gives me that result!
With more than hundred milion iters it gives approximatly a value of 2.928ecc..
geryon obv i did a very simple program for Python so it approach that result veeeeeery slowly
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
Since there are 10 spaces, my first intuition is to get the average outcome of rolling a 10-sided dice, giving me a 5.5 which I'll round to 6. I'll be left with 4 more spaces where I'll repeat again, giving me 2.5. I'll round to 3, now I left 1 space. So, my guess is 3 jumps.
Why round during your calculations giving a less precise answer. There is nothing stopping you from having a theoretical four-and-a-half sided die with an average of 2.75, unless you want to verify it with real life experiments :)
When you add an Nth space at the front of the queue, it has a 1/N chance of adding 1 to the number of hops taken. So this is the harmonic series.
Genius. The frog has n spot in front of it. That means it has a 1/n chance of jumping to spot n and an (n-1)/n chance of not. In the former case, the expected jumps is 1+a_n because it gets to the nth spot having already done one jump. In the latter case, the expected number of jumps would be a_n because the situation is identical to one in which the frog started at the nth spot. Thus a_(n+1) = 1/n * (1+a_n) + (n-1)/n * a_n = (1 + a_n + n*a_n - a_n)/n = a_n + 1/n.
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.
Oh man. With the end of that simulator, I really hope that the answer for 10 just ends up being Pi for some crazy reason.
My guess is that it would be root 10
My bold claim is that the average number of jumps needed is Pi for any number of water lilies.
Pi does seem to love to pop in on random fields of maths every once in a while, so I'm going to second this.
I was about to say that! hope it is pi!
The number of jumps would be an integer, there's nothing like a 0.1415926... leap. So that would finally prove that pi is exactly 3. 🤐
The result is the harmonic series (H(n)=sum[1/i] from i=1 to i=n) and the proof (although it took me a while to come up with it) is quite simple:
I'll prove it by induction. First we define A(n) as the expected number of jumps if the frog starts in the nth spot with its target being spot 0. We calculate one term A(1)=1 (this is evident). Then we assume it true until A(n-1) and prove it for A(n).
We'll calculate A(n)=(1/n)*p1+((n-1)/n)*p2 where p1 is the expected number of jumps given it lands on the adjacent spot and p2 the expected number of jumps if it doesn't (both including the initial jump).
The frog has a 1/n chance to move only 1 spot which would give it (if it did) an expected number of jumps of 1+A(n-1) (once it's in the n-1 spot it will continue as if it started there no matter where it actually started). So p1=1+A(n-1).
If it jumps to any other spot (with a chance of (n-1)/n)) since they are all equiprobable the result will be the same as if it had started in the n-1 spot (given it doesn't land in the n-1 spot the chance of it landing in any other specific spot is given by Bayes' formula 1*(1/n)/((n-1)/n)=1/(n-1) which is obviously the same probability as if it had started in the n-1 spot. Giving us the second term A(n-1).
Now we add both terms A(n)=(1/n)*(1+A(n-1))+((n-1)/n)*A(n-1)=(1/n)+A(n-1). Since we are proving it by induction we assumed that A(n-1)=H(n-1) and we've proven A(n)=(1/n)+A(n-1)=(1/n)+H(n-1)=H(n). And since we proved A(1)=H(1) we've now also proved that A(n)=H(n) for all n whole number greater or equal to 1.
In case someone wants a more algebraic proof here's one starting from the recurrence relation (which is easy enough to deduce) that Matt shows around 4:18 (in very small steps, same definition of A(n) as before).
A(n)=1+(1/n)*(sum[i=1 to i=n-1] A(i))=
=1+ A(n-1)/n+ (1/n)*(sum[i=1 to i=n-2] A(i))=
=1+ A(n-1)/n+ ((n-1)/n)* (1/(n-1))*(sum[i=1 to i=n-2] A(i))=
=1+ A(n-1)/n+ ((n-1)/n)* (1-1+1/(n-1))*(sum[i=1 to i=n-2] A(i))=
=1-(n-1/n)+ A(n-1)/n+ ((n-1)/n)* (1+1/(n-1))*(sum[i=1 to i=n-2] A(i))= Here the last term "1+1/(n-1))*(sum[i=1 to i=n-2] A(i))" is the definition via the recurrence formula of A(n-1)
=(1/n)+ A(n-1)/n+ ((n-1)/n)* A(n-1)=
=(1/n)+ A(n-1)*(1/n+(n-1)/n)=
=(1/n)+ A(n-1)
And again since we've proven A(1)=1=H(1) this proves that A(n)=H(n) for all n>1 and n being a whole number.
@@wasfas1977 *Now* I find the comments where wveryone's solved it before me in the same way, ;-) .
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!
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
working out the number ways to get each jump for increasing numbers of lily pads like in the video Pascal's triangle shows up. (for instance 6 lily pads:
1 way to get 1 jump
5 ways to get 2 jumps
10 ways to get 3 jumps
10 ways to get 4 jumps
5 ways to get 5 jumps
1 way to get 6 jumps
since all paths are equally likely, 3 or 4 jumps will pop up the most since there are more ways for that to happen. Each lily pad added drops us one more line in pascal's triangle. Since the highest numbers are always found at the median. The formula would be the median of {1,2,3,4,...,n} for n lily pads. (i forget how to make that into an equation, and I have to go)
David Kennon It’s better start then most.
Doesn't fly. For instance, the chance that the first jump will be the entire distance is 1/n. The chance you will make single steps (n jumps) is (1/n)^n. They are not equally likely. So 1 jump has a 1/6 chance, while 6 jumps has a 1/46656 chance.
Michael Timothy Yes I see that the probability of individual paths is not equal.
@@Brooke-rw8rc you right, you right! I corrected myself in another comment, but didn't edit this one. below is my other comment
@@dominiquefortin5345 you right, you right! I corrected myself in another comment, but didn't edit this one. below is my other comment
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
Auto frog mode enabled.
Don't know why I found this so funny
Autofrogs fight the evil forces of the Deceptitoads.
@@RFC3514 Lol, just waiting for the live action
This was a fun problem! My initial guess was 3, then using theory I came up with a very unforgiving formula for the probability of crossing in n-many hops which relied on nested summations. So then I used a computer to compute the expected number of hops to be about 2.928968. And then, I ran many simulations on my laptop and found the average number of hops to match the expected value I got. As for generalizing, I found that the expected number of hops grows logarithmically and will be about 0.63 + ln(n+1) for n lily pads!
I used almost exactly the same approach! I thought the logarithmic-like function was just some logarithm in some base, or log plus something or times some constant, but then I saw a comment mentioning the harmonic series... And it all made sense
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
My Guess: 2.92896825396825 jumps on average for ten landing places
My coworker Josh had that exact answer to 10 decimals places.
Yeah I got 2.92842592843 approximately
It's exactly 2.928968253, with the last 6 digits repeating.
2.9289682539682533 is the output my python script gave me.
I got 98.5, is this correct?
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)
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)))
First gut estimate: The expected value for each jump is half the remaining distance. The discrete lily pads prevents Zeno's paradox, so I expect a value near log_2(n).
Second shot:
For 0 pads it jumps to the other side, for a value of 1.
For one lily pad, it either jumps all the way, or jumps to the pad. (0+1)/2+1=3/2.
For two pads, it has an average of (0+1+3/2)/3+1=11/6.
For three pads, it has an average of (0+1+3/2+11/6)/4+1=25/12
For n pads, it has an average of sum( ave(i
I think you're right; I wrote a bit of code and after a million loops the average came out to be 3.0195806, remarkably close to your 83711/27720 (= 3.0198773)
LONG GUESS:
If we start with one lilly pad between the start and tge finish we can say that P(finishing) = 0.5. And P(landing on the pad)=0.5.
This means that the expected number of steps is (1+2)/2 = 1.5 steps.
This will always be the expected number of steps when the frog lands one away from the finish.
Now lets assume there are two lilly pads between the start and the finish.
P(finishing) = 0.3...
P(landing one away) =0.3...
P(landing two away) =0.3...
Therefore the expected number of steps is (1+2+(1+1.5))/3=1.83...
Now if there were three lilly pads between the start and the finish we have
Average steps = (1+2+1.5+1+1.5+1+1.83...)/4=2.083...
Now if there were four lillys
Avg steps = (1+2+1+1.5+1+1.83...+1+2.083...)/5=2.283...
Now if there were five lillys
Avg steps = (1+2+1+1.5+1+1.83...+1+2.083...+1+2.283...)/6= 2.45
Now if there were six lillys
Avg steps =(1+2+1+1.5+1+1.83...+1+2.083...+1+2.283...+1+2.45)/7=2.5928...
Now if there were seven lillys
Avg steps = (1+2+1+1.5+1+1.83...+1+2.083...+1+2.283...+1+2.45+1+2.5928...)/8=2.717......
Now if there were eight lillys
Avg steps=(1+2+1+1.5+1+1.83...+1+2.083...+1+2.283...+1+2.45+1+2.5928...+1+2.717...)/9=2.828...
FINALLY if there are 9 lillys between the start and finish
Avg steps=(1+2+1+1.5+1+1.83...+1+2.083...+1+2.283...+1+2.45+1+2.5928...+1+2.717...+1+2.828)/10=2.928...
Or in conplete form
7381/2520
Is this right?
@@Dziaji woohoo
I got the same solution :D
@@DarA-ud4qm nice!
Isn't this what they call a recursive relation?
@@louisheyyyy It is. Still the result is correct, even if it doesn't answer the question of the problem.
E(n) is the expected number of jumps, n is the number of potential banks. n = 2 being the minimum then. So E(n) = 1/(n-1) * Sigma{(lowerbound 1, upperbound n-1) n }. Sorry I couldn't get the right notations in with youtubes comment editor. So for 10 banks, it would be 5, and for 11, 5.5. This comes down to E(n) = 0.5*(n-1) + 0.5
E(1)=1 because the frog only has the choice of jumping to the end.
{E(n)= E(n-1) + 1/n} because if we put the extra lilypad right in front of the frog then the frog has a (n-1)/n chance of ignoring the lilypad that leads to an expected amount of jumps that is E(n-1) and a 1/n chance of going in that exact lilypad with an expacted amount of jups of 1+ E(n-1). With a bit of probability you can easily work out the formula between the parenthesis and you can show by induction that E(n)=1+1/2+1/3+...+1/n
It is simple and feels right and I also checked for 3 Lily pads, it's 11/6 =[1+½+⅓] so yeah, should be correct.
@@punya1621 idk if there's a nice closed form
There is, if you use Markov chains and calculate the n-step transition matrices (I've written a much longer comment with the math and a link to a spreadsheet showing the solution)
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.
I have to go with the partial sum of the harmonic series as well.
I convinced myself by "building" the matrix of jumps.
You can easily solve the 3 steps case by hand.
I did it by constructing the 4 (=2^(steps-1)) x 2 (=number of steps-1, last step is always on the other side of the river). This is a boolean matrix, place a true if the frog lands there.
Call it M_3. Count the jumps in each row (=number of true +1), you get the vector j_3.
Compute each probability, place it in p_3. The expected value is the dot product of the j_3 and p_3.
If you want to do the case 4 (=n), here is a way:
Build the M_4 matrix (8×3). Fill the first column half with 'false' (=the frog did not stop on first stone) and half with true. Fill the remaining top half with M_3. Do the same with the bottom half.
Convince yourself that you actually covered all possible cases.
By doing so, the j_4 vector is essentially j_3 on top and j_3+1 on the bottom. The probabilities vector for the bottom part is as follow: the frog jumps on the 1st pad (1/4 of the time) and then has to solve the previous '3 step problem' (so it is 1/4 of P_3), while the top part is again P_3 but scaled with (1-1/4), because when it is not landing on the 1st stone (3/4 of the times) it is actually solving a '3 step problem'.
So when you do the dot multiplication to get the probability, the top half will be 3/4×E(3), while the second will be (E(3)+1)/4.
Rearrange and you get E(4) = E(3) +1/4.
Do the general case in the same way, and you get that E(N+1)=E(N)+1/(N+1).
Solve for base case 1: E(1)=1.
Realize it is the partial sum of the harmonic series.
I also tried a less recursive approach: while a pattern clearly exists and it is extremely clear and interesting, I was not able to prove it for the general case.
We shoul ask Leo Moracchioli, he ownsstudios researching this phenomenon
That is the worst joke e... have my upvote
That took me way too long to work out
My guess is 5.5 (or in this case 5 and 6 jumps have the same probability of happening). I started drawing out the jumps and for any number of Lilly pads and started to notice the pascal triangle showing up as well, and after a few "simulations" on paper, I came up with the non recursive formula. f(n) = (n+1)/2 where the n is the number of jumps
For the formula, I've got to it by summing all the jumps of every possible combination (using the Pascal triangle) and dividing by the numbers of tries (given by the triangle as well). This gave me a mean jump estimate, and after a few tries with different lillypad configurations, it always got me to the same solution as given by the formula
I also got 5.5, but I solved it as an expected value problem: I found the probabilities p(x) of each number of jumps x (by brute force counting) and summed the products x*p(x) for x=1,...,10.
I made the same mistake: I took every possible combination, calculated number of jumps for each, summed them together and divided by total number of combinations. But this would be right only if probability of every combination is the same, which isn't!! It can be easily seen fo the n=3. There are 4 possible combinations: 3, 2+1, 1+2, 1+1+1. There are 2 cases that start with 1, so the probability of jumping to first leaf is 1/2 and probability of jumping to second and third is 1/4. But the task says the probability of jumping to any leaf is the same, 1/3 for n=3.
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
Wrote a simulator for this. For n=10, avg is ~2.9. For n = 1000, avg is 7.4 For n=1000000, avg is 14.3. Looks logarithmic to me.
It's the sum of the harmonic series!
Proof: Say there are n lilypads total. After the first jump, the frog must be in one of the following scenarios:
A: It is on the very first lilypad. (With probability 1/n)
B: It is on one of the other lilypads. (With probability (n-1)/n)
The first case reduces to the case for n-1 lilypads, but plus a jump. So we can say that E(A) = 1+E(n-1)
The second case, if you think about it, is the same as if the frog had been in an n-1 lilypads situation, but had already taken a jump. We then get E(B) = E(n-1).
E(n) = E(A)/n+ E(B)*(n-1/n) = 1/n + E(n-1).
And E(1) is trivially 1.
Unfortunately, there are no close-formed solutions to the sum of the harmonic series, so the original question can't be solved as intended. Do have an explicit value for E(10), though! which is 2.92896825396825.
MsErfwe same result with my simulation on Python that explore every possible combination of the jumps of the frog! I think is correct!
Actually 3.019877. Since you start off with 11 possible positions to jump (10 lily pads and the opposite shore), you would need to look at the eleventh harmonic number instead of the tenth.
For demonstration, with zero lily pads, the crossing will always be a single jump (the first harmonic number) and for one lily pad it will average 1.5 jumps (the second harmonic number).
@@MWSin1 No, the video is asking for the answer for 10 positions. That's 9 lilypads + the opposite shore.
@@OrchidAlloy You're right. I somehow misunderstood the way the question was presented.
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 :)
These random capital letters are driving me insane
I don't think the physical condition of the frog has anything to do with Psychology.
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.
I would guess for 10 spots, it would be 4 jumps. If the frog is equally likely to hop on any spot in front of it, that can be averaged out to hopping 5 spots forward, which is half way. Then it would jump half as many spots (rounded up) again, so it hops 3 spots. There are only 2 spots left, so it hops half as many spots to the last pad, then it hops again to the bank.
So yea, I would guess 4 jumps on average.
WaywardBrigand my thoughts exactly
The average works out to ln(n) + 0.5772156649 where n = the number of pads. approximately. It's the harmonic number series and there is no exact formula.
Your heuristic was not terrible, but a little bit off.
The main reason you are a bit off is that your average jump is the median of zero and the max jump when one is the smallest available jump. So the first jump average is 5.5 not 5. When there are two options it’s 1.5 not 1.
Those are good points
* Spoiler for the solution possibly *
After going through way more paper than I thought I would need, I've come to the solution that this is just a partial sum of the harmonic numbers? I went about solving it the same way you'd solve the coupon collector's problem in that it involved the expected value of a geometric series. I might be missing something obvious and I'm completely wrong, but my answer for a river of 10 jumps is 2.928968, and for a river of k jumps I got the sum of (1/i) for i from 1 to k, or (1/1)+(1/2)+(1/3)+...+(1/k)
CGP Grey, Minutephysics, and Standupmaths are all uploading yeet
I think it will be log base two(n), where n is the number of lilypads in the river. Every time it jumps, on average, it halves the distance to the pond.
The expected value will be a decimal, so no need for ceiling. It gives you 3.3 for n=10, which is pretty reasonable.
@@karlmuster263 Yeah, you're right. I knew as soon as I had posted, but I forgot how to edit on mobile.
I initially paused the video and did what Matt did: write a program to simulate the frog loads and loads of times (although I wrote mine in Chipmunk BASIC and not Python). Over 100000 attempts, I got an average of about 2.93. Then my wife made me got to bed so I lay in bed trying to work it out in my head. I realised it would be easier to start from n=1 and work my way up and see if any pattern emerged. Fortunately, one did. For n=1, the result was obviously 1. For n=2, it was 1 and 1/2 and for n=3, it was 1 and 5/6. So the pattern seemed to indicate that for every increase of n+1, the average number of jumps increased by 1/n. My wife had fallen asleep at this point, so I quietly snuck my phone in under my pillow and opened Excel and typed it in for n=1 to 12 to see if the value for n=10 would match what my earlier program had output and it showed a very satisfying 2.928968 which, of course, pleased me immensely. :-)
My guess is 3.3219. I guessed log base 2 of 10.
aka half an order of magnitufe
log base 2 of width was my first instinct too
I tried log base 2 of n, where n is the number of max leaps, it is fairly close when considering small n, but the result diverges from what I get in computer simulation as the n gets bigger. Somehow I managed to pull something like that: log base 2 of n - (log base 10 of n - 0.5) and this spits results very close to computer simulation (checked up to n = 100000) But I honestly don't know where does this log base 10 of n - 0.5 comes from
@Phinehas Priest I couldn't read all of your comment, but I think we did the same kind of thing. I just tried it on numbers of places to jump until 4 places, and then simplified all of the sums to find that for each space added, another number from the harmonic series was added. This essentially meant the answer for n spaces was just the partial sum of the first n numbers in the harmonic series. I graphed every result possible pretty quickly - desmos.com/calculator/jjfcqzuiv5 - and since we're looking at the harmonic series, there is no known formula to find the sum of the first n values without sigma, so I believe this is the best you can get to.
With problems like these, when it's 10pm and you're too tired to think it through, trying each value of n is just the easiest way to do it, and in this case it was the quickest and easiest way to find the pattern. I don't know if it was luck, but I managed to find this in around 15 minutes.
That is my guess too.
but does the Frog know that it lives in a simulation??
but don't you know that the frog lives in a simulation inside a simulation??
:) everything makes sense now
This is what I initially came up with before I took into account the shifting of probabilities. The frog doesn't choose randomly between all possible paths though, it only chooses randomly from its current options:
Every time you add a Lily pad the frog has two options for each sequence of jumps for one less pad. Either add it as a new jump or combine it with the following jump. The average jumps for N+1 pads equals the average for N jumps plus 1 plus the average for N jumps plus zero (no additional jumps if you combine it with the next jump) all over 2. Rearranging you get twice the average for N pads plus 1 all over two or more simply the average for N pads plus a half. If the frog starts out on the pad before the bank it has one way of getting to the bank and that's in one hop. A(1)=1, A(n+1)=A(N)+1/2, A(N)= (N+1)/2
Working on an actual solution now involving adding up reciprocals of permutations of products times the number of terms in that permutation.
I have a hunch that there's a logarithm in here somewhere, so my guess is for 1+ln(n) jumps.
Just count for 3 or 4 and check the formula
Daan Wilmer you are actually correct (ish) as it does tend to that (almost)
you would be correct
That's a very good approximation in the long run tbh
I think the frog is only allowed to jump to the opposite bank or on the lily pads. Using logs is cheating. :o)
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”.
Thank you for sharing your code and keeping it up years later. It's always helpful.
I got that it is the sum of the harmonic series
I got the same recurrence relation as you did (with the constraint that E(0) = 0) and then I considered E(k+1). I did some manipulations to get this is terms of E(k), so I got E(k+1)=E(k)+1-k/(k+1). By plugging it into itself repeatedly you can get it just in terms of k. My final answer was E(n)=sum from k=1 to n of 1/k
"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.
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.
My guess is log 2(N) using the intuition that on average it will hop half way to the end.
Was in Edinburgh for the first time in my life and got the information about your show afterwards 😭😭 would have been great to see you live as it might have been the only chance
What are you dying?
Dank Squidge Perhaps he lives far from anywhere Matt has toured his show, or maybe he is on the secret Mars missio... oh wait, forget I mentioned that.
I 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.
My guess is 7381/2520 (that is, 1+1/2+1/3+...+1/10)
wait, I think that's actually right, I tested it up to 5 and the pattern holds
Correct! 7381/2520 (1+1/2+1/3+...+1/10) is the answer, which is 2,92896825396825
... according to excel.
seems correct, my simulation approximated 2.92891028 for 10^8 executions
I've got the same answer!
This is correct. I gave a full inductive proof in my comment.
Superb timing at 00:20 :)
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. ua-cam.com/video/pdMZjssrAlk/v-deo.html
Thank you! I take my comedy timing very seriously.
Guess: My answer it's three or 2.9something, but I don't know a lot of math so I just played with simple probability. You start with all the leaves having 10% chance of being chosen, but one of them is going to the other side, then if the frog goes to the last leaf it has a 100% probability of going to the other side in the next jump, as you go down the probability also goes down so for the 8th leaf it has a 50% of either going to the 9th leaf or the other side, then the 7th has 33% and so on. That ends up going to 100% combined or at least really close(I don't know how to explain it) and then you have 3 possibilities of getting 100%, meaning the average is 3 or a little less than 3, I dont know if it makes any sense at all but that's how I thought about it.
My guess is 7381/2520 for 10 pads
I've never dug around the OEIS so much before in my life
Or 1 + 1/2 + 1/3 + ...... 1/(n-1) + 1/n
@@DekarNL I got the 11th element of A000254 over 10 factorial, which reduces to the answer you gave. What OEIS sequence did you end up at?
It is Slightly higher than that.
The expected number of jumps on a river of width n is just the harmonic series up to 1/n. For example if n=3, the expected number of jumps is 1 + 1/2 + 1/3. If n=10 then it's 1 + 1/2 + 1/3 + ... + 1/10, which equals 2.9289...
Agreed. This should be the correct answer. Well done!
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.
Yes, (n + 1) / 2
I solved it using a Markov Chain: I got 2.9289682539682538 for n=10.
Yes my simulation gives that result too! 😍
I don't know what 'Markov Chain' is... but I got the exact same result! :D I just used Kotlin instead. XDXD
@@Verrisin I got the equations from modelling it as a Markov chains, I implemented them in kotlin to solve them, too! A "Markov chain" has basically some states and it can change from the current state to any other state with some probability.
2.92896825396826 verified with a program to simply brute force evaluate all 512 jump patterns.
guess: 2.928968253968
The solution idea is as follows:
first, lets enumerate the possible positions where we can be, but in reverse order, i.e. let the frog start at n and end at 0 (this makes the math slightly easier). Now we can define a function dp: N -> R, such that dp(i) gives us the expected number of jumps to get from position i to the end(position 0).
We know at least the first two values of our function:
dp(0) = 0, as we already are where we want to go, and dp(1) = 1, we can only jump to 0
When we are at a position i>1, there are i possible positions where we can jump to (including 0),
i.e. the probability to jump to any one of them is 1/i. If we now know the expected number of jumps to get from
j (with 0
I made a simulation script in python and this is almost the exact value my code was converging on after 1 million trials (2.92994892994893 was my result) script is below
import random
average_hops = 0
total_hops = 0
num_trials = 1000000
for trial in range(num_trials):
remaining_pads = 10
hops = 0
while remaining_pads > 0:
hop_length = random.randint(1,remaining_pads)
#print(hop_length)
remaining_pads -= hop_length
hops += 1
#print(remaining_pads)
total_hops += hops
average_hops = total_hops/(trial+1)
print(average_hops)
@@stevenking871 harmonic number 10.
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.
SPOILER ALERT: solution + attempt at proof
As some pointed out, it is indeed the harmonic series.
Matt already showed the correct recurrence (It depends on some conventions whether we start with i=0 or i=1):
c_n = 1 + 1/n * sum_(i=1)^(n-1) c_i.
Since
(n - 1) * (c_(n - 1) - 1) = sum_(i=1)^(n-2) c_i,
we have
c_n = 1 + 1/n * sum_(i=1)^(n-1) c_i
= 1 + c_(n - 1) / n + 1/n * sum_(i=0)^(n-2) c_i
= 1 + c_(n - 1) / n + (n - 1) / n * (c_(n - 1) - 1)
= 1/n + c_(n - 1)
= sum_(i=1)^n 1/i.
Or you could look up the harmonic number series ;P
Harmonic number (n) = average jumps
@@zanfur But not all of this ways are equally likely. This holds only for every moment and the NEXT jump.
In your example the frog has three options in the first step. So the propability for only one jump is 1/3 for the way "straight to the end". In contrast if he first hops to lily 1 (with a propability of 1/3), there are still two options for the second step each now with propability 1/2. So the way "lily 1 then skip to end" has only a propability of 1/3*1/2=1/6.
@@Doeniz1 yup you're exactly right.
"We had an amazing time. We were all doing it on the bar. People gathered around and shouted out which angle to concentrate on next. "
This is exactly what I expected Edinburgh would be like.
My simulations seem to suggest E(n) is approximated by Log(n+0.5)+γ , where γ is the Euler-Mascheroni constant. In other words, simply the sum of a finite harmonic series. Code below.
import random
nstart = 1
nend = 200
samplesize = 1000000
def Leap(nsteps):
frog = 0
leaps = 0
while frog < nsteps:
frog = random.randrange(frog+1, nsteps+1)
leaps +=1
return leaps
for n in range(nstart,nend+1):
leaplist =[]
for i in range(samplesize):
leaplist.append(Leap(n))
print(n, sum(leaplist)/len(leaplist))
Fun problem. But what if the frog is climbing a sand dune, such that every time it lands, it slides back one spot?
What would happen at the final spot? Would it slide back in an endless loop or would it end once it reached the final spot?
If you assume that once the frog reaches the final spot, it no longer slides back one space, the formula for the expected number of hops is 1 + sum from k=2 to n (where n is the number of spots on the sand dune) of 1/(k-1). This formula works for values of n > 1. The value for n = 1 is just 1 because the frog cannot slide back once it has reached the end. So, basically, it is just the 1 + the harmonic sum offset by 1.
*Ponders The Question For A Few Moments* "Yeah This Is Pretty Hard, Especially For Someone With Basically No Understanding Of Maths."
I did a bit of figuring and research, and worked backwards a bit: using the fact that the average number of moves went up by 0.5 for every n lily pads, I used that and the number of possible sequences (2^n) to determine that the average number of moves for 10-lily is 6 moves.
I had to consult OEIS to find an equation to get the number of moves by putting in the sequence (1,3,8,20,48,112,256,...) to find a(n) = (n+2) * (2^(n-1)); taking a(n)/2^n gives the average number of moves for n lily pads.
I feel like that's as good of an answer as I'll be able to get. Now I can finally look at the other comments to see what everyone else came up with. I'm kind of proud that I was able to fix my initial notations to realize that 2^n played a part in everything.
I 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