Math for fun and glory
- Cheryl's birthday
- Heavier ball
- Liar truth-teller brain teaser
- Toggler brain teaser
- Alien abduction brain teaser
- Blue forehead room brain teaser
- Blue forehead room solution
- Forehead numbers brain teaser
- Light bulb switching brain teaser
- Path counting brain teaser
- 3D path counting brain teaser
3D path counting brain teaser
Extending the path counting to three dimensions. Created by Sal Khan.
Want to join the conversation?
- Let's say we want to genenalize the path counting teasers and figure out the formula for an N-cube (a hypercube in N dimensions) that has a side of M squares long(16 votes)
- Let's start with a square as shown in the last video. To get to the star, you need to go 5 right and 5 down, a total of 10 moves. The right and down moves can be arranged in any order, so long as there are 5 right and 5 down. For example
D D R D R R D R D R
So the problem becomes, how many unique ways can we arrange the above letters? There are 10! ways to arrange 10 letters, but since there are 2 letters repeated 5 times, we need to divide this by 5!5! giving:
(Note: Check the probability/ combinatorics videos if you're confused)
This can be generalized to:
(Number of total moves)!/((Number of moves per direction)!)^Number of directions
Now for a square, cube or hyper cube, the number of moves needed in each direction is M-1. The total number of moves is the number of moves needed in each direction is N(M-1), and the number of directions is simply the number of dimensions of the figure, which is N.
Now substituting these values into the previous equation gives:
This works for a cube of any dimensions and doesn't require any of the meticulous adding as shown in the video. The same logic can be used to find the total number of possible paths to any node in sub a figure. Simply take the factorial of the total number of moves and divide it by the product of the factorials of the number of moves needed in each direction.
It's interesting because the above formula for two dimensions is the same formula for finding values in Pascal's triangle. Thus, what I'm doing is the exact same thing as Sal, except I'm skipping all the adding and simply using a formula to determine such values.(22 votes)
- At6:45, can't it be like we are in a building , & are trying to get to the exit of the building.(4 votes)
- Yes, its basically like your in a building, but not quite. It does however look like you are trying to exit the building.(3 votes)
- how many ways are there if it is four layers?(4 votes)
- Think is four layers because that's why is four layers(2 votes)
- I wonder if this would work for other shapes such as compilations of squares in different shapes, and how the algorithm would change.(4 votes)
- At1:36he says we cannot go back up. Why can't we?(2 votes)
- so it wouldn't be to complicated for us to understand.(2 votes)
- Isnt there six sides not three? So wouldn't there be more paths?(3 votes)
- The video say that you can't go back, so it end up 3 sides(1 vote)
- 6!/(2!2!2!)=90. SImple!
Because we have a total of 6 moves, which consist of 2 Lefts, 2 Downs and 2 Forwards.(3 votes)
- the middle in the blue/purple square should be a zero because you are not able to get to it(2 votes)
- Yes you are. You can go right then down then in, or right then in then down, or down then in then right, or down then right then in, or in then down then right, or in then right then down. That is all six ways listed.(2 votes)
- What happend with a hypercube with the dimensions of 3x3x3x3.
I found that it had 2272 could somebody check it?(1 vote)
- A 4-cube with dimensions of 3 by 3 by 3 by 3 would have 2,520 ways.(3 votes)
- How do you write the number with your mouse so perfect? I suck at it.(1 vote)
- He is using a drawing tablet that inputs physical contact onto the monitor.(3 votes)
Let's see if we can extend the path counting brain teaser to three dimensions. So let's say that I had a three by three cube. I'll keep it at three by three to keep the math from getting too hairy. So let me draw it like that. I won't use a line tool just because-- well, maybe I should have. So let's see. The front of the cube looks something like that. That's the front of the cube. And the cube goes backwards like that. Comes down. Goes like that. It's a three by three, like a Rubik's Cube. I could have drawn this little bit better, but I think this will meet our needs. OK. There you go. Three by three cube. And so our goal is to get from this back left cube. This top corner back left cube. And get to this front, bottom right cube. So this is our goal. I'll do it in this yellow. This is our goal right there. And we're allowed to either go forward. From any cube, these are our three operations or our three movements we can do. We can go forward, or I guess towards the front. We could go down. Or we can go to the right. So I can draw it here. We can go from that cube to that cube. So just like the two dimensional problem, you're only allowed to make forward progress. You're not allowed to come down here, and then go to over here. You're allowed to go down here, then here, but then you're not allowed to go up. So every step you're getting a little bit closer, from this back left top cube, to this front bottom, right cube. And so the same question applies, how many different ways are there to get from there to there? And you can pause it now and try it yourself, because I'm about to explain how to do it. And the first thing, when you tried to do it yourself, is to realize, boy this is hard to visualize. Even if I had to draw this out, I'd have to go in and then out. I mean, how do I even visualize a three dimensional cube like this? And the best way to do is to separately visualize each of the separate layers. So let's do that. Let's make this the magenta layer up here. We'll call that layer one. So this is the magenta layer up here. And you'll see what I'm doing in a second. This is the mauve layer right there. And then finally I'll do the orange layer. The orange layer is that one right there. What we can do is separately draw each of these layers. So first, let's do the magenta layer. So the magenta layer will look like this. And now I'll use things that help-- nope, not like that. I want to use the other tool. The magenta layer. Let me draw some squares in here. It's like that, and like that, and like that, and like that. And then, the middle one was the mauve layer. We'll draw that. The mauve layer looks something like that. And you can imagine I'm slicing it, and just looking at it from above. That's the idea here. And it's going to help us visualize this problem. So the mauve layer looks something like that. And then finally the orange layer. Looks like this. And we're almost ready to actually start doing the problem. Good enough. So just to make sure we understand our visualization, this layer up here-- we call that layer one. We could but this as box one. This layer is layer two. So I'll put a little two here. And I don't want to get these confused with the paths and all that, so I'm writing it really small. And this is layer three, or level three. And that's right there. And just to make sure you understand, this corner right there, this is our start point. And that's right there. Right? Because this is a whole top. So this is the back left of the top. And are finish point, the bottom right, is right here. So, essentially, our problem goes from, how many ways to get from there to there, to how many ways to get from there to there? So let's just stay within a layer. So how many ways can I get to this point right here? Well I can only go from this point, and go straight in the layer like that. So there's only one way to get there. That movement is the exact same movement as this right here. Going from this box to this box. So there's one way to get there. That's the same thing as there. And similarly, I could go there. And I can just go one more step. So there's only one way to get there. And that's like going there and then there. And by the same logic, I could go one to the right here. That's the only way to get there. Or I could go two to the right there. And that's the only way to get there. And now if you watched the two dimensional path counting brain teaser, you know that there's two ways to get here. And the logic is, well you could draw it out. You could go like that. One, two. And that's the same thing as saying, one, two. Though it's easier to visualize here. But the general logic was, well, to know how many ways to get to any square, think about the squares that lead to it, and how many ways can I get to those two squares? And then sum them up. And by the same logic-- so there's two ways to get here. That's that cell. Three ways to get here, right? Two plus one is three. One plus two is three. And three plus three is six. So there were six ways to get to this cube right there, from that one. So this isn't too different from the two dimensional problem so far. But now it gets interesting. So how many ways-- I did this in yellow, but I should have done it in the color of that layer. How many ways are there to get to this cell right here? This cell is that one right there. Well, I start here. And I can just go straight down. There's only one way to be there. But I go straight down. So there's only one way to get there. Actually let's extend. There's only one way to get here, if I'm going straight down. And so there's only one way to get to this cell too. I'd have to go straight down again. So there's only one way to get there. Hopefully you understand the way we're visualizing it. This is the bottom row. And there's only one way. You go from here, straight down to there, straight down to there. And that's the only way to get there. Fair enough. Now this is where it gets interesting. How many ways are there to get to this cell? Well in our old example, there was only one way in two dimensions to go from this cell. But now we can go from this cell, and we could come from above. And where's above? Above is right there. So now we add this cell to that cell. So one plus one is, there are two ways to get there. How many ways to get to this? You can't even see it. This is kind of in the back middle of this cube. How many ways to get there? Well, there's two ways to come from this direction. And I can also come from above right there. So two plus one is three. How many ways to get here? Well, one from behind. And then one from above. So that's two. And you see a little bit of symmetry. And how many ways to come here. Well there's two here. From going straight forward. Two ways to go that way. And then one way to come from above. This is two, and we're on this cell. So if we wanted to know how many ways to get to this cell? There's two ways to go from there. And then one way from above. So that's three. And now, right here, how many ways to get to this cell? There's three ways. I could come from here, from here, or from above. So I have the two plus two plus two is six. Likewise, here, I can come from six plus three is nine. But I can also come from above. From here. So there's 12 ways to get there. And you can do the same logic. How many ways to get here? Well, within the same row there are nine ways. Six plus three is nine. And then you could come from above as well. That's 12. And finally, how many ways to get to this cell right here, which is this one right there? Well, there's 12 ways to get here. So I could go all of those ways. 12 ways to come from behind it, so that's 24. And then six ways to come from above. So 12 plus 12 is 24 plus six is 30. I think you're seeing the pattern. So how many ways to get here? Well it's one plus two, which is three. How many ways to get here? Well it's three plus three, which is six. How many ways to get here? It's one way here, and two from above. So it's three. How many ways to get here? Well, three from behind and three from above. That's six. Here, it's three plus three is six. But you could also come from above. So six again. So that is 12. How many ways to get here? 12 plus six is 18. But there's 12 ways to come from above as well. So 18 plus 12 is 30. And by the same logic, there's 18 ways to get here from these two cells. But I could also come from above. So that is 30. So how many ways to get to this last cell? Well there's 30 from this direction. 30 ways from there. 30 ways from behind it. That's 60. And then there's another 30 ways to come from above. So there are 90 ways. I could write that there, but you can't see it. 90 ways to get from that cell over there to this cell over here. And then the last video, I made the analogy to the binomial theorem. And I'll leave you to think about what the three dimensional analogy is. And I'll throw out a word which is never really mentioned in math class, because it's normally too hairy to deal with. Think about formulating a trinomial theorem, to help you multiply things like x plus y plus z to nth power. And think about how this cube, or an extension of it. This is a three by three by three cube. But imagine if it was, you know, an n by n by n cube. Then you can start taking things to arbitrary powers. So I'll leave you to think about this. But I just thought this was a neat visualization problem, which is really not any more difficult than the last one. Actually, before I leave you I'll leave you with just a general principle. And this is actually really useful for some standardized tests, or just logic games. If I'm trying to get to this cell. And let's say there's a bunch of ways to get here. And it has to have direction. So I won't go into a whole graph theory thing. But it has to have direction. And you can't have cycles. Because then you can have infinite ways to get to a certain point. And let's say that there are x ways to get there. Y ways to get there. z ways to get there. And a ways to get there. I'll cycle through the alphabet. And this is just a subset of the larger graph. This graph could have a bunch of connections. This is just where we are. These are all of the nodes that connect to this. The general rule that we've learned in the last two brain teasers is, you say, OK, how can I get to this node? Well I can go from here, here, here, or here. And I just have to add up. So if I can get from here, there's x ways to come via this node. Y ways to come via that note. z ways to come via that node. a ways to come via that node. So the total ways to get to that node is x plus y plus z plus a. And actually, you'll see problems like this if you ever plan on becoming a lawyer. They actually do have problems like this on the LSAT, that aren't maybe as complicated as what we did here. But you need understand this principle. Anyway hope you enjoyed that.