If you're seeing this message, it means we're having trouble loading external resources on our website.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

## Math for fun and glory

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

Lesson 1: Brain teasers

# 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
• 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.
• At , can't it be like we are in a building , & are trying to get to the exit of the building.
• Yes, its basically like your in a building, but not quite. It does however look like you are trying to exit the building.
• how many ways are there if it is four layers?
• Think is four layers because that's why is four layers
• I wonder if this would work for other shapes such as compilations of squares in different shapes, and how the algorithm would change.
• At he says we cannot go back up. Why can't we?
• so it wouldn't be to complicated for us to understand.
• Isnt there six sides not three? So wouldn't there be more paths?
• 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.
• the middle in the blue/purple square should be a zero because you are not able to get to it
• 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.