Maximizar el primer sumas de dinero en una tabla

Question

Las entradas de un $3×3$ tabla son enteros de$1$$9$, y cada número aparece exactamente una vez. Considere la posibilidad de la fila, columna y diagonal sumas de números en la tabla. Encontrar el máximo número de estos ocho sumas que pueden ser números primos. ¿Cómo puedo empezar con el problema? No es una combinatoria problema, aunque lo parece.

Answer 1

Solución de fuerza bruta:

a(n)=my(v=numtoperm(9,n));vecsum(apply(isprime,[v[1]+v[2]+v[3],v[4]+v[5]+v[6],v[7]+v[8]+v[9],v[1]+v[4]+v[7],v[2]+v[5]+v[8],v[3]+v[6]+v[9],v[1]+v[5]+v[9],v[3]+v[5]+v[7]]))
r=0;for(n=0,9!-1,t=a(n);if(t>r,r=t;print(r" "numtoperm(9,n))))

Esto se lleva a la mitad de un segundo en mi máquina.

Hay 96 soluciones (además de sus reflexiones y rotaciones) para que 7 de las sumas son los principales. Estos son: $$ \left\{\begin{array}{ccc} 1&2&4\\ 5&8&6\\ 7&3&9 \end{array},\qquad \begin{array}{ccc} 1&2&4\\ 5&8&6\\ 7&9&3 \end{array},\qquad \begin{array}{ccc} 1&2&8\\ 7&6&4\\ 3&9&5 \end{array},\qquad \begin{array}{ccc} 1&2&8\\ 7&6&4\\ 9&3&5 \end{array},\qquad \begin{array}{ccc} 1&3&9\\ 5&2&6\\ 7&8&4 \end{array},\qquad \begin{array}{ccc} 1&3&9\\ 5&8&6\\ 7&2&4 \end{array},\qquad \begin{array}{ccc} 1&3&9\\ 7&4&2\\ 5&6&8 \end{array},\qquad \begin{array}{ccc} 1&3&9\\ 7&4&8\\ 5&6&2 \end{array},\qquad \begin{array}{ccc} 1&4&6\\ 7&2&8\\ 3&5&9 \end{array},\qquad \begin{array}{ccc} 1&4&6\\ 7&2&8\\ 9&5&3 \end{array},\qquad \begin{array}{ccc} 1&4&6\\ 7&8&2\\ 3&5&9 \end{array},\qquad \begin{array}{ccc} 1&4&6\\ 7&8&2\\ 9&5&3 \end{array},\qquad \begin{array}{ccc} 1&5&7\\ 8&2&3\\ 4&6&9 \end{array},\qquad \begin{array}{ccc} 1&5&7\\ 8&2&9\\ 4&6&3 \end{array},\qquad \begin{array}{ccc} 1&5&7\\ 9&2&8\\ 3&6&4 \end{array},\qquad \begin{array}{ccc} 1&5&7\\ 9&8&2\\ 3&6&4 \end{array},\qquad \begin{array}{ccc} 1&7&3\\ 8&6&9\\ 2&4&5 \end{array},\qquad \begin{array}{ccc} 1&7&5\\ 9&4&6\\ 3&2&8 \end{array},\qquad \begin{array}{ccc} 1&7&5\\ 9&4&6\\ 3&8&2 \end{array},\qquad \begin{array}{ccc} 1&7&9\\ 8&6&3\\ 2&4&5 \end{array},\qquad \begin{array}{ccc} 2&1&4\\ 3&5&9\\ 8&7&6 \end{array},\qquad \begin{array}{ccc} 2&1&4\\ 3&7&5\\ 6&9&8 \end{array},\qquad \begin{array}{ccc} 2&1&4\\ 3&7&9\\ 6&5&8 \end{array},\qquad \begin{array}{ccc} 2&1&4\\ 3&7&9\\ 8&5&6 \end{array},\qquad \begin{array}{ccc} 2&1&4\\ 3&9&5\\ 6&7&8 \end{array},\qquad \begin{array}{ccc} 2&1&4\\ 3&9&7\\ 6&5&8 \end{array},\qquad \begin{array}{ccc} 2&1&4\\ 5&3&7\\ 6&9&8 \end{array},\qquad \begin{array}{ccc} 2&1&4\\ 5&9&7\\ 6&3&8 \end{array},\qquad \begin{array}{ccc} 2&1&4\\ 9&3&5\\ 6&7&8 \end{array},\qquad \begin{array}{ccc} 2&1&4\\ 9&3&7\\ 6&5&8 \end{array},\qquad \begin{array}{ccc} 2&1&4\\ 9&5&3\\ 8&7&6 \end{array},\qquad \begin{array}{ccc} 2&1&4\\ 9&7&3\\ 6&5&8 \end{array},\qquad \begin{array}{ccc} 2&1&4\\ 9&7&3\\ 8&5&6 \end{array},\qquad \begin{array}{ccc} 2&1&4\\ 9&7&5\\ 6&3&8 \end{array},\qquad \begin{array}{ccc} 2&1&6\\ 3&5&9\\ 8&7&4 \end{array},\qquad \begin{array}{ccc} 2&1&6\\ 5&3&9\\ 4&7&8 \end{array},\qquad \begin{array}{ccc} 2&1&6\\ 5&9&3\\ 4&7&8 \end{array},\qquad \begin{array}{ccc} 2&1&6\\ 9&5&3\\ 8&7&4 \end{array},\qquad \begin{array}{ccc} 2&1&8\\ 3&5&9\\ 4&7&6 \end{array},\qquad \begin{array}{ccc} 2&1&8\\ 3&5&9\\ 6&7&4 \end{array},\qquad \begin{array}{ccc} 2&1&8\\ 3&9&5\\ 6&7&4 \end{array},\qquad \begin{array}{ccc} 2&1&8\\ 5&3&9\\ 4&7&6 \end{array},\qquad \begin{array}{ccc} 2&1&8\\ 5&9&3\\ 4&7&6 \end{array},\qquad \begin{array}{ccc} 2&1&8\\ 9&3&5\\ 6&7&4 \end{array},\qquad \begin{array}{ccc} 2&1&8\\ 9&5&3\\ 4&7&6 \end{array},\qquad \begin{array}{ccc} 2&1&8\\ 9&5&3\\ 6&7&4 \end{array},\qquad \begin{array}{ccc} 2&3&4\\ 5&1&7\\ 6&9&8 \end{array},\qquad \begin{array}{ccc} 2&3&4\\ 5&7&1\\ 6&9&8 \end{array},\qquad \begin{array}{ccc} 2&3&4\\ 7&5&1\\ 8&9&6 \end{array},\qquad \begin{array}{ccc} 2&3&6\\ 5&1&9\\ 4&7&8 \end{array},\qquad \begin{array}{ccc} 2&3&6\\ 5&7&9\\ 4&1&8 \end{array},\qquad \begin{array}{ccc} 2&3&6\\ 7&1&5\\ 4&9&8 \end{array},\qquad \begin{array}{ccc} 2&3&6\\ 7&1&9\\ 4&5&8 \end{array},\qquad \begin{array}{ccc} 2&3&6\\ 7&5&1\\ 8&9&4 \end{array},\qquad \begin{array}{ccc} 2&3&6\\ 7&9&1\\ 4&5&8 \end{array},\qquad \begin{array}{ccc} 2&3&6\\ 7&9&1\\ 8&5&4 \end{array},\qquad \begin{array}{ccc} 2&3&6\\ 7&9&5\\ 4&1&8 \end{array},\qquad \begin{array}{ccc} 2&3&8\\ 5&1&7\\ 6&9&4 \end{array},\qquad \begin{array}{ccc} 2&3&8\\ 5&7&1\\ 6&9&4 \end{array},\qquad \begin{array}{ccc} 2&3&8\\ 7&1&5\\ 4&9&6 \end{array},\qquad \begin{array}{ccc} 2&3&8\\ 7&5&1\\ 4&9&6 \end{array},\qquad \begin{array}{ccc} 2&3&8\\ 7&5&1\\ 6&9&4 \end{array},\qquad \begin{array}{ccc} 2&4&5\\ 8&6&3\\ 7&1&9 \end{array},\qquad \begin{array}{ccc} 2&4&5\\ 8&6&9\\ 7&1&3 \end{array},\qquad \begin{array}{ccc} 2&5&4\\ 7&3&1\\ 6&9&8 \end{array},\qquad \begin{array}{ccc} 2&5&4\\ 7&3&1\\ 8&9&6 \end{array},\qquad \begin{array}{ccc} 2&5&4\\ 7&9&1\\ 6&3&8 \end{array},\qquad \begin{array}{ccc} 2&5&4\\ 7&9&1\\ 8&3&6 \end{array},\qquad \begin{array}{ccc} 2&5&4\\ 9&1&7\\ 6&3&8 \end{array},\qquad \begin{array}{ccc} 2&5&4\\ 9&7&1\\ 6&3&8 \end{array},\qquad \begin{array}{ccc} 2&5&6\\ 7&3&9\\ 4&1&8 \end{array},\qquad \begin{array}{ccc} 2&5&6\\ 7&9&3\\ 4&1&8 \end{array},\qquad \begin{array}{ccc} 2&5&6\\ 9&1&3\\ 4&7&8 \end{array},\qquad \begin{array}{ccc} 2&5&6\\ 9&1&3\\ 8&7&4 \end{array},\qquad \begin{array}{ccc} 2&5&6\\ 9&7&3\\ 4&1&8 \end{array},\qquad \begin{array}{ccc} 2&5&6\\ 9&7&3\\ 8&1&4 \end{array},\qquad \begin{array}{ccc} 2&6&5\\ 8&4&1\\ 3&9&7 \end{array},\qquad \begin{array}{ccc} 2&6&5\\ 8&4&1\\ 9&3&7 \end{array},\qquad \begin{array}{ccc} 2&7&4\\ 9&1&3\\ 6&5&8 \end{array},\qquad \begin{array}{ccc} 2&7&4\\ 9&1&3\\ 8&5&6 \end{array},\qquad \begin{array}{ccc} 2&7&4\\ 9&1&5\\ 6&3&8 \end{array},\qquad \begin{array}{ccc} 2&7&4\\ 9&3&1\\ 6&5&8 \end{array},\qquad \begin{array}{ccc} 2&7&4\\ 9&3&5\\ 6&1&8 \end{array},\qquad \begin{array}{ccc} 2&7&4\\ 9&5&3\\ 8&1&6 \end{array},\qquad \begin{array}{ccc} 2&7&6\\ 9&5&3\\ 8&1&4 \end{array},\qquad \begin{array}{ccc} 2&7&8\\ 9&3&5\\ 6&1&4 \end{array},\qquad \begin{array}{ccc} 2&7&8\\ 9&5&3\\ 4&1&6 \end{array},\qquad \begin{array}{ccc} 2&7&8\\ 9&5&3\\ 6&1&4 \end{array},\qquad \begin{array}{ccc} 3&1&7\\ 5&2&4\\ 9&8&6 \end{array},\qquad \begin{array}{ccc} 3&1&7\\ 5&8&4\\ 9&2&6 \end{array},\qquad \begin{array}{ccc} 3&1&7\\ 9&6&2\\ 5&4&8 \end{array},\qquad \begin{array}{ccc} 3&2&6\\ 5&8&4\\ 9&1&7 \end{array},\qquad \begin{array}{ccc} 3&2&8\\ 9&4&6\\ 7&1&5 \end{array},\qquad \begin{array}{ccc} 3&5&9\\ 8&2&1\\ 6&4&7 \end{array},\qquad \begin{array}{ccc} 5&1&7\\ 6&4&3\\ 8&2&9 \end{array},\qquad \begin{array}{ccc} 5&3&9\\ 4&6&1\\ 8&2&7 \end{array}\right\} $$

Answer 2

Así podemos establecer un-límite superior y también limitan el espacio de la solución con el siguiente:

Cualquier suma de tres números enteros debe ser >= 6 y <= 7+8+9=24 El único de los números primos entre 6..24 son 7,11,13,17,19,23 es decir, {6k + 1 o 5}

En orden para S >= 6 primo, considere la posibilidad de que sus residuos tanto mod 2,3 y 6 deben necesariamente ser:

• mod 2, S == 1
• mod 3, S == 1 o 2
• mod 6, S == 1 o 5

Luego reescribir:{1..9} b = a-6: B:{-5,-4,-3,-2,-1,0,1,2,3} Entonces será el primer si S == -7,-5,-1,1,5 mod 6

Llamar a los números enteros A = (a_1, a_2... a_9),

• mod 2, Una es de cinco y cuatro ceros
• mod 3, Una es de tres ceros, tres, tres de dos en dos
• mod 6, Una es (1..5,0..3)

Así que, ¿cómo elegir la ubicación de S mod 2 y S mod 3 en el fin de maximizar el número de sumas que son ambos impares (mod 2) y residuo 1 o 2 (mod 3).

• mod 2, podemos hacer que todo 3+3+2 de la diagonal+fila+columna de sumas extraño con el siguiente patrón: una fila y una columna contiene tres números impares, los otros dos filas y columnas de cada uno

.e.g. uno de 3x3 tales arreglos posibles mod-2 es:

0 1 0
1 1 1
0 1 0