Vertices of a cube

Some of you may recognise this question from the Oxbridge interview questions thread...

How many ways there are of getting from one vertex of a cube to the opposite vertex without going over the same edge twice?

Ok, firstly I have taken opposite to mean diagonally opposite. My method was to draw a graph of a cube and then select one vertex and find a way to the diagonally opposite one (say A and A'). I then listed all the cycles that contain A', of which there are 3. In total I found 12 ways of going from A to A'.

It is a bit difficult to explain without a diagram, so I will try and get one up as soon as I can. Until then though if anyone can understand what I am talking about, is 12 the right answer?

Reply 1

generalebriety

I think I get 30. I could be wrong, though, because I spent two minutes on it. :p:

Reply 2

ghostwalker

I agree with 30, though it took a bit more than 2 minutes.

Edit: I am assuming that when you reach the opposite corner you stop, and aren't allowed to loop out and back in again on unused paths.

And also that opposite corners are on a straight line through the centre of the cube.
(thanks DFranklin)

Reply 3

DFranklin

To be definite: if each edge has length 1, is |AA'| = \sqrt{2} or \sqrt{3}?

Reply 4

miml

generalebriety

I think I get 30. I could be wrong, though, because I spent two minutes on it. :p:

ghostwalker

I agree with 30, though it took a bit more than 2 minutes.

How? Although looking at my graph I can see a whole load of paths that I have missed out.

Reply 5

generalebriety

miml

How? Although looking at my graph I can see a whole load of paths that I have missed out.

Can you post your method? I'm quite happy to post (a sketch of) my solution if you want, but it'd be much more helpful for you to see where yours went wrong.

DFranklin

To be definite: if each edge has length 1, is |AA'| = \sqrt{2} or \sqrt{3}?

Though I know the question wasn't directed at me, I'm taking |AA'| = sqrt(3).

Reply 6

miml

DFranklin

To be definite: if each edge has length 1, is |AA'| = \sqrt{2} or \sqrt{3}?

\sqrt{3}

Reply 7

miml

After drawing the linked diagram I started counting the paths

eg ABCA' but we can go from CDB'A' . ie one extra as there is a cycle
I got 6 possible paths + 6 paths due to the cycles
ABCA'
ABD'A'
AC'B'A'
AC'D'A'
ADCA'
ADB'A'

However, I can see I have missed out some of the more 'complicated' paths such as A B D' C' B' D C A'. Having written this I think it might be possible to substitute B' A' with B' D C in a similar way to what I did previously.

Reply 8

generalebriety

I don't understand what you mean by a cycle, but nonetheless, let me explain the way I did it.

In going from A to A', I can start off by making three choices; either AB, or AC', or AD (where by "AB" I mean "move from A to B", etc.). Let's pick AB arbitrarily for now. I then have two choices: either BC, or BD'. Let's again arbitrarily pick BC for a minute. Now, once we're at C, we don't have much choice; we can go straight to A' (which gives one solution), or first to D; once at D, we can go via B' (which gives two solutions - count them), or via A (which gives two solutions - count them). So having done ABC, we have five ways of getting from C to A'.

Can you see how to get from here to the solution? Try it yourself before opening the spoiler (which contains a full solution).

Spoiler

Reply 9

miml