Sumas heterogéneas

Queremos llenar una matriz de NxN casillas de lado con números enteros positivos (no necesariamente distintos) de manera que se cumplan las dos siguientes condiciones:

  • Todas las filas y columnas de la matriz tengan sumas distintas
  • La mayor de tales sumas sea lo menor posible

¿Hay alguna manera de lograr esto para cualquier N que no implique una búsqueda por fuerza bruta?

marcos Sábado 09 Febrero 2013 - 8:30 pm | | acertijos, matemática

tres comentarios

Carlos Luna

Asumo que se puede usar el 0, en caso contrario hay que sumar una unidad a todos los números y ajustar un poco lo dicho.

Si todas las sumas deben de ser diferentes y hay que minimizar la mayor de ellas, lo mejor que se puede conseguir es una matriz en la que las 2N sumas de sus filas y sus columnas formen el conjunto de números: {0,1,2,…,2N-1}

No he conseguido tal cosa pero he conseguido una matriz cuya suma máxima es, exactamente 2N. Como su estructura es muy sencilla lo mejor será que la ilustre con dos ejemplos:

Caso N par (ejemplo con N=8)

0___1___1___1___1___1___1___1__=___7
0___0___0___0___0___0___0__13__=__13
0___0___0___0___0___0__11___0__=__11
0___0___0___0___0___9___0___0__=___9
0___0___0___0__15___0___0___0__=__15
0___0___0___5___0___0___0___0__=___5
0___0___3___0___0___0___0___0__=___3
0___1___0___0___0___0___0___0__=___1
=___=___=___=___=___=___=___=
0___2___4___6__16__10__12__14

Caso N impar (ejemplo con N=7)

0___1___1___1___1___1___1___=___6
0___0___0___0___0___0__11___=__11
0___0___0___0___0___9___0___=___9
0___0___0___0___7___0___0___=___7
0___0___0__13___0___0___0___=__13
0___0___3___0___0___0___0___=___3
0___1___0___0___0___0___0___=___1
=___=___=___=___=___=___=
0___2___4__14___8__10__12

La idea básica es llenar de 1’s la primera fila (exceptuando la primera columan en la que va un 0) y luego añadir números impares en una diagonal menor. Este esquema “casi” funciona (nos da, de hecho, una matriz que contiene los números números bajos a costa de permitir que se repita uno de ellos!)

Como el problema proviene de que la suma de la primera fila estará repetida en alguna otra fila o columna (dependiendo de si N es par o impar) la solución pasa por arreglar la suma de esa otra fila/columna de la manera menos dañina posible.

Llegados a este punto la verdad es que me he cansado de pensar, pero parece claro que o bien hay una manera sencilla de arreglar la matriz para conseguir alcanzar el óptimo (una matriz cuya suma máxima sea 2N-1 en vez de 2N) o bien debería ser sencillo demostrar que tal matriz no existe.

Suerte con ello!

Carlos Luna, (URL) - 03-03-’13 18:59
Marcos

¡Gracias Carlos por el análisis!

Marcos, - 07-03-’13 08:07
luisito

La construccion de Carlos tiene que ser optima para N impar. Si sumamos todas las filas y todas las columnas, estariamos sumando todos los numeros de la matriz dos veces, asi que tiene que dar par. Si N es impar, la suma 0+1+2+…+(2N-1) da impar, asi que no se podria.

Para N par me parece que se deberia poder armar una matriz con bloquecitos de 2×2 en la diagonal. Por ejemplo para N=8
0___1___0___0___0___0___0___0
0___2___0___0___0___0___0___0
0___0___2___3___0___0___0___0
0___0___2___4___0___0___0___0
0___0___0___0___4___5___0___0
0___0___0___0___4___6___0___0
0___0___0___0___0___0___6___7
0___0___0___0___0___0___6___8

luisito, - 09-03-’13 16:37
(optional field)
(optional field)

La moderación de comentarios está activa en este sitio web. Esto significa que sus comentarios no serán visibles en la página hasta que hayan sido aprobados por un editor.

¿Recordar información personal?
Letra pequeña: Todas las etiquetas html excepto <b> e <i> serán eliminadas de su comentario. Puede introducir enlaces simplemente escribiendo la url o direcciones de e-mail.