Current time:0:00Total duration:10:42

0 energy points

# Path counting brain teaser

Counting paths in a square. Created by Sal Khan.

Video transcript

Let's say you have a
six by six 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 can pause it now
and try to solve it. And I'll try-- when you unpause
it --slowly work to the solution. And you can pause it anywhere. You can kind of view all the
intermediary steps as hints. So the way to think
about it is, well 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? I can only go one way, right? I can only go from here,
straight to the right. So there's only one way. Let me write that right there. 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 made
a little bit of progress. So how many ways can I get
to this cell right here? 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, you can kind of
view these as symmetric. I mean, when you go straight to
the right, this is if you go straight down. So this is one way. 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? Well, this first time,
let's draw it out. We could either go down
and to the right. And we could go right
and down. Right, 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 have a cell here. Let me draw a couple of cells. Let me draw it like that. And draw it like that. And let's just say this is some
arbitrary cell someplace in this grid. It doesn't even have to
be a six by six grid. It can be an n by n grid. We could do this problem
with 100 by 100. But then the video would take
long to do all of the math. But let's say I want 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 n --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 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 can go from this cell
and straight to the right. So how many total ways can
you get to this cell? Well the only ways you could
have gotten to this cell is by going down from here. But there was n ways you could
have gotten there. So there's n total ways that
you could get to this cell, and then go to this cell. And then there's m ways that
you could get to this cell, and then go to this cell. 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 of all of the ways to get
here, there's n ways to get here before that. And same logic for that. And you saw that right here. With the two, is one plus one. So there's two ways
to get there. And let's see if that logic
holds one more time. Just because, I don't want
you to just take this as a leap of faith. It should make sense to you. So how many ways are
there 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 could go all the
way to the right. That's one. I could go two. Then I could go down
and 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 fill out the box. This is going to be one plus
two is three as well. Let's fill out-- let me switch
colors just to make it interesting. This is 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 three and a three. A four and a four. And if you've seen the videos
on the binomia coefficients, or Pascal's triangle, you should
hopefully start seeing a pattern, or some recognizable
numbers here. So what's this? This is five. And this square has all sorts
of neat things here. You have all ones. And you have one, two, three,
four, five, six. Well, six right? One plus five. Let's see, four, five, six. Six plus four is 10. Six plus four is 10. 10 plus five is 15. 15 plus six is 21. 10 plus 10 is 20. 10 plus five is 15. 21. See, this is 35. 35. 70. 35 plus 21 is 56. 35 plus 21 is 56. 56 plus 70 is 126. And then 126 plus 126 is 252. So let me do that in
a special color. There's 200, right? yeah, 252 ways from getting
from there to there. And that was just a neat kind
of pattern problem, to understand this. And you could just
fill it out. And you can actually do
this for any n by m. It doesn't even have
to be n by m. You could figure out, I could
have said the problem, how many ways are there to
get to this square? And you would have solved it. Once you see that pattern, 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 wasted
all of your time. But there's something
interesting here. If you did watch the video on
binomial coefficients, you'll recognize that these are the
binomial coefficients. Actually let me draw something
for you and maybe you'll recognize it there. And this is all bonus relative
to the problem. You have now solved it. If your whole goal was just to
solve this problem, and not to see how it connects to other
mathematics, then you can stop watching it now. But now I'll show you something
neat about it. 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 coefficients. 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, than using Pascal's triangle. Although it's essentially
the same thing. If you write one, x, 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. You write one and y, y squared,
y to the third, y to the fourth, y to the fifth. And if I were to say, given
this, what is x plus y, I don't know, to the
fourth power? So what you can do is, you say
OK, well, x plus y to the fourth is going to 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 as you go here, where you
say, x to 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 to the coefficients. And not only will it tell
you the coefficients. It will tell you the mix
of the coefficients. So what do I mean by that? So let me erase some
stuff here. 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 the 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 this is
x to the fourth. Or you could say one
x to the fourth. One x to the fourth times one,
which is just one x to the fourth, plus four x to
the third, times y. Right? That's just this one
right there. Then you say, plus six
x squared y squared. And they we're at plus four
x y to the third. And then finally plus one
y to the fourth times just a one or an x. And you might say, that's
amazing Sal. How did that work? And the way to think about it
is, when you multiply this x plus y to the fourth-- 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 as the brain teaser
that I gave you before. How many ways can you
get to this square? Well, we figured out
there are six ways. Anyway hope that you enjoyed
that a little bit.