9
$\begingroup$

Assign one number from 1 to 12 to each edge of a cube (without repetition) such that the sum of the numbers assigned to the edges of any face of the cube is the same.

I tried a bunch of equations but I always ended with more variables than number of equations. So I figured this isn't really a simultaneous equations question.

I pondered if Permutations/Combinations would help. Couldn't figure out much there either.

The only solution I could think of was brute-force (a.k.a trial and error). Or to do it in a slightly manner I thought I could use a backtracking algorithm (http://en.wikipedia.org/wiki/Backtracking). Is that the best way or is my math really rusty?

$\endgroup$
7
  • 3
    $\begingroup$ The sum on each face has to be $26$. Did you know that? Also, simultaneous equations isn't a good way to go about this, since it's difficult to encode the fact that the numbers are supposed to be distinct integers into the equations. $\endgroup$
    – Arthur
    Aug 23, 2014 at 12:59
  • $\begingroup$ @Arthur Can you give a source? That sounds very interesting. $\endgroup$
    – Jam
    Aug 23, 2014 at 13:10
  • 3
    $\begingroup$ If you add all the sums for the six faces, then you get the same result as when you add the number from each edge twice (each edge is counted from two faces). The sum of all integers from $1$ to $12$ is $78$, so the sum of the six faces is $2\cdot78=156$. But the faces are all supposed to be equal, so each of them must be $156/6=26$. $\endgroup$
    – Arthur
    Aug 23, 2014 at 13:18
  • $\begingroup$ @Arthur Great insight. I did not know about that sum being 26. Thank you very much for that. So after this is it like filling up the boxes of a Sudoku puzzle such that the sum comes up to 26 or is there a subsequent trick again? $\endgroup$
    – brahmana
    Aug 23, 2014 at 13:23
  • $\begingroup$ have you thought about the permissible combinations of odd and even? $\endgroup$ Aug 23, 2014 at 13:31

2 Answers 2

9
$\begingroup$

I found this not hard to solve with a pen and a piece of paper towel, so I suspect that it's rather unconstrained and there are many solutions. Later on I may write a program to generate all possible solutions and count them, but for now here's what I did to find a single solution. (Addendum: I did eventually write the program; see the comment below.)

The first step, as already described in the comments, is to find out what the sum of the numbers on a face must be. Let $F$ be the sum of the four edges of a face. The total of all six faces is $6F$. But this counts each edge twice, and the sum of the 12 edges is $1+2+\cdots+12 = 78$, so $6F = 2\cdot 78$, and $$F=26.$$

(Consider a related problem: Arrange the numbers $1,\ldots,12$ in a $3\times 4$ array so that the numbers in each row have the same sum and the numbers in each column have the same sum. There are 4 columns, whose sums together add up to $1+2+\cdots+12 =78$, so for each to have the same sum, each one must sum to $\frac{78}4$. This is impossible, so we know right away that there is no solution.)

With $F=26$, it's natural to consider the numbers in pairs $1–12, 2–11, \ldots, 6–7$ where the pairs always add up to $13$. If we could arrange that each face had exactly two pairs, we would win. Also, we might imagine that the numbers are divided into small numbers $1\ldots 6$ and large numbers $7\ldots 12$. Maybe we can find a solution by matching small numbers with large numbers. To that end, let's arrange $1,12,2,11$ around the middle of the cube, like this:

cube with 1,12,2,11 around the middle

This drawing is too complicated and not compact enough. If we could find a compact representation of the cube that still shows the relationships between the edges and the faces. it would be quicker and simpler to investigate different arrangements of numbers. So suppose the edges of the cube are labeled like this:

cube with 12 letter labels on edges

From now on we'll write this cube like this:

$$\def\r#1{\color{maroon}{#1}}\begin{array}{cccccccc} & \r E && \r F && \r G && \r H\\\r A && \r B && \r C && \r D \\& \r I && \r J && \r K && \r L \\ \end{array}$$

Five of the six faces are easily visible in this display. Three of the middle faces are $AEBI, BFCJ, CGDK$. The fourth wraps around from the right end to the left: $DHAL$. The last two faces are the top and bottom and are $EFGH$ and $IJKL$, which are easy to see in the diagram.

Our assignment of $1,12,2,11$ from before is now:

$$\def\bl#1{\color{blue}{#1}} \begin{array}{cccccccc} & \r E && \r F && \r G && \r H\\\bl1 && \bl{12} && \bl2 && \bl{11} \\& \r I && \r J && \r K && \r L \\ \end{array}$$

The four side faces have so far been assigned edges that total 13, 14, 13, and 12 respectively. We have remaining the four small numbers $3,4,5,6$ and the four large numbers $7,8,9,10$. Since $E$ and $I$ must total 13, let's assign them $6$ and $7$ and see what happens next:

$$\begin{array}{cccccccc} & \bl6 && \r F && \r G && \r H\\1 && 12 && 2 && 11 \\& \bl7 && \r J && \r K && \r L \\ \end{array}$$

Now we need to assign $F$ and $J$, which must add to 12. We have left $3,4,5,8,9,10$. We could use $3,9$ or $4,8$. Let's try $3,9$. (Let's call this decision “$\star$”; it turns out to be wrong, so we'll come back to it later.) It doesn't really matter which one we put on top, since we can switch them later without affecting any of the totals except the top and bottom face. But since we put the small number $6$ on the top face before, let's put the large number $9$ on top this time, to try to keep the top and bottom faces balanced:

$$\begin{array}{cccccccc} & 6 && \bl9 && \r G && \r H\\1 && 12 && 2 && 11 \\& 7 && \bl3 && \r K && \r L \\ \end{array}$$

Now we want to assign $G$ and $K$. We have $G+2+K+11 = 26$, so $G+K= 13$, and the unused numbers are $4,5,8,10$. The only pair we can still use is $5,8$. So let's assign those:

$$\begin{array}{cccccccc} & 6 && 9 && \bl5 && \r H\\1 && 12 && 2 && 11 \\& 7 && 3 && \bl8 && \r L \\ \end{array}$$

Finally, the last two numbers are $4$ and $10$, which combine with the $11$ and $1$ in the $11,L,1,H$ face to make 26. Since we put the small number $5$ on top last time, let's put the large number $10$ on top this time:

$$\begin{array}{cccccccc} & 6 && 9 && 5 && \bl{10}\\1 && 12 && 2 && 11 \\& 7 && 3 && 8 && \bl4 \\ \end{array}$$

Now the four faces around the middle all add up to 26, but the top face is $6+9+5+10 = 30$ and the bottom face is $7+3+8+4 = 22$. Let's call this a “deficit” of 8, the amount by which the bottom face falls short of the amount of the top face. We want a deficit of 0.

We can change the deficit by swapping numbers between the top and bottom. The sides faces all add to 26 so we don't want to change them. But if we swap a top number $t$ with the corresponding bottom number $b$ on the same side face, the deficit will decrease by $t-b$, and the totals on all four side faces will remain as they were. The top-bottom pairs are $6–7, 9–3, 5–8, $ and $10–4$. These contribute $-1, +6, -3, $ and $+6$ to the deficit, respectively, for a total of $+8$. We can change the sign of each contribution from $+$ to $-$ or vice versa, and we want the total deficit to be 0. This is evidently impossible (to see this, just consider whether the 6es should have the same sign or opposite signs; neither works), so we are in a blind alley.

Backing up to the last choice we had, $\star$, we found that adding $3,9$ at that point failed. So let's add $4,8$ instead, obtaining:

$$\begin{array}{cccccccc} & 6 && \bl8 && \r G && \r H\\1 && 12 && 2 && 11 \\& 7 && \bl4 && \r K && \r L \\ \end{array}$$

Then $G+K= 13$ and we have only $3 ,5, 9, 10$, so we take $G,K =3,10$:

$$\begin{array}{cccccccc} & 6 && 8 && \bl3 && \r H\\1 && 12 && 2 && 11 \\& 7 && 4 && \bl{10} && \r L \\ \end{array}$$

and then $5,9$ go in last:

$$\begin{array}{cccccccc} & 6 && 8 && 3 && \bl5\\1 && 12 && 2 && 11 \\& 7 && 4 && 10 && \bl9 \\ \end{array}$$

This time the top totals $6+8+3+5= 22$ and the bottom $7+4+10+9 = 30$, so the bottom has a surplus of $8$. The top-bottom pairs contribute surpluses of $+1, -4, +7, +4$, respectively. We want to switch the signs on these so that they add up to 0. Clearly switching the $+4$ to $-4$ will work, so we swap the positions of $5$ and $9$:

$$\begin{array}{cccccccc} & 6 && 8 && 3 && \bl9\\1 && 12 && 2 && 11 \\& 7 && 4 && 10 && \bl5 \\ \end{array}$$

which is a solution:

solution as above

$\endgroup$
6
  • 1
    $\begingroup$ +1 for the stream-of-consciousness presentation and all the nice pictures. $\endgroup$
    – TonyK
    Aug 23, 2014 at 16:42
  • 1
    $\begingroup$ Addendum: Computer search quickly finds 80 solutions with $A=1$. There are 4 symmetries of the cube that preserve the position of this edge (generated by a vertical flip and a flip across the $A–C$ plane), so of these 80 solutions, only 20 are really different. A list of solution is at github.com/mjdominus/perl-misc/blob/master/search/cubes; the source code is github.com/mjdominus/perl-misc/blob/master/search/cube.pl and the library it uses is github.com/mjdominus/perl-misc/blob/master/search/Search.pm $\endgroup$
    – MJD
    Aug 23, 2014 at 17:41
  • $\begingroup$ +1 Very interesting work. Could you maybe post the initial segment of the solution sequence to make it possible to verify the correctness of additional implementations (obviously not using Perl since we have an implementation already). $\endgroup$ Aug 23, 2014 at 19:54
  • $\begingroup$ @MarkoRiedel I'm sorry, I don't understand what you mean by “initial segment of the solution sequence” that isn't covered by the link at github.com/mjdominus/perl-misc/blob/master/search/cubes that I've already posted. $\endgroup$
    – MJD
    Aug 23, 2014 at 20:07
  • $\begingroup$ Ok, so this indeed requires backtracking, no fancy well known Math formulae here. Using the deficit between top and bottom faces as the key for invalidating a partial solution was neat. @MJD Awesome explanation with kick ass illustration. Absolutely loved it. Thank you. $\endgroup$
    – brahmana
    Aug 24, 2014 at 4:55
1
$\begingroup$

What follows uses the notation from MJDs excellent contribution. Here is an implementation in C by way of Rosetta-Stone like enrichment.

This computes all possible assignments even though each of these inhabits an orbit of $24$ assignments that can be obtained from another by a rotation ($3\times 3$ rotations about an axis through the midpoints of opposite faces, $4\times 2$ rotations about an axis passing through opposite vertices and $6\times 1$ flips about an axis passing through the midpoints of opposite edges, for a total of $9+8+6+1=24$, including the identity.)

This is the C code which is a fast and compact solution. Compiled with GCC 4.8.3.

#include <stdio.h>
#include <stdlib.h>

void search(int sofar, int *assigns, int *seen, 
            char **faces, int sum, int *cref)
{
  if(sofar == 12){
    char *lines[3] = { "EFGH", "ABCD", "IJKL" };

    int pos;
    for(pos=0; pos<3; pos++){
      if(pos != 1){ printf("   "); };

      int idx;
      for(idx=0; idx<4; idx++){
        printf("%02d   ", assigns[lines[pos][idx]-'A']);
      }
      printf("\n");
    }

    printf("\n");

    (*cref)++;
    return;
  }

  int nxt;
  for(nxt=1; nxt<=12; nxt++){
    if(!(seen[nxt-1])){
      assigns[sofar] = nxt;
      seen[nxt-1] = 1;

      int no_admit = 0;

      int fidx;
      for(fidx=0; fidx<6; fidx++){
        int empty = 0, sval = 0, edge;

        for(edge=0; edge<4; edge++){
          int ent = assigns[faces[fidx][edge]-'A'];
          if(ent == -1){
            empty++;
          }
          else{
            sval += ent;
          }
        }

        if((empty==0 && sval != sum) ||
           (empty>0 && sval>=sum)){
          no_admit = 1;
          break;
        }
      }

      if(!no_admit){
        search(sofar+1, assigns, seen, faces, sum, cref);
      }

      seen[nxt-1] = 0;
      assigns[sofar] = -1;
    }
  }
}

int main(int argc, char **argv)
{
  char *faces[6] = {
    "AEBI", "BFCJ", "CGDK",
    "DHAL", "EFGH", "IJKL"
  };

  int assigns[12];
  int seen[12];

  int pos;
  for(pos=0; pos<12; pos++){
    assigns[pos] = -1;
    seen[pos] = 0;
  }

  int sum = 12*13/2/3; int count = 0;

  search(0, assigns, seen, faces, sum, &count);
  fprintf(stderr, "%d results\n", count);

  return 0;
}

The intial solution segment is this (observe that this is the same output as what was posted by MJD):

   10   06   02   08
01   04   09   12
   11   07   03   05

   10   08   02   06
01   04   09   12
   11   05   03   07

   11   05   03   07
01   04   09   12
   10   08   02   06

   11   07   03   05
01   04   09   12
   10   06   02   08

   09   07   02   08
01   04   10   11
   12   05   03   06

   12   05   03   06
01   04   10   11
   09   07   02   08

   09   06   03   08
01   04   11   10
   12   05   02   07

   12   05   02   07
01   04   11   10
   09   06   03   08

   09   03   04   10
01   05   12   08
   11   06   02   07

   09   06   04   07
01   05   12   08
   11   03   02   10

Here are some solutions from the middle of the list.

   09   07   04   06
05   01   08   12
   11   10   02   03

   09   10   04   03
05   01   08   12
   11   07   02   06

   11   07   02   06
05   01   08   12
   09   10   04   03

   11   10   02   03
05   01   08   12
   09   07   04   06

   09   06   03   08
05   02   07   12
   10   11   04   01

   10   11   04   01
05   02   07   12
   09   06   03   08

   07   06   04   09
05   02   08   11
   12   10   03   01

   09   04   06   07
05   02   08   11
   10   12   01   03

   10   12   01   03
05   02   08   11
   09   04   06   07

   12   10   03   01
05   02   08   11
   07   06   04   09

The timings for these were

$ time ./ce > /dev/null
960 results

real    0m3.820s
user    0m3.681s
sys     0m0.030s
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .