Path Counting Brain Teaser

Back

⇐ Use this menu to view and help create subtitles for this video in many different languages. You'll probably want to hide YouTube's captions if using these subtitles.

Path Counting Brain Teaser : Counting paths in a square

相關課程

0 / 750

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.