Here is the Question i'm trying to solve:

An ant is initially positioned at one corner of the Rubik's cube and wishes to go to the farthest corner of the block from its initial position. Assuming the ant stays on the gridlines, how many different paths are possible for it to get to the far corner. Assume that there is no backtracking (it is always moving closer to its goal) and that the ant can travel on any of the six sides. (Be careful about not including paths more than once.)

I am uncertain I correctly calculated all the paths, please correct me if I made a mistake!

I started by realizing that the total number of paths on a rectangular gird is given by either the combination of: C(length+width, width) or C(length+width, length). I then concluded that any path going from one corner to it's opposite corner must to through exactly two faces of the cube. The number of path to go through two faces is then C(9, 3), and that there are six ways to make pairs of two faces starting from the ants corner.

C(9, 3) * 6

However, I believe I have included too many paths because some of the paths overlap. So I subtract every path that goes to the corners directly adjacent to the original corner, which is:

C(6, 3) * 3

So the grand total of paths should be: C(9, 3)*6 - C(6, 3)*3 = 444 paths


migrated from mathoverflow.net Apr 5 '14 at 15:49

This question came from our site for professional mathematicians.

  • $\begingroup$ "Shape theory" means something else. $\endgroup$ – Noah S Apr 5 '14 at 4:22

I think your idea is basically right. Remember, however, that there are two types of paths that have been double-counted: paths that pass through a corner adjacent to the initial corner, and paths that pass through a corner adjacent to the final corner. Therefore you need a factor of $6$ rather than $3$ in your second term.

Here's an inclusion-exclusion argument that clarifies things—at least for me: let the ant start at the front, bottom, left corner, and end at the back, top, right corner. Let the faces adjacent to the initial corner be called $F$ (front), $B$ (bottom), and $L$ (left), and let the faces adjacent to the final corner be called $F'$ (back), $B'$ (top), and $L'$ (right).

As you say, the ant's path lies within two faces. One of these will be an unprimed face; one will be a primed face. Define $P(X,X')$ to be the set of paths that lie within faces $X$ and $X'.$ We have $$ \lvert P(X,X')\rvert=\begin{cases}0 & \text{if $X$ and $X'$ are opposite each other,}\\ \binom{9}{3} & \text{otherwise.}\end{cases} $$ To use an inclusion-exclusion argument, we need to know the sizes of intersections of sets $P(X,X').$ As stated in your solution, intersections like $P(B,F')\cap P(L,F')$ contain $\binom{6}{3}$ paths since such paths must traverse the edge where $B$ and $L$ meet, leaving $\binom{6}{3}$ ways to get from one corner of $F'$ to the other. The same is true of intersections like $P(F,B')\cap P(F,L').$ There are six such intersections in all. The other non-empty two-way intersections are sets like $P(F,B')\cap P(B,L'),$ which contains the single path that traverses the edge where $F$ and $B$ meet, the edge where $F$ and $L'$ meet, and the edge where $B'$ and $L'$ meet. There are six of these as well. Finally, the only non-empty three-way intersections are sets like $P(F,B')\cap P(F,L')\cap P(B,L'),$ which contains the single path described above. There are six of these too.

Inclusion-exclusion then says that the number of paths is the sum of the sizes of all the sets $P(X,X')$ minus the sum of the sizes of all two-way intersections plus the sum of the sizes of all three-way intersections. This yields $$ 6\cdot\binom{9}{3}-\left(6\cdot\binom{6}{3}+6\cdot1\right)+6\cdot1=6\cdot\binom{9}{3}-6\cdot\binom{6}{3}=384. $$

  • $\begingroup$ Thank you so much for such an elegant response and brilliant solution! $\endgroup$ – will.fiset Apr 6 '14 at 2:36

In general, $f(n,n,n)=6(_{3n}C_n-_{2n}C_n)$

[1] http://www.maa.org/sites/default/files/pdf/pubs/Rubiks6.pdf


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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