Enumerando los bordes de un cubo del 1 al 12 de manera que la suma de los bordes en cualquier cara sea igual.

Question

Asigna un número del 1 al 12 a cada arista de un cubo (sin repetición) de manera que la suma de los números asignados a las aristas de cualquier cara del cubo sea la misma.

Intenté con un montón de ecuaciones pero siempre terminaba con más variables que ecuaciones. Así que pensé que esto realmente no era una pregunta de ecuaciones simultáneas.

Pensé si las Permutaciones/Combinaciones podrían ayudar. Tampoco pude averiguar mucho allí.

La única solución que se me ocurrió fue el método de fuerza bruta (también conocido como ensayo y error). O para hacerlo de una manera un poco más ordenada, pensé que podría usar un algoritmo de retroceso (http://en.wikipedia.org/wiki/Backtracking). ¿Es esa la mejor manera o es que mi matemática está realmente oxidada?

Answer 1

Encontré que esto no era difícil de resolver con un bolígrafo y una toalla de papel, así que sospecho que es bastante libre y hay muchas soluciones. Más adelante puedo escribir un programa para generar todas las posibles soluciones y contarlas, pero por ahora aquí está lo que hice para encontrar una única solución. (Adición: Eventualmente escribí el programa; ver el comentario abajo.)

El primer paso, como ya se describió en los comentarios, es averiguar cuál debe ser la suma de los números en una cara. Deje que $F$ sea la suma de los cuatro bordes de una cara. El total de todas las seis caras es $6F$. Pero esto cuenta cada borde dos veces, y la suma de los 12 bordes es $1+2+\cdots+12 = 78$, así que $6F = 2\cdot 78$, y $$F=26.$$

(Considere un problema relacionado: Organice los números $1,\ldots,12$ en una matriz $3\times 4$ de manera que los números en cada fila tengan la misma suma y los números en cada columna tengan la misma suma. Hay 4 columnas, cuyas sumas juntas dan $1+2+\cdots+12 =78$, así que para que cada una tenga la misma suma, cada una debe sumar $\frac{78}4$. Esto es imposible, así que sabemos de inmediato que no hay solución.)

Con $F=26$, es natural considerar los números en pares $1–12, 2–11, \ldots, 6–7$ donde los pares siempre suman $13$. Si pudiéramos organizar que cada cara tuviera exactamente dos pares, ganaríamos. Además, podríamos imaginar que los números se dividen en números pequeños $1\ldots 6$ y números grandes $7\ldots 12$. Tal vez podemos encontrar una solución emparejando números pequeños con números grandes. Con ese objetivo, vamos a organizar $1,12,2,11$ alrededor del centro del cubo, así:

Este dibujo es demasiado complicado y no suficientemente compacto. Si pudiéramos encontrar una representación compacta del cubo que todavía muestre las relaciones entre los bordes y las caras, sería más rápido y simple investigar diferentes disposiciones de números. Supongamos entonces que los bordes del cubo están etiquetados así:

De ahora en adelante escribiremos este cubo así:

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

Cinco de las seis caras son fácilmente visibles en este display. Tres de las caras centrales son $AEBI, BFCJ, CGDK$. La cuarta se enrolla desde el extremo derecho al izquierdo: $DHAL$. Las dos últimas caras son la superior e inferior y son $EFGH$ y $IJKL$, que son fáciles de ver en el diagrama.

Nuestra asignación de $1,12,2,11$ de antes es ahora:

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

Las cuatro caras laterales han sido asignadas con bordes que suman 13, 14, 13, y 12 respectivamente. Nos quedan los cuatro números pequeños $3,4,5,6$ y los cuatro números grandes $7,8,9,10$. Como $E$ e $I$ deben sumar 13, asignémosles $6$ y $7$ y veamos qué sucede a continuación:

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

Ahora necesitamos asignar $F$ y $J$, que deben sumar 12. Nos quedan $3,4,5,8,9,10$. Podríamos usar $3,9$ o $4,8$. Intentemos con $3,9$. (Llamaremos a esta decisión “$\star$”; resulta ser incorrecta, así que volveremos a ella más tarde.) Realmente no importa cuál pongamos en la parte superior, ya que luego podemos intercambiarlos sin afectar ninguna de las sumas excepto la de la cara superior e inferior. Pero como pusimos el número pequeño $6$ en la cara superior antes, pongamos el número grande $9$ arriba esta vez, para intentar mantener equilibradas las caras superior e inferior:

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

Ahora queremos asignar $G$ y $K$. Tenemos $G+2+K+11 = 26$, así que $G+K= 13$, y los números sin usar son $4,5,8,10$. La única pareja que aún podemos usar es $5,8$. Asignémoslos:

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

Finalmente, los dos últimos números son $4$ y $10$, los cuales junto con el $11$ y el $1$ en la cara $11,L,1,H$ suman 26. Como pusimos el número pequeño $5$ arriba la última vez, pongamos el número grande $10$ arriba esta vez:

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

Ahora las cuatro caras alrededor del centro suman todas 26, pero la cara superior es $6+9+5+10 = 30$ y la cara inferior es $7+3+8+4 = 22$. Llamemos a esto un “déficit” de 8, la cantidad por la que la cara inferior cae corta de la cantidad de la cara superior. Queremos un déficit de 0.

Podemos cambiar el déficit intercambiando números entre la parte superior e inferior. Las caras laterales todas suman 26, así que no queremos cambiarlas. Pero si cambiamos un número de la parte superior $t$ con el número correspondiente de la parte inferior $b$ en la misma cara lateral, el déficit disminuirá en $t-b$, y las sumas en las cuatro caras laterales seguirán siendo las mismas. Las parejas de la parte superior-inferior son $6–7, 9–3, 5–8, $ y $10–4$. Estas contribuyen con $-1, +6, -3, $ y $+6$ al déficit, respectivamente, para un total de $+8$. Podemos cambiar el signo de cada contribución de $+$ a $-$ o viceversa, y queremos que el déficit total sea 0. Esto es evidentemente imposible (para ver esto, simplemente considere si los 6 deberían tener el mismo signo o signos opuestos; ninguno funciona), así que estamos en un callejón sin salida.

Volviendo a la última elección que tuvimos, $\star$, descubrimos que agregar $3,9$ en ese punto falló. Así que agreguemos $4,8$ en su lugar, obteniendo:

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

Luego, $G+K= 13$ y solo nos quedan $3 ,5, 9, 10$, así que tomamos $G,K =3,10$:

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

y luego $5,9$ van al final:

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

Esta vez, la suma de la parte superior es $6+8+3+5= 22$ y la parte inferior es $7+4+10+9 = 30$, así que la parte inferior tiene un excedente de 8. Las parejas de la parte superior-inferior contribuyen excedentes de $+1, -4, +7, +4$, respectivamente. Queremos cambiar los signos de estos para que sumen 0. Claramente cambiar el $+4$ a $-4$ funcionará, así que intercambiemos las posiciones de $5$ y $9$:

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

lo cual es una solución:

Answer 2

Lo que sigue utiliza la notación de la excelente contribución de MJD. Aquí hay una implementación en C enriquecida a la manera de Rosetta-Stone.

Esto calcula todas las asignaciones posibles, a pesar de que cada una de estas habita en una órbita de $24$ asignaciones que se pueden obtener de otra mediante una rotación (rotaciones $3\times 3$ alrededor de un eje que pasa por los puntos medios de las caras opuestas, rotaciones $4\times 2$ alrededor de un eje que pasa por vértices opuestos y flips $6\times 1$ alrededor de un eje que pasa por los puntos medios de los bordes opuestos, para un total de $9+8+6+1=24$, incluyendo la identidad.)

Este es el código en C que es una solución rápida y compacta. Compilado con 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 resultados\\n", count);

  return 0;
}

El segmento de solución inicial es este (observa que este es el mismo resultado que lo publicado por 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

Aquí hay algunas soluciones del medio de la lista.

   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

Los tiempos para estos fueron

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

real    0m3.820s
user    0m3.681s
sys     0m0.030s