If you allow jumps of length 1, 2, or 3, you end up with the (fittingly named) Tribonacci numbers where each number is the sum of the three previous numbers: 1, 1, 2, 4, 7, 13, 24, 44, 81, 149.
In the limit you get compositions, which are all th ways to break a number. The metallic ratio of compositions is 2, which is what you notice for n-bacci
People heard about "exponential" during the pandemic, but I think very few people learned what it actually means... most people still think that "exponential" is just hyperbole for "a lot".
All those people are the ones who say "but when will I need this in real life?" during maths class. They're also the people who buy houses they can't afford.
@@EvincarOfAutumn Maybe it was true exponential growth, and there are now quadrillions of COVID cases. They just don't want you to know that the MIB spread it around the galaxy.
@@murk1e Chained libraries have actual chains. That is, the books are literally connected to the shelves with chains and rods. This isn't a "chained library." These are just standard book cages used in rare book rooms. And there's no "back in the day." You can see the display case in the back, likely containing exhibits. Assuming this is a reading room in a rare books area at Oxford (where Tom works) there are likely individual books in those cages worth thousands of pounds, even tens of thousands of pounds each. In this case it's not just theft prevention, but likely preventing access to those who may want to randomly browse old and fragile books without permission. It's very common in such areas in libraries also to be required to stow all your personal items in lockers and undergo extensive bag checks to ensure you're not smuggling out leaves torn out of manuscripts or something (which alone can sometimes be worth thousands of pounds, depending on the source). Depending on the level of security, even allowing the markers and classic Numberphile "brown paper" into the room could require special permission.
The frog/lily pad problem leads to a lovely formula for calculating the nth fibonacci number in log(n) time rather than n time. Rather than thinking about the number of trips by landing on the pads near the end, think about landing on the pads in the middle. If n is even, then every path must land on the middle pad or the one before that and the one after it. There are x(n/2) ways to get to the middle pad and x(n/2) ways to get from the middle pad to the nth pad so there are (x(n/2))^2 ways to get to the end landing on the middle pad. If you don't land on the middle pad, you must land on the one before it and the one after it. There are x(n/2-1) ways to land on the pad before the middle, 1 way to get from 1 BM to 1AM and x(n/2-1) ways to get from 1AM to the end. So there are (x(n/2-1))^2 ways to not land on the middle pad. And thus, x(n) = (x(n/2))^2 + (x(n/2-1))^2 ways to get to the end. For example, x(8) = x(4)^2 + x(3)^2 = 5^2 + 3^2 = 34 If n is odd, you can similarly show that x(n) = x((n-1)/2)*x((n+1)/2)+x((n-3)/2)*x((n-1)/2 and using the fact that x((n+1)/2) = x((n-1)/2 + x((n-3)/2), you end up with x(n) = x((n-1)/2)^2 + 2x((n-3)/2)*x((n-1)/2. For example, x(7) = x(3)^2 + 2x(3)x(2) = 3^2 + 2(3)(2) = 21 Then, if you want to, say, evaluate x(100), you need to evaluate x(50) and x(49), which require you to evaluate x(25), x(24) and x(23) (although, you can reduce that to just x(24) and x(23)) which require you to evaluate x(10) and x(11) etc. It takes a total of ~log2(100) steps.
Yours speed-up is counteracted by how the size of the result grows linearly with the input. Unless you assume that all multiplicatrons take the same time regardless of the number of digits involved.
@@SimonClarkstone assuming we're looking for the n-th fibonacci number, we'll get a Theta(n)-bit number. Additions: We'll need Theta(n) additions of which half work with numbers at least half the length of the result. Assuming addition runs in linear time, we get Theta(n^2) runtime. Matrix exponentiation: We'll need Theta(log n) multiplications (matrix size is O(1)). However, the size of the numbers changes rapidly, making the vast majority of time be spent in the last iteration. In the end, the question is how well you can multiply, but with modern tools, fast matrix exponentiation should be faster for large values of n.
This problem is actually the way the fibonacci numbers were first discovered in India, way before it was discovered in Europe. Instead of lilipads ans leaps, musicians were interested in the number of songs of a given length made with short (1) and long (2) beats.
Numberphile actually did a video specifically on the Indian rhythm origin of Fibonacci numbers a little while ago! I knew we were going to get Fibonacci numbers as soon as the setup to this video was described because of the similarity to that video. That previous video is called "The Truth About Fibs," from October 26, 2022
I remember there being a leetcode problem about climbing stairs that was analogous to this problem. My solution was an equivalent form of the sum of binomial coefficients, but then i saw other peoples solutions being fibonacci sequence and was so confused lol.
If you’ve done dynamic programming you’d have the intuition to figure out the condition that constructs that recurrence relationship then from there it’s obvious.
You solution is related to how if sum of the slants of pascals triangle, you get the Fibonacci numbers: summing up the slants in pascals triangle gives exactly the same binomial coefficients as in your solution
Matt Parker did a frog problem a few years ago where the frogs could jump as far as they wanted, and asked about the everage number of hops to the end for n lillypads. I don't remember my solution, but it was great fun to solve.
This video is great but I'm a little dissatisfied about the argument on why the solution must be exponential. Tom draws a tiny curve and says this is exponential, how do you know this is the case and not some crazy polynomial just from the graph? I'm not saying is wrong, obviously this is the answer but it could maybe be argued better, like the fact that that the nth term of the sequence depends on the previous terms which is a feature of exponential growth. In any case, pretty nice video as always
Yes. Exactly my feelings too. I mean it was obvious that it was Fibonacci sequence but very far from obvious it should be exponential. Particularly after first 4 points. "Oh that looks exponential!". What kind of argument is that?? 😅
Yes. That was informal, and actually, not even true. The sequence cannot truly be exponential since three of the terms are colinear. An exponential function and a linear function never intersect at three points. It is only *approximately* exponential (it's asymptotically equivalent to a particular exponential function). As we saw in the final formula, it is actually the sum of two exponential functions. However, it's reasonable that you might notice the shape and think "what if this behaves like an exponential in the limit", and go down a line of reasoning similar to this.
@@kavetovaifyThe argument is that the increase equals the value of the sequence itself. And, as one sees, it's not strictly exponential, but it's the sum of two exponentials (aka geometric series).
To put the argument more clearly: The proof that it is exponential is that the exponential model works. The intuition leading to that proof is 'oh, it looks exponential, let's try that and see if it works' You'd be surprised that this is how a lot of mathematics is first done. A lot of presentation also only give the proof without (or, without adequate) explanation of the intuition or logic leading to the proof. Sometimes, there's follow-up investigations that uncover more meaningful connections, etc. but that's not always guaranteed to have been done.
If you say that the nth term is twice the average of the previous 2 (or in hand wavy terms twice the term that is 1 and a bit earlier) it becomes easier to justify the exponential statement. ... or you could say between twice the (n-2)th term and twice the (n-1)th term. So between 2 to the n/2 and 2 to the n.
My approach was to start with 100 jumps of one, and gradually replaces 2 jumps with a single 2-jump. It's fairly easy to work out the permutations of the replaced jump. Work all the way up to 50 2-jumps, and add them together. I haven't done the actual working out, but the logic feels sound.
If you also solve this problem in a combinatorial way, you can get a different formula for the nth Fibonacci number as a sum of binomial coefficients. x_n = F_(n+1)=sum (n-k choose k) from k=0 to k=floor(n/2).
I get that Xsub0 (the starting case with no lily pads) makes the math clean at 1... But counting "no action" as an option in the word problem means there are Infinity ways to reach the 100th lily pad
The pond-lily-pad-hopping problem is also isomorphic to the more dry-land-table-top problem of how many ways can you place dominoes on a 2xn rectangle. (It gets a little more complicated, I mean interesting, to count domino placements on a 3xn rectangle.)
I don't want to come across as insensitive here, but when I was younger my parents encouraged me heavily to pursue academics and steer clear of people piercings and tattoos. It's always refreshing when I see Tom in one of these videos because I did pursue a doctorate and I'm also covered in tattoos. I love the reality we currently live in is not the reality I was told it would be. "You won't get a job if you get tattoos! People will judge you, nobody will take you seriously!" Now we live in a world ran by the people that were told that and rejected it. It's lovely.
When he started enumerating the simple cases by hand, I had this half-intuition that if you know the number of ways you can travel across N steps, then since those steps will always stay the same even in the case of N + 1, N + 2, etc, it should be relatively easy to calculate how many new steps adding a new tile would give: you don't need to start from scratch every time and brute-force all combinations for all tiles, you can just reuse the previous results (programmers would call this "memoization"). If I'd thought about it a little bit longer, I probably would've made the connection with recursion and thus the Fibonacci series. Too bad my brain is as smooth as a Bernini sculpture. 😔
12:00 - nah, I figured it at the very beginning, when got to x_3, and understood that it is the sum of previous 2, because there are only 2 ways to make last jump. And it clicked immediately that this are Fibonacci numbers.
This is similar to my favorite programming question: The rules are slightly different. The frog's speed always starts at 1 but with each subsequent jump they can increase their speed by 1, decrease their speed by 1, or keep their speed constant. Write a function that takes in an array of booleans representing whether or not there is a Lilly pad at that particular position that returns the fewest number of jumps the frog can cross the river in. Return -1 if it's not possible.
Tried to solve a problem kinda similar to this some time ago. Rules: 1. Random jump-distance 1-6, 2. Fixed distance to target (e.g 100), 3. Some lillypads are missing (you lose if you step on them) - fixed layout (e.g: Lillipad 3,15, 30 are missing). I tried to calculate the chance of winning - ended up simulating it to get a close estimate. Still no clue to this day how to solve this.
Ah, love random computer science examples that occasionally let me spot things instantly. When learning recursion, the specific example of why it could be bad was "You can make a method to get you any number of the Fibonacci sequence in one line of code, but doing so is a really stupid idea." Said line of code was return(method(x-1)+method(x-2));
A fun follow up exercise here would be to solve the recursive function using a Generating Function. The nice thing about that method is you don’t have to guess that the function has exponential growth, the formula at the end eventually just falls out naturally.
If you set the problem up as an adjacency matrix M and solve for the inverse of (I - M), then the first row/last column (depending on the direction you want to go) gives you total number of paths between nodes i and j. In other words, the first row/last column of (I - M)^{-1} will be the Fibonacci sequence.
What a great video! At 6:42 that reminded me of moving up the fretboard of a musical instrument using half steps and whole steps, so I wrote a function to explore that connection and found some pretty interesting stuff: The function: getScales(Total number (of lilypads), Largest Leap Value, Show total # OR Show all solutions spelled out, Keep all duplicates that are the same under rotation or not) I did some exploring of the different cases: getScales(5, 2, 1, 1) shows that example at 6:42 getScales(4, 2, 1, 1) is the example shown at 5:50, but it prints them out in order of smallest hops to largest: [ '1111', '112', '121', '211', '22' ]. If we imagine that the lily pads are not in a line, but rather in a loop, then we can say that 112, 121, and 211 are really all the same family, just rotated around the loop. So for example getScales(4, 2, 1, 0) prints out: [ '1111', '112', '22' ] If you set the maximum leap size to be 2, then the total number of paths the frog can take will be a fibonacci number. If you also remove all the duplicates via rotation, the sequence for the first 12 lilypads (starting from 0) would be: 1, 1, 2, 2, 3, 3, 5, 5, 8, 10, 15, 19, 31 That 31 represents the unique number of musical families of scales that can be made with leaps of either a half step or a whole step. Here's a spreadsheet of them: docs.google.com/spreadsheets/d/1bvIbCPeJdHo92JZThONwRGaIlNGY2LPoCF-2dFC4pe0/edit?usp=sharing If you don't limit the leap value to 2, but set it as the total number of lilypads, and don't remove for duplicates via rotation. EG getScales(6, 6, 0, 1) reads 32 getScales(12, 12, 0, 1) reads 2048 The total number of paths for any number of lilypads will always be a power of two. Here's the sequence for getScales(n, n, 0, 0) for the first 12 n: 1, 1, 2, 3, 5, 7, 13, 19, 35, 59, 107, 187, 351 Where that 351 represents the total number of unique musical families of notes. I made a video about that: ua-cam.com/video/p1DDaqyGtRI/v-deo.html If you want to play with getScales() here it is: let scales = []; // Helper function to check if two scales are cyclic duplicates function areCyclicDuplicates(scale1, scale2) { // If lengths are different, they can't be cyclic duplicates if (scale1.length !== scale2.length) return false; // Concatenate scale1 to itself and check if scale2 is a substring return (scale1 + scale1).includes(scale2); } // Function to generate scales recursively function generateScales(currentScale, totalNotes, largestStep, currentNotes) { if (currentNotes === totalNotes) { scales.push(currentScale); return; } for (let step = 1; step
Hypothesis before watching the rest of the video after the intro: Simple induction. Base case: X1 = 1 (Can only do hop of 1), X2 = 2 (big hop or 2 small hops) Xn = Xn-1 + Xn-2 So, X3 = 2 + 1 = 3 X4 = 3 + 2 = 5 X5 = 5 + 3 = 8 Hey, this pattern's looking familiar, isn't it? It's Fibonacci!
Two questions: given jumps of length 1 or 2 as discussed in the video, and assuming either length jump is equally likely, what is the expected value for the number of jumps? What if the frog can make a jump of any length (from 1 up to and including all the remaining lily pads) randomly chosen such that the probability of any particular length jump is equal. So, at the start, with 100 lily pads, it could jump 1, or 2, or 3, or … 100, each with the likelihood of 1/100. For example, let’s say 50 for the first jump, so now the next jump would be 1, or 2, or … 50, with 1/50 probability. Say the next jump is 21, now 1/39 for the remaining jump, say 13, now 1/16, say 8, now 1/8, say 3, now 1/5, say 4, now 100% chance of jumping 1 to the final lily pad. What is the expected value for the number of jumps?
I haven't watched Numberphile in a while now, it has been a couple of years. My first thought after starting the video was "What happened to James Grime??" 🤣
I was a Math major. I'm a little disturbed, but fascinated, by the way he draws X's, and sticks with parchment. I get it, but it isn't normal. Looks beautiful though! I sometimes make my symbols look artistic!
*Two* really nice moments. Though I didn't get why x98 + x99 = x100. x89 and x99 sound like huge numbers but only 1 jump away from x100, so I never would have thought they _sum_ to x100, instead I would have thought x98 + 1 = x100.
I had the same issue and had to do a bit more reading/thinking on it. Hopefully this will help! Let's simplify this down to the number of ways to get to 5 spaces. There are eight. a)2+2+1 b)2+1+1+1 c)1+2+1+1 d)1+1+2+1 e)1+1+1+1+1 f)2+1+2 g)1+2+2 h)2+1+2 Now let's look at the way to get to 4 spaces: i)2+2 j)2+1+1 k)1+2+1 l)1+1+2 m)1+1+1+1 Finally, let's look at all the ways to get 3 spaces: n)2+1 o)1+2 p)1+1+1 If you notice, all of the examples for getting 5 are actually ALL of the ways to get 3 and all of the ways to get 4 with just one additional step. 1) a = i +1 2) b = j + 1 3) c = k + 1 4) d = l + 1 5) e = m +1 6) f = n + 2 7) g = o +2 8) h = p +2 If you'll notice, 1)-5) are all of the ways you can go to pad 4 with an additional + 1 and 6)-8) are all the ways you can get to pad 3 with an additional + 2. This is what they mean when they say that the only way you can get to the 5th lilypad is to either be at the 3rd lilypad and make a jump of 2 or to be at the 4th lilypad and make a jump of 1. Any way that you could go from pad 3 to pad 5 by first resting at 4 is already encapsulated by all the ways you can get to pad 5 via pad 4---because all of the ways to 4 necessarily include any permutation where the penultimate move is at 3. Trying to include again would be tantamount to double counting. More concisely: The number of routes to X_n is the same as the number of routes to X_{n-2} plus the number of routes to X_{-1}---but the individual unique sequences are necessarily elongated by the addition of a +2 and +1, respectively.
@@erikfinnegan It might be easier to visualize if you go back to x3=x2+x1 x1 is 1 x2 is 1,1 or 2 x3 is 1,2 or 1,1,1 or 2,1 1,2 is just x1 and an extra jump of 2 1,1,1 and 2,1 are both x2 and an extra jump of 1
I actually played with the formula at 10:20 to try to see how it relates to Binet's formula for a closed-form expression, and at first I didn't take into account that x0 = F1, but it fits perfectly except that you get n+1 in Binet's after expanding this. Pretty cool to see it derived!
@@250minecraft You can get it even faster with fast matrix power; basically it involves squaring the matrix repeatedly. At that point, the real bottleneck is dealing with huge numbers.
So, I actually tried to solve this before listening to the whole video, and did come up with a solution. My solution only works for even Fibonacci numbers, but I was still proud of it! You can find the Nth Fibonacci number Fn with the following formula, which is a sum: Fn = sum(0->N/2) of (N-X) nCr X So for instance, the 8th Fibonacci number is… F8 = 8 nCr 0 + 7 nCr 1 + 6 nCr 2 + 5 nCr 3 + 4 nCr 4 = 1 + 7 + 15 + 10 + 1 = 34 (I didn’t know at the time that I was calculating Fibonacci numbers, but it worked out) I reasoned that with an even number of lily pads, you could take 0 double jumps all the way up to N/2 double jumps. If you take 0 double jumps, you have chosen to double jump 0 times across N pads (8 nCr 0). If you perform exactly 1 double jump, you reduce the total number of jumps by 1, and can choose any of those jumps as your 1 double jump (7 nCr 1). If you double jump twice, you again reduce the number of jumps by 1, but now choose two jumps to be your double jumps (6 nCr 2). You continue this process of reducing the number of jumps by one and choosing one extra time until you are only performing double jumps (4 nCr 4). It doesn’t quite work with odd numbers since it requires the number N/2 to be a whole number. Still, it works!
1] For X total pads, you can skip up to floor(X/2) 2] If you are skipping S pads then you are making S 2-jumps and X-2S 1-jumps (a total of X-S). 3] There are (X-S) choose S ways to order the jumps. The above becomes a rather messy "factorials in a sigma" expression, but it's not too horrible to work with. And it will simplify the the same answer as in the video.
(Haven't watched the soln yet) Assume there are S_(n-2) ways of hopping to stone n-2, S_(n-1) ways of hopping to stone n-1. Any path to stone n must land on either stone n-1 or n-2. If it lands on n-1, there is only one way of getting to n, ie just jumping one space, so S_(n-1) paths to stone n hit stone n-1. Alternatively, if the frog lands on n-2. It has two options, jumping to stone n-1 and then stone n, or jumping directly to stone n. However the former is accounted for in the S_(n-1) ways of getting to stone n via n-1, so we count S_(n-2) ways of getting to stone n via n-2 (pv we don't use stone n-1) In total, S_n = S_(n-1) + S_(n-2). Since S_0=1 and S_1=1, we conclude that S_n is the nth Fibonacci number.
The moment he wrote "x_n = " I realized it was induction, so I paused the video to figure it out. Once I found the formula x_n = x_{n-1} + x_{n-2} I knew it was the Fibonacci numbers. After that I just put "101st Fibonacci number" into WolframAlpha and got the answer, but actually solving the recurrence relation with initial values and getting the exponential formula was better! Great video!
So, basically, it is very easy to find an upper bound for this (but it's a pretty big one): Define each jump of length 1 as 0. Define each jump of length 2 as 1. Each possible pattern of jumps is now represented by a unique binary number consisting of 50 to 100 digits, where each digit represents an individual jump. The upper bound is, therefore, 1267650600228229401496703205375 - which comes out as 100 times the digit 1 when expressed as binary. Now of course we know the actual number can't be this high, because if every jump were a jump of length two, then only 50 jumps could happen in total. But it gives us a very quick guesstimate for the kind of dimensions we're working with
I remember doing this exact problem in high school precalc! I ended up writing code to brute force it, but then proved the pattern on the whiteboard, which was such an awesome realization
My approach was: For the first step, the frog can either jump 1 or 2 steps. If it jumps 1 step, it has then all the possibilities for 99 steps left. If it jumps 2 steps, it has all the possibilities for 98 steps left. So x_100 = x_99 + x_98 ... which leads to the same result, just not doing it "backwards" from the end but forwards instead, which I think is simpler and more straightforward...
If you state that the frogcs mate at the other side wants to see the frog do all possible combinations before arriving, you could have an interesting rephrasing that would require determining if the lillypad quantity is even or odd. When the number of lillypads is a multiple of three the frog will finish on the "wrong side" of the pond.
I absolutely LOVE linear recurrence relations. After discrete maths in uni, I'd do them for fun. I recently reminded myself how again. The equations where the weird roots or trig functions cancel out are the coolest. The notation here is different from what I learned, but not too dissimilar. We had car for "constant" and "ratio," I think.
I first encountered this problem years ago in university as a "tiling problem" - you have rectangular tiles of size 1x2, how many ways are there of tiling a strip of floor 2xn long. There was the same extra credit problem - "what if you have 1x3 tiles on a 3xn floor?" only that resulted in the interesting sequence x(n-3)+x(n-1)=x(n). If you have both 1x3 and 1x2 tiles, things get quite complicated, as you can have a block of 6 length that could be either two threes long or three twos long. It was an interesting problem I would recommend Tom look into it.
1:30 before watching further, I want to make a guess, it feels like it could be something to do with binary representation, so I will guess there are somewhere around 2^50 different permutations.
One more step (jump ?). What happens if the frog could jump 1 to J spaces ? What is the relation between J and Lambda ? How exponentially is growing the number of occurrences according to J ?
I stumbled onto all that beautiful mathematics years ago by playing Xenogears for playstation 1. The turn-based attack system utilizes the triangle, square and x buttons in a similar manner to frog leaps. I always thought it was a very unique and clever battle mechanic and I'm glad I took the time to count all the different ways of attacking back then and make all those connections and generalizations.
5:28 when there are 4 lily pads, the 5 different ways the frog can jump are 1111, 22, 112, 211, 121. All of these numbers have the digit sum 4 and are only made of the digits 1 and 2. That means when there are n lily pads, the total number of ways the frog can jump is all the numbers written only using 1 and/or 2 that have the digit sum n. If we try this with n=3, the numbers would be 111, 12, 21. All of them have the digit sum 3 and are dont have any other digit than 1 and 2.
Using the n=0 case as an initial value is pretty dodgy IMO, you could argue that it should be 0 as we're not counting a 0 distance jump anywhere else. Much better to use n=1 and n=2 to fix the constants. Those aren't hard to do, because the defining equation for lambda allows you to reduce lambda squared easily.
But n=0 is the initial value. It's philosophical but there's only one way to do nothing, and that's to do nothing. And anything to the zeroth power is 1 so it makes sense in the equation. And 1, 1 is how the Fibonacci numbers starts off. That's how you get to 2, by adding the two previous numbers, 1 and 1. You could consider n=0 to be 0 but then you aren't doing math at that point with n=0 and you have to carve out arbitrary rules to make n=1 and additional n work mathematically. 0, negative numbers, imaginary numbers, and others, are just an extension of the rules we've discovered for our real world numbers, you have to follow those rules to the end for mathematics to logically work. You can't just argue n=0 equals 0 because it feels right, it has to follow logically.
@@jmhorange There's no inherent reason why allowing no jumps is allowed in the problem more than allowing negative (or fractional) jumps. Even the recurrence relation is only actually defined for n>=3: there is no a priori reason why, eg, x_1= x_-1 + x_0. Everything outside positive integer n is a continuation of the original problem into a previously undefined domain. It is not part of the problem itself, which is why it wasn't part of the exploration earlier in the video and why it's a poor choice to use such a point to solve the original problem.
you're considering the problem to be the size of the jump when the main problem is how many ways to reach the last lilypad. doing nothing with 0 lilypads is still an entry because it's the same as already being at the last one. is it an unsatisfactory answer from a storytelling perspective, sure, but that doesn't change the maths.
The real reason it is valid to say x0=1 is because at that point, we are trying to solve the recurrence relation independent from the frog problem. If we choose to start with x0=1, x1=1 just because we can, then x2=1+1=2 just like in the real problem. From there the sequence continues exactly the same, so solving the problem with the addition of x0=1 doesn't actually change anything. If it was a slightly different problem where x2 was different but the Fibonacci pattern remained, you could "solve" for what value of x0 continues the pattern as x2-x1.
Great Numberphile video, but I'm also interested in the room this was filmed in. That table looks worn down by hundreds of years of use, and what kind of books are behind the cages? It would be an honour to work in a place with so much history.
it's St Edmund Hall Old Library, a college of Oxford University [where Tom is an Outreach Fellow ]... there's a 3d "wikispace" for it with a 360 interactive image so you can pan around. if you search for; _wikispace St Edmund Hall Old Library_ you should find it edit to add: looking at the wikipedia entry for the college, you'll also find the quote "the oldest surviving academic society to house and educate undergraduates in any university" - estimated to have been established by 1236, possibly earlier - so yeah :) quite a history :)
The way it unfolded to me was to write the recursive function for X(n). The function would return 1 if n=0 or n=1, otherwise it would return 1 + X(n-2) [the frog starts with a jump of two, then completes with X(n-2) jumps] plus 1 + X(n-1) [the frog jumps 1 and completes with X(n-1) jumps.
I did this with combinatorics. If you have n Steps of 2, you have 100-2n Steps of 1. So in total 100-2n+n=100-n Numbers to arrange. You can arrange 100-n Numbers (100-n)! times. But 2,1,1' is the same as 2,1',1 and so on. So you have to divide by n! and (100-2n)! to extract this equal combinations. Sum up the Terms from n=0 to n=50 and you have the same awnser.
I know it's not fibonacci number related, but it's about that exponential growth. In my early days of learning a bit more advanced math, the teacher said something like "Let's say you have 3 books and you want to arrange them in every possible combination on your bookshelf. There are 6 different ways to arrange the, Now let's say you have 10 books to arrange in every possible combination, how long would it take you? Let's say it took you a 10 seconds to arrange the books in a new order." It seems almost simple, it's only 10 books, maybe a couple hours. But it would take over a year of continuously rearranging the books. And adding just 1 more book would now take over 12 years. (Yes, it's when I learned about factorial). That's why I love the idea of how many possible combinations can a deck of 52 cards be arranged in. It's such a stupidly large number that most people can't wrap their head around it.
because I'm lazy - I did an approximation: minimum jumps required is 50, maximum 100, so average is about 75 jumps for all permutations. Each jump has is 2 options (Except last jump, but use base 2 anyway) -> 2 ^ 75 ~= 3.77e22 Which is in the same realm of magnitude as 5.73e20 - close enough :D
For me an easier way of looking at this being fibonachi is not going from the end, but going form the start. If there are let's say 5 lilipads (X5), the frog can jump 1 lilipad and still have 4 to go (X4), if it does a big jump, it has 3 lilipads to go (X3). If I know how many ways the frog can jump 4 lilipads (X4) and 3 lilipads (X3), then the sum should be the amount of ways how to jump 5 lilipads (X5).
To avoid making a guess of what the solution is and then afterwards confirming you guess was correct, I'd advise to solve the problem as an eigenvalue problem. This is a robust way of deducing the solution to the equation x_n = x_n-1 + x_n-2.
The "high school" intuition is that when a problem leads to a quadratic equation and the solution is somehow sign constrained, then one root leads to a valid solution and the other is discarded. The idea that the actual solution should be obtained as a linear combination of both roots comes out of the blue.
Do you know why it is that the solution is a linear combination? My thought was the same, that it would be the nonnegative solution of the quadratic solution.
@@veessee I don't know how much you know about linear algebra, so I will answer as if you knew only the absoute basics - vectors and matrices. The math the author is hiding from us is probably a couple weeks' worth of Linear Algebra 101. Just to signal what's involved - if you represent the two initial values in the Fib sequence as the column vector vector [1,1], then iterating the recursion that defines the sequence can be reframed as repeatedly transforming this vector with the matrix [[0,1],[1,1]]. After each step, you will get a vector whose coordinates are two consecutive terms of the Fibonacci sequence. On the other hand, every such transformation/multiplication of a vector by a matrix can be understood as a transformation of the whole plane if you consider how it affects any possible vector [x,y] rather than just [1,1]. When viewed like this, this transformation is geometrically equivalent to simultaneously stretching or compressing the plane along two lines through the origin. This might be difficult to visualise, so let me break it down: - there are two lines through the origin, U and V, that are uniquely derived from the matrix - each of these lines has an associated scaling factor, also derived from the matrix - to "apply the matrix" to point P on the plane, you first take the "coordinates" of that point as if U and V were the axes of the coordinate system; that is, you measure the side lengths of the parallelogram with opposite corners at the origin and P, and sides parallel to U and V - then you apply the associated scaling factors to these coordinates; this gives you the position of the point (still in uv coordinates) after the transformation Now if you iterate this procedure, and look at how the u and v coordinates (measured along the lines U and V as described above) change, you will notice that at each step the u coordinate is multiplied by one scaling factor, and the v coordinate is multiplied by the other scaling factor. This means that the sequences of successive u and v values are two independent geometric sequences. So if the uv coordinates of the initial vector [1,1] are called [u₁, v₁], and the scaling factors are called λᵤ and λᵥ, then after n iterations it's [u₁λᵤⁿ, v₁λᵥⁿ]. You recognize the powers of λ from the video, right? Now, we are interested in the xy coordinates, not in the uv coordinates, so we need to map these uv coordinates back to xy; we are also only really interested in the y coordinate, because the Fibonacci sequence is a sequence of numbers, not points. This is where the linear combination comes into play: when you derive this inverse mapping and take just the y coordinate, what emerges is the linear combination of the scaling factors (named λ₁ and λ₂ in the video) raised to the n-th power. I know I am still skipping over details here, but at least you can take my word that this linear combination emerges as a result of a step-by-step derivation, rather than as a divine revelation that "the solution must be of this particular form". Some actual terminology used in linear algebra: - the directions of the lines U and V are represented as vectors called the *eigenvectors* of the matrix - the scaling factors associated with the eigenvectors are called the *eigenvalues* of the matrix - the polynomial that was set to 0 and solved in the video as the equation to get the eigenvalues is called the *characteristic polynomial* of the matrix
The way that an integer recurrence can be solved with square roots reminds me of one that Matt Parker posted the other day. if rand() is defined as a function that returns a random number from 0 to 1 then the square root of rand() gives the same distribution as the maximum of two rand() functions.
Does 2 ^ (n/2) work? There are 2 ways to get to the second lily pad. Then there are 2 ways to get from lily pad 2 to lily pad 4. So 2x2 possible ways to get to lily pad 4. Then 2 ways to get from lily pad 4 to lily pad 6. So 2x2x2 or 2^(6/2) ways to get to lily pad 6.
So the logical follow up question is: What if you allow any jump length >0? That is actually pretty easy. Using the same method as befor, you end up with X(n)=X(1)+X(2)+...+X(n-1), thus the n-th term is just the sum of all the previous terms, which means it just doubles with every step. So it should be 1, 2, 3, 6, 12, 24, 48, 96....
Fun fact, the solution for the 1, 2 or 3 problem is the tribonacci sequence a(n+2). Explicit formula for the tribonacci function. a(n) = j*C^n + k*r1^n + L*r2^n where C = (1 + (19-3*33^(1/2))^(1/3) + (19+3*33^(1/2))^(1/3))/3 [C is the real root to x^3-x^2-x-1=0] p = ((3*C-5)*(C+1)/4)^(1/2) m = (1-C)/2 r1 = m+p*i [r1 and r2 are the complex roots to x^3-x^2-x-1=0] r2 = m-p*i j = 1/((C-m)^2 + p^2) a = -j/2 b = (C-m)/(2*p*((C-m)^2 + p^2)) k = a+b*i L = a-b*i Philippe LALLOUET, Jun 23 2007
Instead of recursion, I used combinatorics, arriving at: Total number of ways to cross = sum i=0->50 of (100-i)Ci Exactly same answer :) I wonder if there's a way to go about the problem with Markov Chains.
I have to disagree with the 0 case though. "You're already there" is the same as allowing no jumps. Which would add infinitely many ways to cross the lilypads. Why force the first two fibonacci numbers in? Fibonacci himself didn't even use them.
So how many ways do you think there are of doing nothing? (Mathematically, you can get it by working backwards - what do you have to have added to 1 to get 2 - or by treating the Fibonacci numbers as a special case of the gamma function).
There are 3 possible sequences to jump across 3 lily pads: (1,1,1), (1,2), (2,1) There are 2 for jumping across 2 lily pads: (1,1), (2) There is 1 for 1 lily: (1) There is 1 for no lilys: () (0), (0,0,0), (0,0,0,0,...) etc. are not valid, because a jump of distance 0 (jumping in place) was never valid to begin with. The frog is already at the goal when it started the journey, so there is nothing to do, and there is only one way to do literally nothing.
10:00 Same, but a bit more compact: (((1+R)/2)^(n+1) - ((1-R)/2)^n+1)/R with R=sqrt(5). From the binomial expansion it is clear to me that the even powered terms will cancel and from the odd powered, an even power of R remains after finally dividing by R.
I'm kinda proud that I anticipated the fibonacci sequence already at the 6:43 mark :D I liked the frog model to visualize the whole thought experiment :3
While you were talking about x2, I was thinking about x0=1. That set the sequence up to be 1,1,2,3. I believe x4=5. I wonder if the final result will be the Fibonacci sequence. edit: Just seconds later you talk about the conditions to reach lilly-pad number 100, being either a jump of 2 from 98 or of 1 from 99, and now I'm absolutely certain the sequence is simply the Fibonacci sequence.
If it takes 1 second per leap across the pads for a 1 or 2 long jump then how long would it take a frog to jump all possible combinations when n=100? E.g., jumping 2,2,2,2,2,2,2... is 50 seconds (50 jumps) but 1,1,1,1,1,1,... is 100 seconds.
So it would take roughly 100000x longer than universe has existed to try all combinations at a rate of 1 second per leap for 100 lilypads. Oof. Really big numbers indeed.
DYNAMIC PROGRAMMING! This is the classical "Climbing Stairs to reach at the top" Dynamic Programming problem(Computer Science): There are n stairs, a person standing at the bottom wants to climb stairs to reach the nth stair. The person can climb either 1 stair or 2 stairs at a time, the task is to count the number of ways that a person can reach at the top.
This makes me think of a related problem: given a set of coin denominations, how many ways can they add to a given value. Like U.S. has 1, 5, 10, and 25 cent coins. How many ways make a dollar?
This type of question can be solved using generating functions. The answer is the coefficient of x^100 in (1+x+x^2+...)(1+x^5+x^10+...)(1+x^10+x^20+...)(1+x^25+x^50+...).
I've been thinking that there's something interesting noting that all possible Fibonacci-like sequences (those made by summing some finite rolling pattern of the previous terms) is dominated by 2^n by counting two ways: 2^n frog-paths with no restrictions and Fibonacci-like-ly many when restricted to some set of legal jump sizes. You can even see the largest real solution to the sequence of equations "sum(x^n, n=0..N-1) = x^N" approaches 2 as N -> infinity, corresponding to frogs being allowed to take larger and larger jumps and the set of legal paths becomes the set of all paths.
If you allow jumps of length 1, 2, or 3, you end up with the (fittingly named) Tribonacci numbers where each number is the sum of the three previous numbers: 1, 1, 2, 4, 7, 13, 24, 44, 81, 149.
In the limit you get compositions, which are all th ways to break a number. The metallic ratio of compositions is 2, which is what you notice for n-bacci
I'm glad there is a name for the thing I expected to exist.
I knew tribbing somehow had to be part of this.
@@adityakhanna113 n-bacci sounds like a pasta you make with chemistry
And if you allow either jumps to women or jumps to sandwiches, you end up with the Tribbiani numbers.
Amphibionacci? 🐸
Bravo
That's really clever! 😅
*round of applause*
we can also do it with combinatorics but then after it we have to add 100C0 +99C1+98C2+........+50C50
Ribbitnacci.
Interestingly, if you replace the frog with a grasshopper, the answer will be identical regardless of the color of the grasshopper.
Spittin facts
😎😎😎
People heard about "exponential" during the pandemic, but I think very few people learned what it actually means... most people still think that "exponential" is just hyperbole for "a lot".
I've seen too many growth graphs and people say "thats exponetional growth!" and I'm stating "thats quadratic, not even close to exp".
Yes, and it makes me cringe.
All those people are the ones who say "but when will I need this in real life?" during maths class.
They're also the people who buy houses they can't afford.
“Exponential* growth!”
* logistic, but like, the fast part
@@EvincarOfAutumn Maybe it was true exponential growth, and there are now quadrillions of COVID cases. They just don't want you to know that the MIB spread it around the galaxy.
Why are the books in little cages. Does this library not have free range books?
The cages are there for your protection.
The cages are another layer of protection to frog plages.
Serious answer.
It’s a chained library. Back in the day, books were incredibly pricey items - it’s theft prevention.
@@murk1e Nowadays the theft happens when you buy textbooks at the start of the year
@@murk1e Chained libraries have actual chains. That is, the books are literally connected to the shelves with chains and rods. This isn't a "chained library." These are just standard book cages used in rare book rooms. And there's no "back in the day." You can see the display case in the back, likely containing exhibits. Assuming this is a reading room in a rare books area at Oxford (where Tom works) there are likely individual books in those cages worth thousands of pounds, even tens of thousands of pounds each.
In this case it's not just theft prevention, but likely preventing access to those who may want to randomly browse old and fragile books without permission. It's very common in such areas in libraries also to be required to stow all your personal items in lockers and undergo extensive bag checks to ensure you're not smuggling out leaves torn out of manuscripts or something (which alone can sometimes be worth thousands of pounds, depending on the source). Depending on the level of security, even allowing the markers and classic Numberphile "brown paper" into the room could require special permission.
I love these videos. A gentle reminder to myself of just how much there is to learn, and how little I actually know.
I like to believe that Tom lives in that chair, and Brady just visits him from time to time.
can confirm.
The frog/lily pad problem leads to a lovely formula for calculating the nth fibonacci number in log(n) time rather than n time. Rather than thinking about the number of trips by landing on the pads near the end, think about landing on the pads in the middle.
If n is even, then every path must land on the middle pad or the one before that and the one after it. There are x(n/2) ways to get to the middle pad and x(n/2) ways to get from the middle pad to the nth pad so there are (x(n/2))^2 ways to get to the end landing on the middle pad. If you don't land on the middle pad, you must land on the one before it and the one after it. There are x(n/2-1) ways to land on the pad before the middle, 1 way to get from 1 BM to 1AM and x(n/2-1) ways to get from 1AM to the end. So there are (x(n/2-1))^2 ways to not land on the middle pad. And thus, x(n) = (x(n/2))^2 + (x(n/2-1))^2 ways to get to the end. For example, x(8) = x(4)^2 + x(3)^2 = 5^2 + 3^2 = 34
If n is odd, you can similarly show that x(n) = x((n-1)/2)*x((n+1)/2)+x((n-3)/2)*x((n-1)/2 and using the fact that x((n+1)/2) = x((n-1)/2 + x((n-3)/2), you end up with x(n) = x((n-1)/2)^2 + 2x((n-3)/2)*x((n-1)/2. For example, x(7) = x(3)^2 + 2x(3)x(2) = 3^2 + 2(3)(2) = 21
Then, if you want to, say, evaluate x(100), you need to evaluate x(50) and x(49), which require you to evaluate x(25), x(24) and x(23) (although, you can reduce that to just x(24) and x(23)) which require you to evaluate x(10) and x(11) etc. It takes a total of ~log2(100) steps.
That is a neat intuition for the use of fast matrix exponentiation!
Leaving a reply to remind me of this comment :)
Same dropping a comment to work this out on paper sometime 👍🏻
Yours speed-up is counteracted by how the size of the result grows linearly with the input. Unless you assume that all multiplicatrons take the same time regardless of the number of digits involved.
@@SimonClarkstone assuming we're looking for the n-th fibonacci number, we'll get a Theta(n)-bit number.
Additions: We'll need Theta(n) additions of which half work with numbers at least half the length of the result. Assuming addition runs in linear time, we get Theta(n^2) runtime.
Matrix exponentiation: We'll need Theta(log n) multiplications (matrix size is O(1)). However, the size of the numbers changes rapidly, making the vast majority of time be spent in the last iteration.
In the end, the question is how well you can multiply, but with modern tools, fast matrix exponentiation should be faster for large values of n.
This problem is actually the way the fibonacci numbers were first discovered in India, way before it was discovered in Europe. Instead of lilipads ans leaps, musicians were interested in the number of songs of a given length made with short (1) and long (2) beats.
Indians use morse code for their rhythm bwahahaha 🤣
Are you indian?
Numberphile actually did a video specifically on the Indian rhythm origin of Fibonacci numbers a little while ago! I knew we were going to get Fibonacci numbers as soon as the setup to this video was described because of the similarity to that video. That previous video is called "The Truth About Fibs," from October 26, 2022
And then they woke up and shat themselves
Yeah, that’s why some mathematicians call them the Virihanka-Fibonacci numbers, after the person who discovered the pattern in length 1 and 2 beats
Dude is rocking pi, chains, math equations, and two pokeballs on his arms. What a baller.
@TomRocksMaths I'm sure there's a story behind the 3 on your left ring finger, but I don't want to start an argument about thumbs.
I believe he has the navier-stokes equations about fluid dynamics tattoed
And is that the Axii sign from the Witcher too?
@@dfunited1
Isn't that an e for Euler's number?
I, an engineer, don't see the difference between e, pi or 3, so in a sense we're both right.
I remember there being a leetcode problem about climbing stairs that was analogous to this problem. My solution was an equivalent form of the sum of binomial coefficients, but then i saw other peoples solutions being fibonacci sequence and was so confused lol.
I've seen that. I understand the video but i don't know how they were solving it
The sums of the diagonals of Pascal's triangle (binomial coefficients) are the Fibonacci numbers.
If you’ve done dynamic programming you’d have the intuition to figure out the condition that constructs that recurrence relationship then from there it’s obvious.
You solution is related to how if sum of the slants of pascals triangle, you get the Fibonacci numbers: summing up the slants in pascals triangle gives exactly the same binomial coefficients as in your solution
I didn't check the solution, but just printed output of brute force solution. Thankfully, Fibonacci is quite recognizable.
0:03
'An illustration of a frog that's not that bad' merch out NOW!
He gave his drawing a go, so it’s likely a Parker Frog.
Wow, that was a very ribbiting video, I couldn’t take my eyes off it.
i nearly croaked by the end of it
I, for one, feel like they have toad me all of this before 🤷♂️
I was wondering why the frog doesn't just pole volt over to the other side, but then I realized the stick it has is just a tad pole.
Your pun has spawned many imitators. Kermit me to add my own.
Matt Parker did a frog problem a few years ago where the frogs could jump as far as they wanted, and asked about the everage number of hops to the end for n lillypads. I don't remember my solution, but it was great fun to solve.
Indeed it's still my favourite math question
This video is great but I'm a little dissatisfied about the argument on why the solution must be exponential. Tom draws a tiny curve and says this is exponential, how do you know this is the case and not some crazy polynomial just from the graph? I'm not saying is wrong, obviously this is the answer but it could maybe be argued better, like the fact that that the nth term of the sequence depends on the previous terms which is a feature of exponential growth.
In any case, pretty nice video as always
Yes. Exactly my feelings too. I mean it was obvious that it was Fibonacci sequence but very far from obvious it should be exponential. Particularly after first 4 points. "Oh that looks exponential!". What kind of argument is that?? 😅
Yes. That was informal, and actually, not even true. The sequence cannot truly be exponential since three of the terms are colinear. An exponential function and a linear function never intersect at three points. It is only *approximately* exponential (it's asymptotically equivalent to a particular exponential function). As we saw in the final formula, it is actually the sum of two exponential functions.
However, it's reasonable that you might notice the shape and think "what if this behaves like an exponential in the limit", and go down a line of reasoning similar to this.
@@kavetovaifyThe argument is that the increase equals the value of the sequence itself. And, as one sees, it's not strictly exponential, but it's the sum of two exponentials (aka geometric series).
To put the argument more clearly:
The proof that it is exponential is that the exponential model works.
The intuition leading to that proof is 'oh, it looks exponential, let's try that and see if it works'
You'd be surprised that this is how a lot of mathematics is first done. A lot of presentation also only give the proof without (or, without adequate) explanation of the intuition or logic leading to the proof. Sometimes, there's follow-up investigations that uncover more meaningful connections, etc. but that's not always guaranteed to have been done.
If you say that the nth term is twice the average of the previous 2 (or in hand wavy terms twice the term that is 1 and a bit earlier) it becomes easier to justify the exponential statement.
... or you could say between twice the (n-2)th term and twice the (n-1)th term. So between 2 to the n/2 and 2 to the n.
12:40 - For some reason, that little frog sound at the end of the long answer cracked me up. 😅
My approach was to start with 100 jumps of one, and gradually replaces 2 jumps with a single 2-jump. It's fairly easy to work out the permutations of the replaced jump.
Work all the way up to 50 2-jumps, and add them together.
I haven't done the actual working out, but the logic feels sound.
In R you can solve it this way:
# Number of double jumps
a
If you also solve this problem in a combinatorial way, you can get a different formula for the nth Fibonacci number as a sum of binomial coefficients.
x_n = F_(n+1)=sum (n-k choose k) from k=0 to k=floor(n/2).
This combinatorics problem is just awesome!
I get that Xsub0 (the starting case with no lily pads) makes the math clean at 1...
But counting "no action" as an option in the word problem means there are Infinity ways to reach the 100th lily pad
Frogonacci numbers
Ribbitnacci was right there.
🐸
We get to the best pun after hopping around for just a ribbit.
Amphibonacci
No
Meta has practice interview questions for software engineers, and one of them is basically exactly this, right down to the amphibious set dressing
In coding questions there is an alternate version of the exact same problem about walking up a flight of stairs by ones and twos.
The pond-lily-pad-hopping problem is also isomorphic to the more dry-land-table-top problem of how many ways can you place dominoes on a 2xn rectangle. (It gets a little more complicated, I mean interesting, to count domino placements on a 3xn rectangle.)
2:11 I love the showcase of the Parker frog
I don't want to come across as insensitive here, but when I was younger my parents encouraged me heavily to pursue academics and steer clear of people piercings and tattoos. It's always refreshing when I see Tom in one of these videos because I did pursue a doctorate and I'm also covered in tattoos. I love the reality we currently live in is not the reality I was told it would be. "You won't get a job if you get tattoos! People will judge you, nobody will take you seriously!" Now we live in a world ran by the people that were told that and rejected it. It's lovely.
When he started enumerating the simple cases by hand, I had this half-intuition that if you know the number of ways you can travel across N steps, then since those steps will always stay the same even in the case of N + 1, N + 2, etc, it should be relatively easy to calculate how many new steps adding a new tile would give: you don't need to start from scratch every time and brute-force all combinations for all tiles, you can just reuse the previous results (programmers would call this "memoization").
If I'd thought about it a little bit longer, I probably would've made the connection with recursion and thus the Fibonacci series. Too bad my brain is as smooth as a Bernini sculpture. 😔
Anyone worked out the sequence for when the frog can jump 1, 2 or 3 spaces?
The Tribonacci sequence of course
Angzt had posted their comment a day before you asked. :-)
Quote: 1, 1, 2, 4, 7, 13, 24, 44, 81, 149[, ...]
Also, 14:55.
I love the tattoo of one of the most important constants in mathematics on Tom's finger: the number 3.
11:05 I love the frog blithely hopping across the Fibonacci numbers
12:00 - nah, I figured it at the very beginning, when got to x_3, and understood that it is the sum of previous 2, because there are only 2 ways to make last jump. And it clicked immediately that this are Fibonacci numbers.
Same
CS majors having leetcode flashbacks rn
This is similar to my favorite programming question:
The rules are slightly different. The frog's speed always starts at 1 but with each subsequent jump they can increase their speed by 1, decrease their speed by 1, or keep their speed constant.
Write a function that takes in an array of booleans representing whether or not there is a Lilly pad at that particular position that returns the fewest number of jumps the frog can cross the river in. Return -1 if it's not possible.
Tried to solve a problem kinda similar to this some time ago. Rules: 1. Random jump-distance 1-6, 2. Fixed distance to target (e.g 100), 3. Some lillypads are missing (you lose if you step on them) - fixed layout (e.g: Lillipad 3,15, 30 are missing).
I tried to calculate the chance of winning - ended up simulating it to get a close estimate. Still no clue to this day how to solve this.
Ah, love random computer science examples that occasionally let me spot things instantly.
When learning recursion, the specific example of why it could be bad was "You can make a method to get you any number of the Fibonacci sequence in one line of code, but doing so is a really stupid idea."
Said line of code was return(method(x-1)+method(x-2));
A fun follow up exercise here would be to solve the recursive function using a Generating Function. The nice thing about that method is you don’t have to guess that the function has exponential growth, the formula at the end eventually just falls out naturally.
If you set the problem up as an adjacency matrix M and solve for the inverse of (I - M), then the first row/last column (depending on the direction you want to go) gives you total number of paths between nodes i and j. In other words, the first row/last column of (I - M)^{-1} will be the Fibonacci sequence.
What a great video! At 6:42 that reminded me of moving up the fretboard of a musical instrument using half steps and whole steps, so I wrote a function to explore that connection and found some pretty interesting stuff:
The function:
getScales(Total number (of lilypads), Largest Leap Value, Show total # OR Show all solutions spelled out, Keep all duplicates that are the same under rotation or not)
I did some exploring of the different cases:
getScales(5, 2, 1, 1) shows that example at 6:42
getScales(4, 2, 1, 1) is the example shown at 5:50, but it prints them out in order of smallest hops to largest: [ '1111', '112', '121', '211', '22' ].
If we imagine that the lily pads are not in a line, but rather in a loop, then we can say that 112, 121, and 211 are really all the same family, just rotated around the loop. So for example getScales(4, 2, 1, 0) prints out: [ '1111', '112', '22' ]
If you set the maximum leap size to be 2, then the total number of paths the frog can take will be a fibonacci number. If you also remove all the duplicates via rotation, the sequence for the first 12 lilypads (starting from 0) would be:
1, 1, 2, 2, 3, 3, 5, 5, 8, 10, 15, 19, 31
That 31 represents the unique number of musical families of scales that can be made with leaps of either a half step or a whole step.
Here's a spreadsheet of them:
docs.google.com/spreadsheets/d/1bvIbCPeJdHo92JZThONwRGaIlNGY2LPoCF-2dFC4pe0/edit?usp=sharing
If you don't limit the leap value to 2, but set it as the total number of lilypads, and don't remove for duplicates via rotation. EG getScales(6, 6, 0, 1) reads 32
getScales(12, 12, 0, 1) reads 2048
The total number of paths for any number of lilypads will always be a power of two.
Here's the sequence for getScales(n, n, 0, 0) for the first 12 n:
1, 1, 2, 3, 5, 7, 13, 19, 35, 59, 107, 187, 351
Where that 351 represents the total number of unique musical families of notes. I made a video about that:
ua-cam.com/video/p1DDaqyGtRI/v-deo.html
If you want to play with getScales() here it is:
let scales = [];
// Helper function to check if two scales are cyclic duplicates
function areCyclicDuplicates(scale1, scale2) {
// If lengths are different, they can't be cyclic duplicates
if (scale1.length !== scale2.length) return false;
// Concatenate scale1 to itself and check if scale2 is a substring
return (scale1 + scale1).includes(scale2);
}
// Function to generate scales recursively
function generateScales(currentScale, totalNotes, largestStep, currentNotes) {
if (currentNotes === totalNotes) {
scales.push(currentScale);
return;
}
for (let step = 1; step
Oh the powers of two when not limiting the stepscan be thought of akin to finding the power set of a set. From set theory. Cool find!
Hypothesis before watching the rest of the video after the intro:
Simple induction. Base case: X1 = 1 (Can only do hop of 1), X2 = 2 (big hop or 2 small hops)
Xn = Xn-1 + Xn-2
So, X3 = 2 + 1 = 3
X4 = 3 + 2 = 5
X5 = 5 + 3 = 8
Hey, this pattern's looking familiar, isn't it? It's Fibonacci!
Two questions: given jumps of length 1 or 2 as discussed in the video, and assuming either length jump is equally likely, what is the expected value for the number of jumps?
What if the frog can make a jump of any length (from 1 up to and including all the remaining lily pads) randomly chosen such that the probability of any particular length jump is equal. So, at the start, with 100 lily pads, it could jump 1, or 2, or 3, or … 100, each with the likelihood of 1/100. For example, let’s say 50 for the first jump, so now the next jump would be 1, or 2, or … 50, with 1/50 probability. Say the next jump is 21, now 1/39 for the remaining jump, say 13, now 1/16, say 8, now 1/8, say 3, now 1/5, say 4, now 100% chance of jumping 1 to the final lily pad. What is the expected value for the number of jumps?
I haven't watched Numberphile in a while now, it has been a couple of years. My first thought after starting the video was "What happened to James Grime??" 🤣
I was a Math major.
I'm a little disturbed, but fascinated, by the way he draws X's, and sticks with parchment.
I get it, but it isn't normal.
Looks beautiful though! I sometimes make my symbols look artistic!
*Two* really nice moments.
Though I didn't get why x98 + x99 = x100.
x89 and x99 sound like huge numbers but only 1 jump away from x100, so I never would have thought they _sum_ to x100, instead I would have thought x98 + 1 = x100.
Same question here.
The ways to get to x99 seem to be a set that's largely contained in the set that solves x98. 🤔
I had the same issue and had to do a bit more reading/thinking on it. Hopefully this will help!
Let's simplify this down to the number of ways to get to 5 spaces. There are eight.
a)2+2+1
b)2+1+1+1
c)1+2+1+1
d)1+1+2+1
e)1+1+1+1+1
f)2+1+2
g)1+2+2
h)2+1+2
Now let's look at the way to get to 4 spaces:
i)2+2
j)2+1+1
k)1+2+1
l)1+1+2
m)1+1+1+1
Finally, let's look at all the ways to get 3 spaces:
n)2+1
o)1+2
p)1+1+1
If you notice, all of the examples for getting 5 are actually ALL of the ways to get 3 and all of the ways to get 4 with just one additional step.
1) a = i +1
2) b = j + 1
3) c = k + 1
4) d = l + 1
5) e = m +1
6) f = n + 2
7) g = o +2
8) h = p +2
If you'll notice, 1)-5) are all of the ways you can go to pad 4 with an additional + 1 and 6)-8) are all the ways you can get to pad 3 with an additional + 2. This is what they mean when they say that the only way you can get to the 5th lilypad is to either be at the 3rd lilypad and make a jump of 2 or to be at the 4th lilypad and make a jump of 1. Any way that you could go from pad 3 to pad 5 by first resting at 4 is already encapsulated by all the ways you can get to pad 5 via pad 4---because all of the ways to 4 necessarily include any permutation where the penultimate move is at 3. Trying to include again would be tantamount to double counting.
More concisely: The number of routes to X_n is the same as the number of routes to X_{n-2} plus the number of routes to X_{-1}---but the individual unique sequences are necessarily elongated by the addition of a +2 and +1, respectively.
@@erikfinnegan It might be easier to visualize if you go back to x3=x2+x1
x1 is 1
x2 is 1,1 or 2
x3 is 1,2 or 1,1,1 or 2,1
1,2 is just x1 and an extra jump of 2
1,1,1 and 2,1 are both x2 and an extra jump of 1
I actually played with the formula at 10:20 to try to see how it relates to Binet's formula for a closed-form expression, and at first I didn't take into account that x0 = F1, but it fits perfectly except that you get n+1 in Binet's after expanding this. Pretty cool to see it derived!
wait. there's a way to get the nth Fibonacci number _without_ using recursion or loops??
Wait til you learn that easiest way to get nth Fibonacci number is matrix multiplication
@@250minecraft You can get it even faster with fast matrix power; basically it involves squaring the matrix repeatedly. At that point, the real bottleneck is dealing with huge numbers.
@@pierrecurie I know
So, I actually tried to solve this before listening to the whole video, and did come up with a solution. My solution only works for even Fibonacci numbers, but I was still proud of it! You can find the Nth Fibonacci number Fn with the following formula, which is a sum:
Fn = sum(0->N/2) of (N-X) nCr X
So for instance, the 8th Fibonacci number is…
F8 = 8 nCr 0 + 7 nCr 1 + 6 nCr 2 + 5 nCr 3 + 4 nCr 4 = 1 + 7 + 15 + 10 + 1 = 34
(I didn’t know at the time that I was calculating Fibonacci numbers, but it worked out)
I reasoned that with an even number of lily pads, you could take 0 double jumps all the way up to N/2 double jumps. If you take 0 double jumps, you have chosen to double jump 0 times across N pads (8 nCr 0). If you perform exactly 1 double jump, you reduce the total number of jumps by 1, and can choose any of those jumps as your 1 double jump (7 nCr 1). If you double jump twice, you again reduce the number of jumps by 1, but now choose two jumps to be your double jumps (6 nCr 2). You continue this process of reducing the number of jumps by one and choosing one extra time until you are only performing double jumps (4 nCr 4).
It doesn’t quite work with odd numbers since it requires the number N/2 to be a whole number. Still, it works!
1] For X total pads, you can skip up to floor(X/2)
2] If you are skipping S pads then you are making S 2-jumps and X-2S 1-jumps (a total of X-S).
3] There are (X-S) choose S ways to order the jumps.
The above becomes a rather messy "factorials in a sigma" expression, but it's not too horrible to work with. And it will simplify the the same answer as in the video.
(Haven't watched the soln yet)
Assume there are S_(n-2) ways of hopping to stone n-2, S_(n-1) ways of hopping to stone n-1. Any path to stone n must land on either stone n-1 or n-2. If it lands on n-1, there is only one way of getting to n, ie just jumping one space, so S_(n-1) paths to stone n hit stone n-1.
Alternatively, if the frog lands on n-2. It has two options, jumping to stone n-1 and then stone n, or jumping directly to stone n. However the former is accounted for in the S_(n-1) ways of getting to stone n via n-1, so we count S_(n-2) ways of getting to stone n via n-2 (pv we don't use stone n-1)
In total, S_n = S_(n-1) + S_(n-2). Since S_0=1 and S_1=1, we conclude that S_n is the nth Fibonacci number.
The moment he wrote "x_n = " I realized it was induction, so I paused the video to figure it out. Once I found the formula x_n = x_{n-1} + x_{n-2} I knew it was the Fibonacci numbers. After that I just put "101st Fibonacci number" into WolframAlpha and got the answer, but actually solving the recurrence relation with initial values and getting the exponential formula was better! Great video!
So, basically, it is very easy to find an upper bound for this (but it's a pretty big one):
Define each jump of length 1 as 0.
Define each jump of length 2 as 1.
Each possible pattern of jumps is now represented by a unique binary number consisting of 50 to 100 digits, where each digit represents an individual jump. The upper bound is, therefore, 1267650600228229401496703205375 - which comes out as 100 times the digit 1 when expressed as binary.
Now of course we know the actual number can't be this high, because if every jump were a jump of length two, then only 50 jumps could happen in total. But it gives us a very quick guesstimate for the kind of dimensions we're working with
I remember doing this exact problem in high school precalc! I ended up writing code to brute force it, but then proved the pattern on the whiteboard, which was such an awesome realization
My approach was: For the first step, the frog can either jump 1 or 2 steps. If it jumps 1 step, it has then all the possibilities for 99 steps left. If it jumps 2 steps, it has all the possibilities for 98 steps left. So x_100 = x_99 + x_98 ... which leads to the same result, just not doing it "backwards" from the end but forwards instead, which I think is simpler and more straightforward...
Multiplying the equation (L^n - L^(n-1) - L^(n-2) - ... - 1 = 0) by (L-1) gives (L^(n+1) - 2 L^n + 1 = 0)
This problem was given to my daughter in her early high school maths class. I found it really fun and worked out that it was Fibonacci-related.
If you state that the frogcs mate at the other side wants to see the frog do all possible combinations before arriving, you could have an interesting rephrasing that would require determining if the lillypad quantity is even or odd.
When the number of lillypads is a multiple of three the frog will finish on the "wrong side" of the pond.
I absolutely LOVE linear recurrence relations. After discrete maths in uni, I'd do them for fun. I recently reminded myself how again. The equations where the weird roots or trig functions cancel out are the coolest. The notation here is different from what I learned, but not too dissimilar. We had car for "constant" and "ratio," I think.
I first encountered this problem years ago in university as a "tiling problem" - you have rectangular tiles of size 1x2, how many ways are there of tiling a strip of floor 2xn long. There was the same extra credit problem - "what if you have 1x3 tiles on a 3xn floor?" only that resulted in the interesting sequence x(n-3)+x(n-1)=x(n). If you have both 1x3 and 1x2 tiles, things get quite complicated, as you can have a block of 6 length that could be either two threes long or three twos long.
It was an interesting problem I would recommend Tom look into it.
1:30 before watching further, I want to make a guess, it feels like it could be something to do with binary representation, so I will guess there are somewhere around 2^50 different permutations.
One more step (jump ?). What happens if the frog could jump 1 to J spaces ? What is the relation between J and Lambda ? How exponentially is growing the number of occurrences according to J ?
I stumbled onto all that beautiful mathematics years ago by playing Xenogears for playstation 1. The turn-based attack system utilizes the triangle, square and x buttons in a similar manner to frog leaps. I always thought it was a very unique and clever battle mechanic and I'm glad I took the time to count all the different ways of attacking back then and make all those connections and generalizations.
Let's think of a real-world example of an animal that doesn't want to touch water... frog it is! 😂
But it's traveling faster by jumps
It should've been cats, lol.
Cats and bathtubs.
5:28 when there are 4 lily pads, the 5 different ways the frog can jump are 1111, 22, 112, 211, 121. All of these numbers have the digit sum 4 and are only made of the digits 1 and 2. That means when there are n lily pads, the total number of ways the frog can jump is all the numbers written only using 1 and/or 2 that have the digit sum n.
If we try this with n=3, the numbers would be 111, 12, 21. All of them have the digit sum 3 and are dont have any other digit than 1 and 2.
Using the n=0 case as an initial value is pretty dodgy IMO, you could argue that it should be 0 as we're not counting a 0 distance jump anywhere else. Much better to use n=1 and n=2 to fix the constants. Those aren't hard to do, because the defining equation for lambda allows you to reduce lambda squared easily.
You need to verify the answer with induction anyways
But n=0 is the initial value. It's philosophical but there's only one way to do nothing, and that's to do nothing. And anything to the zeroth power is 1 so it makes sense in the equation. And 1, 1 is how the Fibonacci numbers starts off. That's how you get to 2, by adding the two previous numbers, 1 and 1. You could consider n=0 to be 0 but then you aren't doing math at that point with n=0 and you have to carve out arbitrary rules to make n=1 and additional n work mathematically. 0, negative numbers, imaginary numbers, and others, are just an extension of the rules we've discovered for our real world numbers, you have to follow those rules to the end for mathematics to logically work. You can't just argue n=0 equals 0 because it feels right, it has to follow logically.
@@jmhorange There's no inherent reason why allowing no jumps is allowed in the problem more than allowing negative (or fractional) jumps. Even the recurrence relation is only actually defined for n>=3: there is no a priori reason why, eg, x_1= x_-1 + x_0. Everything outside positive integer n is a continuation of the original problem into a previously undefined domain. It is not part of the problem itself, which is why it wasn't part of the exploration earlier in the video and why it's a poor choice to use such a point to solve the original problem.
you're considering the problem to be the size of the jump when the main problem is how many ways to reach the last lilypad. doing nothing with 0 lilypads is still an entry because it's the same as already being at the last one. is it an unsatisfactory answer from a storytelling perspective, sure, but that doesn't change the maths.
The real reason it is valid to say x0=1 is because at that point, we are trying to solve the recurrence relation independent from the frog problem. If we choose to start with x0=1, x1=1 just because we can, then x2=1+1=2 just like in the real problem. From there the sequence continues exactly the same, so solving the problem with the addition of x0=1 doesn't actually change anything. If it was a slightly different problem where x2 was different but the Fibonacci pattern remained, you could "solve" for what value of x0 continues the pattern as x2-x1.
the frog should definitely do the one block vertical jump for the steak
Great Numberphile video, but I'm also interested in the room this was filmed in. That table looks worn down by hundreds of years of use, and what kind of books are behind the cages?
It would be an honour to work in a place with so much history.
it's St Edmund Hall Old Library, a college of Oxford University [where Tom is an Outreach Fellow ]... there's a 3d "wikispace" for it with a 360 interactive image so you can pan around. if you search for; _wikispace St Edmund Hall Old Library_ you should find it
edit to add: looking at the wikipedia entry for the college, you'll also find the quote "the oldest surviving academic society to house and educate undergraduates in any university"
- estimated to have been established by 1236, possibly earlier - so yeah :) quite a history :)
The frog is so cute, I love its happy smile and eyes!
The way it unfolded to me was to write the recursive function for X(n). The function would return 1 if n=0 or n=1, otherwise it would return 1 + X(n-2) [the frog starts with a jump of two, then completes with X(n-2) jumps] plus 1 + X(n-1) [the frog jumps 1 and completes with X(n-1) jumps.
I did this with combinatorics. If you have n Steps of 2, you have 100-2n Steps of 1. So in total 100-2n+n=100-n Numbers to arrange. You can arrange 100-n Numbers (100-n)! times. But 2,1,1' is the same as 2,1',1 and so on. So you have to divide by n! and (100-2n)! to extract this equal combinations. Sum up the Terms from n=0 to n=50 and you have the same awnser.
I know it's not fibonacci number related, but it's about that exponential growth. In my early days of learning a bit more advanced math, the teacher said something like "Let's say you have 3 books and you want to arrange them in every possible combination on your bookshelf. There are 6 different ways to arrange the, Now let's say you have 10 books to arrange in every possible combination, how long would it take you? Let's say it took you a 10 seconds to arrange the books in a new order." It seems almost simple, it's only 10 books, maybe a couple hours. But it would take over a year of continuously rearranging the books. And adding just 1 more book would now take over 12 years. (Yes, it's when I learned about factorial).
That's why I love the idea of how many possible combinations can a deck of 52 cards be arranged in. It's such a stupidly large number that most people can't wrap their head around it.
because I'm lazy - I did an approximation: minimum jumps required is 50, maximum 100, so average is about 75 jumps for all permutations. Each jump has is 2 options (Except last jump, but use base 2 anyway) -> 2 ^ 75 ~= 3.77e22
Which is in the same realm of magnitude as 5.73e20 - close enough :D
For me an easier way of looking at this being fibonachi is not going from the end, but going form the start.
If there are let's say 5 lilipads (X5), the frog can jump 1 lilipad and still have 4 to go (X4), if it does a big jump, it has 3 lilipads to go (X3).
If I know how many ways the frog can jump 4 lilipads (X4) and 3 lilipads (X3), then the sum should be the amount of ways how to jump 5 lilipads (X5).
To avoid making a guess of what the solution is and then afterwards confirming you guess was correct, I'd advise to solve the problem as an eigenvalue problem. This is a robust way of deducing the solution to the equation x_n = x_n-1 + x_n-2.
The "high school" intuition is that when a problem leads to a quadratic equation and the solution is somehow sign constrained, then one root leads to a valid solution and the other is discarded. The idea that the actual solution should be obtained as a linear combination of both roots comes out of the blue.
Do you know why it is that the solution is a linear combination? My thought was the same, that it would be the nonnegative solution of the quadratic solution.
@@veessee I don't know how much you know about linear algebra, so I will answer as if you knew only the absoute basics - vectors and matrices.
The math the author is hiding from us is probably a couple weeks' worth of Linear Algebra 101. Just to signal what's involved - if you represent the two initial values in the Fib sequence as the column vector vector [1,1], then iterating the recursion that defines the sequence can be reframed as repeatedly transforming this vector with the matrix [[0,1],[1,1]]. After each step, you will get a vector whose coordinates are two consecutive terms of the Fibonacci sequence.
On the other hand, every such transformation/multiplication of a vector by a matrix can be understood as a transformation of the whole plane if you consider how it affects any possible vector [x,y] rather than just [1,1]. When viewed like this, this transformation is geometrically equivalent to simultaneously stretching or compressing the plane along two lines through the origin. This might be difficult to visualise, so let me break it down:
- there are two lines through the origin, U and V, that are uniquely derived from the matrix
- each of these lines has an associated scaling factor, also derived from the matrix
- to "apply the matrix" to point P on the plane, you first take the "coordinates" of that point as if U and V were the axes of the coordinate system; that is, you measure the side lengths of the parallelogram with opposite corners at the origin and P, and sides parallel to U and V
- then you apply the associated scaling factors to these coordinates; this gives you the position of the point (still in uv coordinates) after the transformation
Now if you iterate this procedure, and look at how the u and v coordinates (measured along the lines U and V as described above) change, you will notice that at each step the u coordinate is multiplied by one scaling factor, and the v coordinate is multiplied by the other scaling factor. This means that the sequences of successive u and v values are two independent geometric sequences. So if the uv coordinates of the initial vector [1,1] are called [u₁, v₁], and the scaling factors are called λᵤ and λᵥ, then after n iterations it's [u₁λᵤⁿ, v₁λᵥⁿ]. You recognize the powers of λ from the video, right?
Now, we are interested in the xy coordinates, not in the uv coordinates, so we need to map these uv coordinates back to xy; we are also only really interested in the y coordinate, because the Fibonacci sequence is a sequence of numbers, not points. This is where the linear combination comes into play: when you derive this inverse mapping and take just the y coordinate, what emerges is the linear combination of the scaling factors (named λ₁ and λ₂ in the video) raised to the n-th power. I know I am still skipping over details here, but at least you can take my word that this linear combination emerges as a result of a step-by-step derivation, rather than as a divine revelation that "the solution must be of this particular form".
Some actual terminology used in linear algebra:
- the directions of the lines U and V are represented as vectors called the *eigenvectors* of the matrix
- the scaling factors associated with the eigenvectors are called the *eigenvalues* of the matrix
- the polynomial that was set to 0 and solved in the video as the equation to get the eigenvalues is called the *characteristic polynomial* of the matrix
"Just to satisfy my curiousity." is a nice summation of the number of ways that there are to enjoy mathematics.
I really love that room.
The way that an integer recurrence can be solved with square roots reminds me of one that Matt Parker posted the other day.
if rand() is defined as a function that returns a random number from 0 to 1 then the square root of rand() gives the same distribution as the maximum of two rand() functions.
Does 2 ^ (n/2) work? There are 2 ways to get to the second lily pad. Then there are 2 ways to get from lily pad 2 to lily pad 4. So 2x2 possible ways to get to lily pad 4. Then 2 ways to get from lily pad 4 to lily pad 6. So 2x2x2 or 2^(6/2) ways to get to lily pad 6.
So the logical follow up question is: What if you allow any jump length >0? That is actually pretty easy.
Using the same method as befor, you end up with X(n)=X(1)+X(2)+...+X(n-1), thus the n-th term is just the sum of all the previous terms, which means it just doubles with every step.
So it should be 1, 2, 3, 6, 12, 24, 48, 96....
You'll find that it's not "1, 2, 3, 6, 12, 24, 48, 96...."; in fact, it's "1, 2, 4, 8, 16, 32, 64, 128...."
@@Anonymous-df8it
....you are right of course.
For some idiotic reason i thought X(3) was still 3... which it isn't.
Fun fact, the solution for the 1, 2 or 3 problem is the tribonacci sequence a(n+2).
Explicit formula for the tribonacci function.
a(n) = j*C^n + k*r1^n + L*r2^n
where
C = (1 + (19-3*33^(1/2))^(1/3) + (19+3*33^(1/2))^(1/3))/3 [C is the real root to x^3-x^2-x-1=0]
p = ((3*C-5)*(C+1)/4)^(1/2)
m = (1-C)/2
r1 = m+p*i [r1 and r2 are the complex roots to x^3-x^2-x-1=0]
r2 = m-p*i
j = 1/((C-m)^2 + p^2)
a = -j/2
b = (C-m)/(2*p*((C-m)^2 + p^2))
k = a+b*i
L = a-b*i
Philippe LALLOUET, Jun 23 2007
Back in 1992, the problem we were given to investigate for our GCSE coursework was like this, but adding 1's and 3's rather than 1's and 2's.
it get's more exciting when you start exploring primes .. well done!
Instead of recursion, I used combinatorics, arriving at:
Total number of ways to cross = sum i=0->50 of (100-i)Ci
Exactly same answer :)
I wonder if there's a way to go about the problem with Markov Chains.
I have to disagree with the 0 case though. "You're already there" is the same as allowing no jumps. Which would add infinitely many ways to cross the lilypads. Why force the first two fibonacci numbers in? Fibonacci himself didn't even use them.
So how many ways do you think there are of doing nothing? (Mathematically, you can get it by working backwards - what do you have to have added to 1 to get 2 - or by treating the Fibonacci numbers as a special case of the gamma function).
The sequence of zero jumps does not contain any jumps of length zero, so it is a valid solution.
@@matejlieskovsky9625 Yes. The difference between nothing and the set containing nothing.
There are 3 possible sequences to jump across 3 lily pads: (1,1,1), (1,2), (2,1)
There are 2 for jumping across 2 lily pads: (1,1), (2)
There is 1 for 1 lily: (1)
There is 1 for no lilys: ()
(0), (0,0,0), (0,0,0,0,...) etc. are not valid, because a jump of distance 0 (jumping in place) was never valid to begin with. The frog is already at the goal when it started the journey, so there is nothing to do, and there is only one way to do literally nothing.
I love how you actually derived a direct formula for the Fibonacci numbers.
10:00 Same, but a bit more compact:
(((1+R)/2)^(n+1) - ((1-R)/2)^n+1)/R with R=sqrt(5).
From the binomial expansion it is clear to me that the even powered terms will cancel and from the odd powered, an even power of R remains after finally dividing by R.
I'm kinda proud that I anticipated the fibonacci sequence already at the 6:43 mark :D I liked the frog model to visualize the whole thought experiment :3
While you were talking about x2, I was thinking about x0=1. That set the sequence up to be 1,1,2,3. I believe x4=5. I wonder if the final result will be the Fibonacci sequence.
edit: Just seconds later you talk about the conditions to reach lilly-pad number 100, being either a jump of 2 from 98 or of 1 from 99, and now I'm absolutely certain the sequence is simply the Fibonacci sequence.
And the number of ways to get to -1 is zero, since the frog cannot jump backwards.
This exactlly was the problem demonstrating the dynamic programming when I was taking the Algorithm lecture in University. 🥰
Ello! From the other side of the pond.
I won't say anything about what that drawing on 3:39 looks like, butt I will say I'm immature enough to be distracted by it.
If it takes 1 second per leap across the pads for a 1 or 2 long jump then how long would it take a frog to jump all possible combinations when n=100? E.g., jumping 2,2,2,2,2,2,2... is 50 seconds (50 jumps) but 1,1,1,1,1,1,... is 100 seconds.
It would take the frog 41544212574050115730575 seconds, which is 1317358338852426 years, 108 days, 17 hours, 36 minutes and 15 seconds.
So it would take roughly 100000x longer than universe has existed to try all combinations at a rate of 1 second per leap for 100 lilypads. Oof. Really big numbers indeed.
I absolutely LOVE an answer this satisfying!
Another fun problem for you guys, how many different ways can a chess king walk from it’s starting square e1 to e8 in 7 moves
14 year old me solving this problem for a freaking leetcode problem when I'm bored by my own project and tired of staring a c++ error is fascinating.
Would the sequence for 1, 2, or 3 jump sizes be called the Tribonacci numbers?
DYNAMIC PROGRAMMING!
This is the classical "Climbing Stairs to reach at the top" Dynamic Programming problem(Computer Science):
There are n stairs, a person standing at the bottom wants to climb stairs to reach the nth stair. The person can climb either 1 stair or 2 stairs at a time, the task is to count the number of ways that a person can reach at the top.
This makes me think of a related problem: given a set of coin denominations, how many ways can they add to a given value. Like U.S. has 1, 5, 10, and 25 cent coins. How many ways make a dollar?
This type of question can be solved using generating functions. The answer is the coefficient of x^100 in (1+x+x^2+...)(1+x^5+x^10+...)(1+x^10+x^20+...)(1+x^25+x^50+...).
Interestingly, if you allow hops of any size up to n, the number of ordered partitions of n becomes simply 2^(n - 1).
If you could do it by jumps of any length, it's 2**98., i.e. the number of ways you could record the center 98 pads as hit-or-missed.
This is one of my most favourite numberphile videos.
Man, seems molecular dynamics are turning more mainstream and I really like it
Come on Brady, you already know about the Golden Ratio relationship from the Brady Numbers.
I've been thinking that there's something interesting noting that all possible Fibonacci-like sequences (those made by summing some finite rolling pattern of the previous terms) is dominated by 2^n by counting two ways: 2^n frog-paths with no restrictions and Fibonacci-like-ly many when restricted to some set of legal jump sizes. You can even see the largest real solution to the sequence of equations "sum(x^n, n=0..N-1) = x^N" approaches 2 as N -> infinity, corresponding to frogs being allowed to take larger and larger jumps and the set of legal paths becomes the set of all paths.