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.
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.
@@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.
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
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
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.
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.
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 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.
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
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.
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.
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 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
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 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 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.
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. 😔
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!
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.
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));
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.
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 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!
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 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??" 🤣
@@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!
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?
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.
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.
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.
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.
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!
Tom: It looks awful. Also Tom, just 25 seconds later talking about the very same expression: This is a really good example of the beauty of mathematics
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
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
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.
(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.
This was very cool! My intuition was to guess 2 to the power of 100 since each pad has 2 states as in having or not having the frog and there's 100 of them. I would have never guessed there's a relationship with the Fibonacci sequence. Then again, I'm not as mathy as I used to be. Thank you for sharing. And Tom's a pretty cool guest. Nail and Gear forevah!
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.
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.
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.
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
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.
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!
I remember figuring out the iterative form of the Fibonacci, because I wanted to display a visual Pascal's Triangle (and highlight the angled Fibonacci in it, as well as the total) in a browser, but the recursive approach ran me out of memory too fast and my visual triangle was boring due to how small it was. By moving to the iterative, I was able to make a very large triangle such that the next problem was space to hold the giant numbers at the bottom of the triangle.
*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
Ok. I want frogs that can jump up to 5. Because the quintic has no general solution. That is when integer solutions to an equation become truly amazing.
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 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.
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...
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.
It’s not about the numbers of jumps, but about the numbers of possibilities. There are no more possibilities to get from X99 to X100 than going for the one jump.
(X)n is number of possibilities, not number of steps. In case (X)99 there’s no other options for you. In case of (X)98 we chose the condition that it will jump 2 steps ahead and no other routes are possible.
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 ?
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
😎😎😎
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 like to believe that Tom lives in that chair, and Brady just visits him from time to time.
can confirm.
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.
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.
I love these videos. A gentle reminder to myself of just how much there is to learn, and how little I actually know.
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.
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
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.
This is so unrealistic. A frog that thinks about how many ways it can jump definitely doesn't have a mate waiting for him.
😂
12:40 - For some reason, that little frog sound at the end of the long answer cracked me up. 😅
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.
Frogonacci numbers
Ribbitnacci was right there.
🐸
We get to the best pun after hopping around for just a ribbit.
Amphibonacci
No
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.
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!
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
This combinatorics problem is just awesome!
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.
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
I love the tattoo of one of the most important constants in mathematics on Tom's finger: the number 3.
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.
Average CSc student: "Hey, I have seen this one, this is a classic!"
Numberphile: "What do you mean you've seen it? It's brand new!"
Cue frog eating a McFly
@@Half_theBattleI'm lovin' it.
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.
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
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
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.
2:11 I love the showcase of the Parker frog
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.)
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
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).
11:05 I love the frog blithely hopping across the Fibonacci numbers
CS majors having leetcode flashbacks rn
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 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.
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. 😔
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!
The most decorated mathematician I ever saw. Respect.
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.
Same story here. My parents told me "You won't get a job if you're not qualified".
I really love that room.
The frog is so cute, I love its happy smile and eyes!
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));
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.
"Just to satisfy my curiousity." is a nice summation of the number of ways that there are to enjoy mathematics.
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.
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.
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 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!
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.
it get's more exciting when you start exploring primes .. well done!
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??" 🤣
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!
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?
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.
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.
This is one of my most favourite numberphile videos.
I think the frog's little froggy brain exploded from too many choices ... 😆🐸
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.
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.
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!
Tom: It looks awful.
Also Tom, just 25 seconds later talking about the very same expression: This is a really good example of the beauty of mathematics
These frogs look soo lovely!!
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
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
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.
I love how you actually derived a direct formula for the Fibonacci numbers.
I absolutely LOVE an answer this satisfying!
Man, seems molecular dynamics are turning more mainstream and I really like it
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.
(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.
This was very cool! My intuition was to guess 2 to the power of 100 since each pad has 2 states as in having or not having the frog and there's 100 of them. I would have never guessed there's a relationship with the Fibonacci sequence. Then again, I'm not as mathy as I used to be. Thank you for sharing. And Tom's a pretty cool guest. Nail and Gear forevah!
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.
Wow! Tom's best vid yet.
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.
This exactlly was the problem demonstrating the dynamic programming when I was taking the Algorithm lecture in University. 🥰
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.
Another great video on your channel! Thank you.
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.
the frog should definitely do the one block vertical jump for the steak
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
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.
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)
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!
I remember figuring out the iterative form of the Fibonacci, because I wanted to display a visual Pascal's Triangle (and highlight the angled Fibonacci in it, as well as the total) in a browser, but the recursive approach ran me out of memory too fast and my visual triangle was boring due to how small it was. By moving to the iterative, I was able to make a very large triangle such that the next problem was space to hold the giant numbers at the bottom of the triangle.
*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
Ok. I want frogs that can jump up to 5. Because the quintic has no general solution.
That is when integer solutions to an equation become truly amazing.
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.
my favorite math meme is a photo of a smiling bill cosby with the caption “tan(b)/sin(b) = “
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.
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...
"alright so we're a frog"
man
I wish
Would the sequence for 1, 2, or 3 jump sizes be called the Tribonacci numbers?
14:00 That's called Tribonacci sequence
So much fun
Joey Tribonacci from Friends...?
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.
4:27 There I got lost. Why X98+X99 = X100? Wouldn’t it be X98+1+X99+1= X100?
My question exactly....
Yeah this immediately confused me. In my head my immediate concern is double counting and similar issues
It’s not about the numbers of jumps, but about the numbers of possibilities. There are no more possibilities to get from X99 to X100 than going for the one jump.
@@thomasd8694 But „the one jump“ is exactly what I am missing in the further calculations…
(X)n is number of possibilities, not number of steps. In case (X)99 there’s no other options for you. In case of (X)98 we chose the condition that it will jump 2 steps ahead and no other routes are possible.
If you allow jumps of any length, you get f_n = 2^(n−1) for n≥1
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 ?
The entire video I was screaming to myself, “FIBONACCI!!! GOLDEN RATIO!!! φ!!! MY FAVORITE NUMBER!!!”
Interestingly, if you allow hops of any size up to n, the number of ordered partitions of n becomes simply 2^(n - 1).