Main content

### Course: Math for fun and glory > Unit 2

Lesson 1: Brain teasers- 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

© 2024 Khan AcademyTerms of usePrivacy PolicyCookie Notice

# 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:

10!/5!5!=252

(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:

(N(M-1))!/(M-1)!^N

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)

## Video transcript

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.