Fall 2015, problem 1

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!

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.

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.

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.

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.

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}$

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}$

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

The total no. of possible ways for arrainging the 8 numbers on a vertices of a cube is 8! (means 8 76 54 32*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.

											

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

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

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).

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 F 1, 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.

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

total is 8!

then we have 12 edges:

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 = 8 7 - 82 = 40

no of edges = 12

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

probability = 480/8! = 1/84