Fall 2015, problem 1

The numbers $1,2,3,4,5,6,7,8$ are assigned to the vertices of a cube so that each vertex has a different number. Find the probability that no two consecutive numbers are written on vertices with a common edge, where $8$ and $1$ are considered consecutive.

Comments

2 years ago

For a cube numbering that satisfy such conditions, if we connect 1-2-3-4-5-6-7-8-1 each "-" would represent a either a face diagonal(F) or body diagonal(B). With only Fs, one can only travel in one of the two tetrahedra that does not share any vertex. So we need Bs - and we must have an even number of them (2 or 4), to get back to the original tetrahedra. With only B, one can only travel back and forth in one of the four pairs of vertices.

The only possible types of sequences of steps are FFFBFFFB(8x3x2x2, wlog suppose each vertex is distinct) and FBFBFBFB(8x3x2) and rotations of them. added: FFFBFFFB has 4 "rotations": 1-FFFBFFFB-1, 1-FFBFFFBF-1, 1-FBFFFBFF-1, 1-BFFFBFFF-1, and FBFBFBFB can also be BFBFBFBF.

Subtotal = 4 x FFFBFFFB +2 x FBFBFBFB Total: 8!

P(no consecutive)= 1/84? (~~1/280~~ strikethrough didn't work) I indeed forgot the 4 and 2...

Thanks mwoenker for the formatting guide!

I'm trying to keep the line separated, but using a list makes the font much smaller. Also it looks like either the whole post is a list or there is no list?

JiazhenTan 2 years ago

Paragraphs are separated by one or more blank lines -- in other words, you have to hit enter twice between paragraphs.

The formatting syntax is called markdown. It is basically the same syntax that is used in StackOverflow and Reddit, I believe. You can see a little documentation on it by pressing the question mark button in the editor. We need to write up something more detailed and make it more visible. Also we allow LaTeX syntax between \$...\$.

This looks like a better overview of the basics.

mwoenker 2 years ago

@Jiazhen I understood the first paragraph of your answer but what calculation you have done I don't understand that. So please elaborate your answer a little bit. Particularly I want to ask that what is subtotal and total and how you got the required probability to be equal to 1/280.

Singh 2 years ago

I think the reasoning of the second paragraph goes like this: If in order to label the vertices without consecutive numbers sharing a common edge, you need to label the first vertex with some number, then travel along a face diagonal or a body diagonal to another vertex and label that second vertex with the next number in the cycle of 1-2-3-4-5-6-7-8-1. If you get a box and dry tracing some paths around it, you'll notice that there are only two possible path types that a) visit each vertex exactly once and b) whose start and end points are the same place:

The first option is that you travel along 3 face diagonals, then a body diagonal, then 3 face diagonals, then a body diagonal(FFFBFFFB). There are 8 possible starting numbers. After labeling the first vertex, there are 3 possible face diagonals you could choose. After labeling the second vertex, there are 2 remaining possible face diagonals you could choose. After labeling the third vertex, there's only one face diagonal you can travel across without landing on an already labeled vertex. At the fourth vertex you then travel across the body diagonal (there's only one possibility). At the fifth vertex there are 2 viable face diagonals, and after the sixth vertex onwards the rest of the path is completely determined. So the total number of FFFBFFFB-type paths is 8x3x2x2=96.

The second option is that you alternate face diagonal, then body diagonal. There are 8 possible starting numbers. After labeling the first vertex, there are 3 possible face diagonals you could choose. After labeling the second vertex, you travel along the only possible body diagonal. After labeling the third vertex, there are 2 viable face diagonals to travel along. After labeling the fourth vertex, the remaining path is completely determined (body diagonal moves turn out to be a lot more restrictive than face diagonal moves). So the total number of FBFBFBFB-type paths is 8x3x2=48.

Then there is something about considering the different rotations of the paths, which results in the factors of 4 and 2, but I don't understand where those values come from.

Actually, the calculation comes out to 1/280 ignoring those factors: (96+48)/8! = 1/280.

Matthew 2 years ago

Thank you Sir Mathew for clearing my doubts.

Thank you Sir Jiazhen for elaborating your solution.

Singh 2 years ago

@Matthew thanks, that clarified a lot. I have skipped too many steps...

if we always start and end with 1, then permuting the 'F' and 'B's produce different results, so we have the 4 and 2.

JiazhenTan 2 years ago
2 years ago

Cute -- the key being the role of the two types of diagonals. I am getting lazy in my old age, so I cheated and wrote a Python script. FWIW, the answer I get is 1/84.

What's your algorithm? All I can come up with is checking all...

JiazhenTan 2 years ago

Tan:

Sorry for the delay. Just got back from Thanksgiving holiday, and before that, well, my day job ...

Truth to tell, I was rather embarassed by my first two iterations of the Python script for this problem. The following script is fairly tight. It does indeed iterate over all 8! = 40,320 permutations of the integers from 1 to 8. The script defines a canonical labeling on a "cube graph" (using the letters 'a' to 'h') and assigns integers according to their order in the current permutation, which is a list generated by the standard (since Python 2.6.x) "itertools" package. (It also uses the NetworkX Python package to implement simple graph operations.) The script is written in Python 2.7.10. I would strongly advise anyone interested in running this script to have a Python 2.7.x with x large enough to support the pip Python package installer, which can be used to install NetworkX. (For the record, I used my office workstation, an iMac running Mountain Lion.) Also, in earlier versions, I used the Matplotlib package to plot the cubic graph, just to check. (Sorry, no animations or labeling (yet). If I ever get around to updating my Web site ...)

The basic idea is that for every permutation, the assignment of integers by their "place" in the (ordered) list is checked for the non-consecutive integer constraint (with 8 adjacent to 1.) If the assignment is good, it is printed. The number of "good" permutations is just the number of output lines, which is 480, and 480/8! is 1/84.

Anyway, here is the code (some long lines have been broken in two; also, some underscores in the first few lines seem to have been eaten during the cut-and-paste):

import networkx as nx import itertools as iter

G=nx.Graph()

A=set('abcdefgh')

G.addnodesfrom(set(A))

nx.setnodeattributes(G,'label','0')

G.addedgesfrom([('a','b'),('b','c'),('c','d'),('d','a'),('e','f'),('f','g'),('g','h'),('h','e'),('a','e'),('b','f'),('c','g'),('d','h')])

for perm in iter.permutations('12345678'):

G.node['a']['label'] = perm[0]
G.node['b']['label'] = perm[1]
G.node['c']['label'] = perm[2]
G.node['d']['label'] = perm[3]
G.node['e']['label'] = perm[4]
G.node['f']['label'] = perm[5]
G.node['g']['label'] = perm[6]
G.node['h']['label'] = perm[7]

flag = False
for v in G.nodes_iter():
    v_value = int(G.node[v]['label'])
    for w in G.neighbors(v):
        w_value = int(G.node[w]['label'])
        diff = abs(v_value - w_value)
        if ( diff == 1 ):
            flag = True
            break

        if v_value == 1:
            if w_value == 8:
                flag = True
                break

        if v_value == 8:
            if w_value == 1:
                flag = True
                break

    if flag:
        break

if not flag:
    print "a,b,c,d,e,f,g,h = %s %s %s %s %s %s %s %s" % (perm[0],perm[1],perm[2],perm[3],perm[4],perm[5],perm[6],perm[7])
wgw 2 years ago

Thank you for sharing! I also just got my homework done...

JiazhenTan 2 years ago
2 years ago

Where do we stand on this now? Various solutions but no conclusive answer.

I too have written a program (in C) which confirms the result by wgw, i.e. 1/84

I am probably older than wgw and also somewhat lazy.

What's your algorithm? I don't have anything better than brute force...

JiazhenTan 2 years ago

I can send you the code if you give me your email address.

The 8 vertices are (0,0,0) ... (1,1,1) with adjacent vertices having the property that 2 of the coordinates are the same.

Populate each of the vertices with the permutations of 1..8 and pick out those items which do not have the property of adjacent vertices containing consecutive values.

I guess this could be viewed as brute force and this approach is only valid for the kind of problem which produces relatively small finite solutions.

If the problem were to be extended to "metacubes" of many dimensions I don't think it would fare very well.

PhilBoyd 2 years ago

Could you please send the code to 1942597938@qq.com? Just wondering if you are using a quadruple to represent each vertex or listed all 12 edges. Thanks in advance!

Update: Just got your code; somehow it got spammed... Thank you very much!

JiazhenTan 2 years ago
2 years ago

Below is a program in Prolog which I think generates all solutions, number of solutions: 480. Giving a probability of 480/8! = 1/84

Code is at: http://swish.swi-prolog.org/p/Prob1%20Solution.pl

The query to run is:

setof(L,create_sol(L),Ls),length(Ls,Len).

Output: Ls = [[0, 2, 4, 6, 3, 5, 7, 1], [0, 2, 4, 6, 5, 7, 1|...], [0, 2, 5, 3, 4, 6|...], [0, 2, 5, 3, 4|...], [0, 2, 5, 3|...], [0, 2, 6|...], [0, 2|...], [0|...], [...|...]|...], Len = 480.

2 years ago

Sorry ahead of time for my very long and space-consuming attempt at responding to this!

If you assign the eight vertices in a certain order, you can easily count the number of ways that assignments are possible. Let the notation n(a,b,c) be such that "vertex n" touches (vertex a, vertex b, vertex c). So for the following assignments, we have:

  • 1(2,3,4) can be assigned any number (8 ways to choose)
  • 2(1,5,6): 7 possible numbers to choose from, but 2 touch 1(2,3,4) .. (5 ways to choose)
  • 3(1,6,7): 6 possible numbers to choose from, but 2 touch 1(2,3,4) .. (4 ways to choose)
  • 4(1,5,7): 5 possible numbers to choose from, but 2 touch 1(2,3,4) .. (3 ways to choose)

Yet to be assigned are 5(2,4,8), 6(2,3,8), 7(3,4,8), 8(5,6,7)

From here we have a number of assignments to choose from for 5. Let the number line be --x-x-x-x-x-x-x-x-- and can be rotated and flipped in any such manner while preserving symmetry, so the actual digits don't matter. If we set assignment for 1 in one of the center two nodes, then possible permutations at this point are:

  • --2-3-4-x-1-x-x-x--
  • --3-2-4-x-1-x-x-x--
  • --3-x-2-x-1-x-x-4--
  • --3-x-2-x-1-x-4-x--

Note that 2 and 4 can actually be flipped and still preserve this structure. Immediately, we can see that the only arrangement that allows for 5, 6, and 7 assignment is the --3-2-4-x-1-x-x-x-- arrangement. So possible ways to determine 5 are

  • --3-2-4-x-1-5-x-x--
  • --3-2-4-x-1-x-5-x--
  • --3-2-4-x-1-x-x-5--

But since both 6 and 7 touch 3, only the third is viable, so we have --3-2-4-x-1-x-x-5--.

  • 5(2,4,8): 4 possible numbers to choose from, must touch 3(1,6,7) so that 6(2,3,8) and 7(3,4,8) are possible to arrange .. (1 way to choose)
  • 6(2,3,8): 3 possible numbers to choose from, can be either --3-2-4-x-1-x-6-5-- or --3-2-4-x-1-6-x-5-- .. (2 ways to choose)
  • 7(3,4,8): 2 possible numbers to choose from, cannot touch 4 .. (1 way to choose)
  • 8(5,6,7): 1 possible number to choose from .. (1 way to choose)

And finally, for the probability we have (8x5x4x3x1x2x1x1)/8! = 1/42 ... which is twice the result from simulations above... If anyone wants to point out where I went wrong, that'd be great.

Although I got lost when you started to assign the fifth node, I do want to note that, with different assignment for 1(2,3,4), 2(1,5,6), 3(1,6,7), and 4(1,5,7), the number of possible assignment for 5(2,4,8), 6(2,3,8), 7(3,4,8), 8(5,6,7) are different (also the problematic part in saikrishnapavan45 and Samurai's method).

For example, assign 1 to node 1(2,3,4), 3 to node 2(1,5,6), 5 to node 3(1,6,7), 7 to node 4(1,5,7), and...?

Making a semi-exhaustive list with your method, using the symmetry of a cube, won't be too much work, though.

JiazhenTan 2 years ago

Wouldn't that just represent a homomorphism though? Since the cube structure is preserved, vertex connections are also preserved, and naming is an arbitrary process and should have no effect on the probability. At least from my understanding.

KoriSmith 2 years ago

Really, try assign 1 to node 1(2,3,4), 3 to node 2(1,5,6), 5 to node 3(1,6,7), 7 to node 4(1,5,7) and try to assign a number to node 8(5,6,7).

Different assignments to node 1,2,3, and 4 produce different number of possible assignments for node 5,6,7, and 8, so something must be wrong with any formula that does not consider the assignment for the first four vertices.

However, I didn't quite get your number line idea. Would you please explain whether you are assigning numbers to node 1,2,3, and 4, or are you assigning the number 1,2,3, and 4 to the nodes? And how do you place the number line on the cube - does each x represent a node? or a number yet to be chosen?

JiazhenTan 2 years ago
2 years ago

Since there still seems to be some confusion, I'm going to try and break down Jiazhen Tan's proof to what may seem like excruciating detail. But then again, the proof really is not entirely trivial in the details. The answer is, of course, still $p = \frac{1}{84}$.

First off a - somewhat tedious - list of definitions (some of which are standard):

  • Let the corners of the cube be represented by the elements of the set $C \subset \mathbb{R}^3$, defined as:

$$C := \{(x_1,x_2,x_3) \in \mathbb{R}^3: \forall_{i=1}^3:x_i \in \{0,1\} \}$$

  • Let a point $p \in C$ be called even, if the number of coordinates of $p$ with value 1 is even. Otherwise call it odd. Whether $p$ is even or odd is called the parity of $p$.
  • For $p_1, p_2 \in C$ with $p_1 \neq p_2$ write $p_1 N p_2$ if $p_1$ and $p_2$ differ in exactly one coordinate ($p_1$ and $p_2$ are "neighbours"), write $p_1 F p_2$ ($p_1$ and $p_2$ are "face diagonal), if $p_1$ and $p_2$ differ in exactly two coordinates and finally write $p_1 B p_2$ ($p_1$ and $p_2$ are "block diagonal"), if $p_1$ and $p_2$ differ in all three coordinates.
  • A sequence $ p_1, p_2, .., p_k \in C$ is called a path if $\forall_{i=1}^{k-1}:p_i \neq p_{i+1}$. If in addition $p_1 = p_k$ and otherwise there are no repetitions, we also call it a loop. A loop is called a walkthrough if $k = 9$ and it contains every point $q \in C$. Finally a path is diagonal if $\forall_{i=1}^{k-1}:p_i F p_{i+1}$ or $p_i B p_{i+1}$.
  • Let $S := \{N,F,B\}$ be the set of neighbourhood symbols. For a path $p_1, p_2, ..., p_k \in C$ and a sequence $O_1, O_2, ..., O_{k-1} \in S$ with $p_i \neq p_{i+1} \forall_{i = 1}^{k-1}$ we say $p_1, .., p_k$ is of type $O_1, O_2.., O_{k-1}$ and write $p_1 O_1 p_2 O_2 p_3 .. p_{k-1} O_{k-1} p_k$ if $\forall_{i=1}^{k-1}: p_i O_i p_{i+1}$.
  • A bijective function $f: C \rightarrow \{1, 2, ..8\}$ is called an assignment if for all $p, q, \in C$ with $p N q$ the numbers $f(p)$ and $f(q)$ are not consecutive in the sense of the problem statement.

We have to prove that the number of assigments is $\frac{8!}{84}$.

  • [Statement (1)] If we have two corners $p \neq q$, then $p$ and $q$ have the same parity if and only if $pFq$. $p$ and $q$ have different parity if and only if $pNq$ or $pBq$.
  • [Statement (2)] The number of assignments is the same as the number of diagonal walkthroughs. This is, because by considering the path $f^{-1}(0)f^{-1}(1)..f^{-1}(9)$ for each assignment $f$ you create only and all diagonal walkthroughs exactly once.
  • [Statement (3)] All diagonal walkthroughs are of type $FFFBFFFB$, $FFBFFFBF$, $FBFFFBFF$ or $BFFFBFFF$ (class "$2B$") or else of type $FBFBFBFB$ or $BFBFBFBF$ (class "$4B$"). Proof: Let $w=S_1S_2..S_8$ be a type of walkthrough. Then there are exactly eight neighbourhood symbols in $w$ (rule 1), by definition. There cannot follow two $B$s immediately one after another, since we cannot go forth and back to the same point (rule 2). There cannot follow more than three $F$s right after one another, since there are only four different points of a given parity (rule 3). There must be an even number of $B$s (rule 4), since we start and end our walkthrough on the same parity (on the same point, indeed). The classes $2B$ and $4B$ mentioned above are easily the only sequences of $F$s and $B$s that satisfy rules 1 through 4.
  • [Statement (4)] All types of class $2B$ ($4B$, resp.)correspond to the same number of paths. Proof: Take a path $p_1..p_9$ of type $FFFBFFFB$ and start at $p_2$ and you get a path of type $FFBFFFBF$. This defines a bijective map from paths of type $FFFBFFFB$ to those of type $FFBFFFBF$. The other cases work analogously.

At long last, we now count the diagonal walkthroughs of the two remaining types $FBFBFBFB$ (type 1) and $FFFBFFFB$ (type 2).

Number of Walkthroghs of type 1: Let $p_1..p9$ be a walkthrough of type 1. Then $p_1 p_3 p_5 p_7 p_9$ is a loop of type $NNNN$) without repetitions. There are exactly $6 \times 4 \times 2$ of those. The factor of 6 because any $NNNN$ loop without repetitions is contained within one cube face (pen and paper) and there are 6 of those to choose from. The factor of 4, because there are 4 starting points to choose from in a given face. The factor of 2 because there are two ways you can go round the face. There are no additional factors for choosing $p_2,p_4,p_6,p_8$, because for every pair $p,q$ of corners $pNq$ there exists exactly one r with $pFrBq$.

Number of Walkthroughs of type type 2: Let $p_1..p_9$ be a walkthrough of type type 2. The points $p_1$ through $p_4$ are all of the even or all of the odd corners (factor of $2$: parity). Say they're the even ones. There are $4!$ permutations of the even points (factor of $4!$). $p_5$ is fixed by $p_4 B p_5$ (factor of $1$, if you will). $p_8$ is fixed by $p_8 B p_9$. So two choices remain for $p_6 p_7$ (factor of $2$).

Gathering all factors, the number of assignments is: $2 \times (6 \cdot 4 \cdot 2) + 4 \times (2 \cdot 4! \cdot 2) = \frac{8!}{84}$

2 years ago

Start with the vertex labeled 1 . it along with the other vertices have 3 common edges with 3 other vertices. Now the first one must not be a 8 0r 2 , leaving 3,4,5,6,7 ..four choices out of 7 so probability 5 /7. The other two now have that probability , yielding (5/7)(5/7)(5/7).Go to the opposite vertex ( diagonally opposite ) . do the same with it but now only 4 choices left , means of any label with again 3 common vertices 5/7 cubed . since this is an ' AND ' probability we multiply ..giving 5/7 to sixth power ..** not my final answer * lol Thinking now instead of 5/7 cubed it would be 5/7 x 4/6x3/5

When it becomes $\frac{5}{7} \cdot \frac{4}{6} \cdot \frac{3}{5}$, what would the expression of the other part change to?

Edit: What would be the probability that the other four vertices satisfy the conditions?

JiazhenTan 2 years ago

You mean the opposite vertex to the one first chosen? On diagonal ?

Samurai 2 years ago

Great question Jiazhen ..i havnt figured that out yet lol. Your attack by permuting the cobaecutive sequences along * diagonals might be the only way .i attempted this way and dont yet know how to compute p of the other 4

Samurai 2 years ago
2 years ago

The total no. of possible ways for arrainging the 8 numbers on a vertices of a cube is 8! (means 8765432*1= 40320.) as per the condition the total no of ways of no two consecutive numbers are written on vertices with a common edge is given by = 5C3 (means 10). The probability of no two consecutive numbers are written on vertices with a common edge of a cube is 10/8! .

           As the no. of possible ways for arrainging the 8 numbers on a vertices of a cube is same as arranging 8 different numbers in 8 different places which is 
          8! (8 factorial = 40320). As per the given condition no two consecutive numbers are written on vertices with a common edge consider a number "8" the total no. of 
          possibilities for placing a number beside 8 is 2,3,4,5,6. Eliminating 1 & 7 so the total no. of possibilities would be 5 numbers this includes eliminating the number 8
         as this number is already assumed to be placed from our initial assumption. so it gives the number of ways of placing an non-consecutive numbers would be (n-3)C3 
         the number 8 vertice is surrounded by 3 other vertices so any of these vertices cannot have the consecutive numbers so that 3 in (n-3)C3 represents thenumber of 
        surrounding vertices and n-3 represents the number of left out number other than the number placed at the vertice and its corresponding consecutive numbers.

Your attempt is similar to @Samurai's and have a similar problem; maybe you can try to list the possible arrangements after choosing 8 and 3 of its surroundings? Here's kinda a hint

JiazhenTan 2 years ago

True my friend Jiazhan , this one got past samurai ;) making use of the diagonals seems to be the kicker and best way to solve this one . trying to label and compute ( probabilty) dead ends

Samurai 2 years ago

I was on right track it seems thanx to saikrishna pointing out for the first vertex and common vertices thier can only be the numbers 3,4,5,6,7 which is the 5c3._as for the other 4 vertices , we need only subtract the events theses vertices have consecutive labels, which helps considerably if we assume the vertex opposite the first one as 1 will be 2 we must not have the 3 on the side of cube with label 2 .which means its on the side with label 1. So. Really its 4c3 not 5c3 :( sorry krishana no points awarded for that lol

Samurai 2 years ago

assume the vertex opposite the first one as 1 will be 2 ... Really its 4c3 not 5c3

Without loss of generality?

JiazhenTan 2 years ago
2 years ago

Please let me know if i am right . It would be helpful. Thanks in advance.

2 years ago

Any square (side of the cube) cannot have three consecutive numbers. Based on that, my solution is 4/315.

I agree that

Any square (side of the cube) cannot have three consecutive numbers.

But would you elaborate on how did you get $2^6$ configurations? How does your observation helped in your solution?

JiazhenTan 2 years ago
2 years ago

Yea wlog since its not necesary. The other was is to subtract from all the cases that this side of cube * has consecutive vertices which is easier to count since 4 numbers from the set of 8 chosen

2 years ago

The probability in the analogous problem for a hypercube in $\mathbb{R}^4$ is $\frac{147092404224}{16!} \approx \frac{1}{142}$. Can anybody confirm?

In four dimensions there are face ($F$) diagonals (two coordinates change) block ($B$) diagonals (3 coordinates change) and hyper ($H$) diagonals (all coordinates change). If you choose two corners $A, B$ of the hypercube that are diagonal and the line from A to B is...

  • ...$F$, then there are 828252336 good permutations that have the number 1 at A and the number 2 at B .
  • ...$B$, then there are 844757232 good permutations that have the number 1 at A and the number 2 at B .
  • ...$H$, then there are 844732320 good permutations that have the number 1 at A and the number 2 at B .

It's kinda interesting that it only makes a very slight difference, which type of diagonal you start with.

Here is the C program I used to compute the number 147092404224 of good permutations. It takes about an hour or so to complete on my machine. If you set the global variable dim = 3 you get the result for the $\mathbb{R}^3$ case, namely #(No Consecutive) = 480. If you uncomment a block in the main function, it will compute the probability by a Monte Carlo method. (If you set dim=5 it will not terminate in this life. Also the result would be garbage, anyway, because the long int type would overflow).

2 years ago

Regarding my post where I gave python code to count the correct answer, I did think about this problem last night, and I have the more elegant solution I'd hoped for yesterday. I don't know if this is Group Theory, or Operator Theory, or none of the above, because I'm really just an experimental physicist.

Consider the eight vertices of a cube. We'll number them 0, 1, ..., 7, and we'll arrange them so that 0, 1, 2, 3 form the vertices, in a clockwise manner, on the top plane of the cube, and vertices 4, 5, 6, 7 form the vertices on the bottom plane of the cube, also clockwise, with 4 under 0, 5 under 1, etc.

Let's start, arbitrarily, at vertex 0. You have a group of eight vertices, split into two groups of four each, with: * Main Group: Vertices 0, 1, 2, 3, 4, 5, 6, 7 * Sub Group 1 being vertices 0, 2, 5, 7, and * Sub Group 2 being vertices 1, 3, 4, 6.

Note that if you start in Sub Group 1, and travel along any face diagonal of the group, you remain in Sub Group 1. The same holds for Sub Group 2. The only way to travel from Sub Group 1 to Sub Group 2 is via a body diagonal, which connects vertices 0 to 6, 1 to 7, 2 to 4, and 3 to 5.

This paragraph is not required for the solution, but is interesting and explains my python code: from any vertex there are three face diagonal moves you can make, which I'll call F1, F2, and F_3, and one body diagonal move you can make, which I'll call B. These can be written as functions, for any vertex n: * F1(n) = n xor 2, * F2(n) = n xor 5, * F3(n) = n xor 7, and * B(n) = n xor 6.

The problem statement says you have to place the numerals 1 through 8 (consecutively, where 8 is defined as consecutive with 1) on the eight vertices of the cube such that no two numerals are connected by a common edge of the cube. Thus each consecutive numeral must either be placed on the face diagonal or body diagonal of the previous numeral, and when you get to the last numeral (8), it must connect along a face or body diagonal to numeral 1.

Place numeral 1 on a vertex, let's say on vertex 0. If you restrict yourself to placing subsequent numerals on face diagonals, you get stuck in Sub Group 1 and run out of options after placing numeral 4. So you need a body diagonal to open up Sub Group 2. But the problem statement says you need to bet back to your starting point after placing numeral 8, so you need an even number of body diagonals to solve this problem.

Next, you can't follow a body diagonal move with another body diagonal move, or you end up back where you started. You rapidly discover your only possible moves are: * FFFBFFFB * FFBFFFBF * FBFFFBFF * BFFFBFFF * BFBFBFBF * FBFBFBFB

Now you just count up how many such moves are possible. The first four choices (involving two body diagonal moves) have the same number of solutions, and the last two choices (involving four body diagonal moves) both have the same number of solutions. Thus the total number of solutions is 4 times the number of FFFBFFFB solutions, plus 2 times the number of BFBFBFBF solutions. * FFFBFFFB: your first F has 3 choices, your next F has 2, and your third F has 1 choice. You have only one B choice. From here you only have two choices in your fourth F move, one choice in your fifth F move, and one choice in your sixth F move, since your sixth F move has to line up opposite your starting point so that the second B move returns you to where you started. This is 12 possible solutions. * BFBFBFBF: your first B has only one option, from there you make 3 possible F moves, 1 B move, 2 more possible F moves, 1 B move, 1 F, 1 B, and 1 F. This adds 6 possible solutions.

The total number of solutions is thus 4 times 12 + 2 times 6 = 60, out of 7! permutations, which is 1 in 84 probability.

I don't know why formatting doesn't work. Sorry. It looks great on the screen until I hit post.

jsv 2 years ago
2 years ago

This sure seems like if I knew something about Group Theory this would be way easier. Like the group consists of 8 vertices, with Face Diagonal Moves keeping you in a four-vertex subset of the group, and Body Diagonal Moves taking you to the other four-vertex subsets. I'll think about this some more and come back if something clever hits me.

For now, the dumb answer: a recursive python script that walks through all orderings, identifying those that satisfy the problem statement.

Define eight vertices of a cube, with vertices 0, 1, 2, 3 on the top face, clockwise, and 4, 5, 6, 7 on the bottom face, also clockwise, with 4 under 0. Then the face diagonals of 0 are 2, 5, and 7, while the body diagonal is 6.

def Go(S,l):
    C = [str(int(S[-1])^x) for x in (2,5,6,7)]  # C are vertices you can travel to

    if (len(S) == 8):
        if S[0] in C:        # Make sure your last step connects back to your starting vertex
            l[0] += 1
            print '%2d %s' % (l[0],S)
        else:
            for k in C:
                 if k not in S:
                    Go(S+k,l)
Go('0',[0])

You get 60 paths starting from vertex '0'. Out of 7 factorial possibilities, P = 60 / 7! = 1/84

1 year ago

I too found the answer using a program (in Perl 6, and it draws the cubes as well!). Remember, the four-color theorem was also proved with the help of a computer!

1 year ago

total is 8!

then we have 12 edges:

<hr></hr> <hr></hr> <hr></hr>

combination of numbers placed at each end = 8 * 7 combination of consectutive numbers = 8*2 ( for every number there are 2 options for consective number)

combination so number are not consecutive = 87 - 82 = 40

no of edges = 12

combination so that no edge has consecutive number = 12 *40 = 480

probability = 480/8! = 1/84

Post an answer:

To post an answer, please log in