If you're seeing this message, it means we're having trouble loading external resources on our website.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

Main content

# Path counting brain teaser

## Video transcript

let's say you have a 6x6 grid and that's what I've drawn right here one two three four five six one two three four five six and you were to start in the top-left corner so you were to start right here and your goal is to get to the bottom right corner you want to get right there where the star is and you can only move in two ways you can only move to the right or you can only move down you can't move diagonally you can't move up you can't move to the left so in every step you can't move diagonally and every step will get you a little bit closer to this star so you can't have backward moves and my question to you is how many different ways are there to get from here to here that's the problem so you could pause it now and try to solve it and I'll try to when you unpause it slowly work to the solution and you could pause it anywhere you can kind of view all the intermediary steps as hints so the way to think about is well you know one just let's do the easy ones let's figure out how many ways can I go from here to each intermediate cell and maybe that'll help us to figure out how many ways can we get to this end point so let me pick a suitable color how many ways can I get from this starting point to this cell right there well I can only go one way right I can only go from here right straight to the right so there's only one way let me write that right there one one way to get there and how many ways can I get to this cell right here there's only one way I can only go straight down remember I can't go to the right down and then the left because left is not allowed every step has to give me some progress to my goal so it looks like we've we've made a little bit of progress so how many ways can I get to this cell let me write this how many ways can't get to this cell right here well I could go to the right here and then I could go one more step to the right and that's pretty much the only way I can get there right if I go down I can't go back up so there's only one way to go there by the same logic only one way to go there just straight out one way to go there one way to go there similarly these are kind of you can kind of view these as symmetric I mean this is when you go straight to the right this is if you go straight down so this is one 'we just straight all the way down one way one way one way fair enough now let's do a slightly more interesting cell how many ways are there to get to this cell right here how many ways oh this first time let's draw it out we could be there go down and to the right and we could go right and down alright so there's two ways to get to this cell that's fair enough and this was easy to do to work out all the ways because there aren't that many but you might already see an interesting pattern if I'm if I have a cell here let me draw a couple of cells let me draw three cells no that's not what I'm going to do let me draw it like that and draw it like that you know let's just say this is some arbitrary cell someplace in this grand doesn't you have to be a six by six grid it could be an N by n good we can do this problem with a hundred by a hundred but then the video would take long and do all of the math but let's say I wanted to figure out how many ways can I get to this cell right here and let's say I know that there are n ways to get to this cell and M ways not M M ways to get to that cell so how many ways can I get there well the only way to get to this cell and I'll do it in another color the only way to get to this cell based on the rules I got gave you is either to go straight down or go straight to the right so you can either go from this cell straight down or you could go from this cell and straight to the left or straight to the right so how many total ways can you get to this cell well the other ways you could have gotten to this cell is by going down from here but there's n ways you could have gotten there right so there's n total ways that you could get to this cell and then go to this cell and then there's my you could get to this cell and then go to this cell right so this cell or this box I keep using the word cell maybe because my brain is fixated on Excel there are n plus M ways to get to it and hopefully you understand that intuition because there's two ways to get to this cell directly from that one and from that one and I'm saying that there's n ways to get there so if all of the ways to get here there's n ways to get here before or that and same logic for that and you saw that right here with the twos one plus one so there's two ways to get there now let's see if that logic holds one more time just because I don't want you to just take this set as a leap of faith it should make sense to you so how many ways are to get here so based on what I just told you I should just be able to add two plus one and say three but let's see if that works out so I can go all the way to the right that's one I could go to then I could go down that way three and notice out of all of the three ways to get here one of them comes from this cell and two of them comes from this cell so that makes sense relative to the intuition I just gave you so let's just fill out this box let's just follow the box this one's going to be one plus two is three as well let's fill out let me switch colors just to make it interesting this was one plus three is four three plus three is six three plus one is four and you can kind of see a symmetry along this diagonal right there's a 3 and a 3 a 4 and a 4 and if you've done if you've seen the videos on the binomial coefficients or Pascal's triangle you should hopefully start seeing a pattern or some recognizable numbers here suppose this is 5 and this is this square has all sorts of neat things here right you have all ones and you have one two three four five six well six right one plus five 64 5 6 6 plus 4 is 10 6 plus 4 is 10 10 plus 5 is 15 15 plus 6 is 21 10 plus 10 is 20 10 plus 5 is 15 21 see this is 35 35 70 35 plus 21 is 56 35 plus 21 is 56 56 Plus 70 is 126 126 and then 21 26 plus 126 is 252 so let me do that in a special color there's 200 right that's yeah 252 ways from getting from there to there and that was just a neat kind of pattern problem to understand this and you can just fill it out and you can actually drew this for any and buy and it doesn't have to be n by n you could figure out you know I could have set the problem how many ways are there to get to this square and you would have solved and once you see that patent you can just do simple addition and figure it out to do it by hand to figure out the 252 ways of getting there would have taken you forever it would have it would have wasted all of your time but there's something interesting here is if you did watch the video on binomial coefficients you'll recognize that these are the binomial coefficients so if you look at actually let me draw something for you and maybe you'll recognize it there let's say you wanted it to take and this is all bonus relative the problem you have now solved it if your whole goal was just to solve this problem and not too little see how it connects to other mathematics then you can stop watching it now but now I'll show you something neat about it we learned so if you wanted to figure out X plus y to the nth power and we do this a lot in the videos on Pascal's triangle and binomial coefficient but I want to show you it's the same exact thing here this might actually be even an easier way for you to do it then when you then using Pascal's triangle although it's essentially the same thing if we write if you write 1x X x squared X to the third X to the fourth X to the fifth these are supposed to go on top of the square but I realize I was running out of space all right 1 + y Y squared Y to the 3rd Y to the fourth Y to the fifth and if I were to say given this what is x + y I don't know to the fourth power so what you can do is you can say okay well X plus y to the fourth is gonna be you know X to the fourth plus something something something a bunch of terms all the way to Y to the fourth and everything in between so you go as you go here where you say oh x2 the fourth all the way down to Y to the fourth so it'll be this diagonal right here so let me draw this diagonal so this diagonal right here and these will essentially tell you the coefficients and not only will it tell you the coefficients will tell you it will tell you the mix of the coefficients so what do I mean by that so let me erase some stuff here and this is all bonus to the actual problem we've solved the problem so I can erase all of this so we want to figure out X plus y to the fourth all we have to do and I'll leave you to play with this cube a little bit more just to see all the patterns in it and what do the numbers do along each row and each column and each diagonal but if you want to figure out X plus y to the fourth or actually just you go this is X to the fourth or you could say one X to the fourth one X to the fourth x wat 1 which is just 1 X to the 4th plus 4 4 X to the 3rd times y right that's just this one right there then you say plus 6 x squared Y squared x squared Y squared and then we're at plus 4 X Y to the 3rd and then finally plus 1 Y to the 4th times just a 1 or an X you might say that's amazing Sal how did that work and the really way to think about the thing that the way to think about it is when you multiply this X plus y to the 4th and I encourage you to try it if you're bored one day there's actually six ways to get an x squared Y squared term you'll see that when you multiply it all out and we did that in kind of the intuition behind the binomial theorem videos but there's six ways to get there which is the exact same problem that's a part of the brain teaser that I gave you before how many ways can you get to this square while we figure it out there are six ways anyway hopefully you enjoyed that a little bit