Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

A $3 \times 3$ cube is composed of $27$, $1 \times 1$ cubes. Moving along the surface of the larger cube, how many ways are there to get from the closer top-left vertex, to the further bottom-right vertex?

Constraints:

  • You may only move along the surface of the cube
  • You may only move right, down, and forward
  • You may only move on the edges of the smaller cubes
share|improve this question
1  
I'm not posting this as an answer since the result can be obtained without a computer; I just coded it to decide which of the various answers given are correct. This code counts $384$ paths. You can vary the number of dimensions and the number of subdivisions if you like. –  joriki Feb 28 '13 at 23:55
    
Thank you joriki. That is the solution I have also obtained using a slightly different method than those previously stated. –  Brian Silva Mar 1 '13 at 0:38

5 Answers 5

up vote 7 down vote accepted

Name the faces of the $3\times3$ cube touching the start A, B, and C. Name the faces touching the finish vertex D, E, and F. Any valid path lies within just two of these faces - one of A, B, and C, and an adjacent one of D, E, and F.

The number of paths that lie entirely within faces A and D is $9\choose3$. (Unfold the two faces into a $3\times6$ rectangle.) Similarly, there are $9\choose3$ paths that lie entirely within faces A and E, if A and E are adjacent, etc. There are 3 ways to choose one of A, B, and C and for each choice, two of the faces D, E, and F are adjacent, so this method counts $6{9\choose3}$ paths.

Unfortunately, this counts paths twice if they begin or end (but not both) by traversing an entire edge of the larger cube, and it counts paths three times if they both begin and end by traversing an entire edge of the larger cube.

The number of paths counted exactly twice is $3\cdot({6\choose3}-2)+({6\choose3}-2)\cdot3=108$, and the number of paths counted exactly three times is 6.

All told, then, there are $6{9\choose3} - 108 - 2\cdot6 = 384$ paths.

share|improve this answer
    
This seems to be correct; see my comment under the question. –  joriki Mar 1 '13 at 0:24
    
I really like this method. I tried to do something similarly before hand and failed miserably, but this is very nice. Thanks! –  Brian Silva Mar 1 '13 at 0:42

If you are interested in a general solution, for any $n x n$ cube, I will show you.

Odd $n$, where $n$ is the $k^{th}$ odd integer: $\frac{(3n)!}{(n!)^{3}} - 3[2(\frac{(3n-3)!}{((n-1)!)^{3}}) + 6(\frac{(3n-4)!}{((n-1)!)^{2}(n-2)!}) + 6(\frac{(3n-5)!}{(n-1)!((n-2)!)^{2}}) + ... + (\frac{(n+1)!}{(k!)^{2}})(\frac{(n+1)!}{(n-1)!((n-k)!)^{2}})]$

Even $n$, where $n$ is the $k^{th}$ even integer: $\frac{(3n)!}{(n!)^{3}} - 3[2(\frac{(3n-3)!}{((n-1)!)^{3}}) + 6(\frac{(3n-4)!}{((n-1)!)^{2}(n-2)!}) + 6(\frac{(3n-5)!}{(n-1)!((n-2)!)^{2}}) + ... + 2(\frac{(n+1)!}{(k)!(k+1)!})(\frac{(n+1)!}{(n-1)!(n-k)!(n-k-1)!})]$

share|improve this answer
    
You may be correct, but I think my solution generalizes to give this much simpler expression for the answer on an $n\times n\times n$ cube: $6\cdot({3n\choose n} - {2n\choose n})$. –  Steve Kass Mar 1 '13 at 3:36

At the beginning you can choose one of three options. Once you pick the first option you wont be able to move in one direction until you have done one of the two movements you can do at least three times.

Therefore wee need to count the nine digit numbers made of exactly three of each of the following digits: 1,2,3 such that there are not all three digits appear before the first third digit appears for example:

1,1,2,2,1,2,3,3,3 works but 1,2,3,1,2,3,1,2,3 does not because three of the same kind don't appear before all three types appear. To do this count the correct numbers in which the third type of number appears in the fourth,sixth and seventh

share|improve this answer
    
This is exactly my process and I counted 384 ways. 1680 including inside travels and 1296 on only inside travels. Someone can check –  Alex Feb 28 '13 at 23:23
    
what do you mean inside travels and outside travels? –  Jorge Fernández Feb 28 '13 at 23:27
    
I mean that they are travels where you must go on the inside of the cube, because the question asks for only surface or "outside" travels –  Alex Feb 28 '13 at 23:30
    
I tested this method as well and obtained an answer of 600. However, this answer doesn't match one I obtained in another way. I'm going to work on this more to obtain a confident answer. –  Brian Silva Feb 28 '13 at 23:32
    
What did you get Jorge? By the way, you can only use the 3rd 4th and 5th positions for the third letter. And, this can be done 3 times - for all the combinations of two letter. –  Alex Feb 28 '13 at 23:51

[Note: As @joriki points out, this is wrong, though perhaps elegant...]

Or much more easily, take the required 9 steps as follows, which will generate all possible paths once each.

  1. Choose one of the three initial directions.
  2. For the next 7 steps, you will have exactly two directions to choose from.
  3. You will have no choice for the last move.

This gives $3\cdot 2^7$ paths.

share|improve this answer
    
This looks very elegant but unfortunately it's wrong (though the result is right). On the second move, you have all three options, whereas if you first exhaust two of the directions you have only one choice for more than one final move. –  joriki Feb 28 '13 at 23:59
    
Good catch, @joriki! –  Steve Kass Mar 1 '13 at 0:12

Like Pascal's triangle, store 1 in the starting vertex, and for each vertex $a$ connected to a vertex with a stored value, add the values of all such connected vertices and store it in $a$.

Right, down, and forward are simply distance in the graph of the edges & points from the start, the further bottom-right vertex the furthest.

EDIT AGAIN: I count 512.

share|improve this answer
    
You can count more than 54 by just going over 2 faces and going between opposite vertices. –  Brian Silva Feb 28 '13 at 23:43
    
Oooooops I did it with a 2 by 2 by 2 cube. –  Loki Clock Mar 1 '13 at 0:02
    
Okay, now I've done it. –  Loki Clock Mar 1 '13 at 0:26

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.