### 載入中...

相關課程

⇐ 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.

載入中...