¿Puede encontrar una matriz $A_{4\times39}$ con elementos de $\{-1,0,1\}$ para que
¿Cómo puedes hacer eso? ¿Es posible generalizar este caso?
Creo que es posible (espero no haberme equivocado, lo cual es fácilmente posible)
He aquí algunas reflexiones: Puedes asumir que la primera línea es 13 1 s entonces 13 0 s y luego 13 -1 s. Llamamos a una columna $i$ -col, si su entrada superior es $i$ . Para los 26 1 / -1 -cols que tiene como máximo $3^3$ opciones para completar. Por lo tanto, necesitas todas las posibles 3tuplas excepto una. Para la 0 -los protocolos se olvidan del signo para el primer no 0 entrada por ahora. A continuación, tiene $9$ opciones a la izquierda. Así que las necesitas todas. Colócalas y juega con los signos hasta que cada fila (2-4) tenga 4 1 y 5 -1 procedente del 0 -cols. La columna que falta para el otro 1 / -1 -cols es $(*,-1,-1,-1)$ De lo contrario, te habrías quedado con dos muchos 1 s. Ahora llene todas las filas restantes completando el 1 -cols y -1 -cols. Continúa intercambiando columnas, hasta que los números sean correctos.
Un consejo útil es que si encuentras una solución, la matriz obtenida al negar una fila sigue siendo una solución. Otra pista: si consideras una columna y su negación como una clase de equivalencia, ¿cuántas clases hay? ¿Cuántas de ellas deben utilizarse realmente? ¿Qué se puede decir de las clases que no se utilizan? ¿Cómo se relaciona esto con la pista sobre las negaciones de las filas?
Sin embargo, la pista clave para este problema está contenida en el enunciado original del problema. Es la pregunta de si la solución puede ser generalizada. Yo recomendaría intentar generalizaciones con columnas más cortas, digamos columnas de longitud $2$ o $3,$ antes de intentar generalizaciones con columnas más largas, e incluso antes de intentar construir el $4\times39$ ejemplo. Tendrás que averiguar cuál será la longitud de la fila en el caso general, utilizando consideraciones como las anteriores. Una vez que tengas eso, debería ser posible hacer los casos de menor tamaño mediante una búsqueda exhaustiva. ¿Puedes basarte en estos resultados para construir ejemplos más grandes?
Añadido: Para que quede claro, mis insinuaciones sugerían una construcción recursiva. Para responder a las preguntas planteadas en mi primer párrafo: para columnas de longitud $\ell,$ hay $\frac{1}{2}(3^\ell-1)$ clases. Cuando $\ell$ es $4,$ es decir $40$ clases. Por lo tanto, si vamos a tener 39 columnas, una clase no se utilizará. Esto sugiere una posible generalización a $\ell\ne4$ y dejamos que $$s(\ell)=\frac{1}{3}\left[\frac{1}{2}(3^\ell-1)-1\right]=\frac{1}{6}(3^\ell-3),$$ que es un número entero. Buscamos matrices de $\ell$ filas y $3s(\ell)$ columnas que satisfagan sus condiciones (1), (2) y (3), y que tengan $s(\ell)$ cada uno de $1,$ $0,$ y $-1$ en cada fila.
Como los dos miembros de cada clase de equivalencia sólo difieren en el signo, el número y la posición de los ceros son independientes del miembro que se elija para representar la clase. Hay $3^\ell$ vectores de longitud $\ell$ con elementos en $\{-1,0,1\},$ compuesto por $\ell\cdot3^\ell$ elementos totales, de los cuales un tercio, o $\ell\cdot3^{\ell-1},$ son cero. Dado que el vector cero, que contiene $\ell$ no se debe utilizar, cualquier conjunto constituido por un representante de cada clase de equivalencia contiene $\frac{1}{2}(\ell\cdot3^{\ell-1}-\ell)=\frac{1}{6}(3^\ell-3)\ell=s(\ell)\ell$ elementos cero. Este es exactamente el número de elementos cero necesarios para satisfacer la condición (4) sobre los elementos de la fila, lo que implica que se utilizan todas las clases de equivalencia que contienen elementos cero. Por lo tanto, una de las clases de equivalencia que contiene sólo $\pm1$ es la clase no utilizada. Como la normalización de las filas es arbitraria, podemos tomar la clase no utilizada como la clase formada por el vector de todos los elementos y su negación.
Resolvamos el $\ell=2$ caso primero. Tenemos $s(\ell)=1.$ Las columnas serán $\pm(1,0)^T,$ $\pm(0,1)^T,$ y $\pm(1,-1)^T.$ Si elegimos los signos $+,$ $-,$ y $-,$ obtenemos la matriz $$M_2=\begin{bmatrix}1 & 0 & -1\\0 & -1 & 1\end{bmatrix},$$ que tiene una $1,$ un $0,$ y una $-1$ en cada fila.
Si hemos construido una matriz $M_\ell,$ que satisfaga las condiciones (1), (2) y (3), y que tenga $s(\ell)$ $1\text{s,}$ $s(\ell)$ $0\text{s,}$ y $s(\ell)$ $-1\text{s}$ en cada fila, entonces el $\ell\times9s(\ell)$ matriz $$\begin{bmatrix}M_\ell & M_\ell & M_\ell\end{bmatrix}$$ tiene $3s(\ell)$ $1\text{s,}$ $3s(\ell)$ $0\text{s,}$ y $3s(\ell)$ $-1\text{s}$ en cada fila. Por supuesto, ahora tenemos tres copias de cada columna, pero anteponiendo a cada copia un elemento diferente, $1,$ $0,$ o $-1,$ obtenemos un $(\ell+1)\times9s(\ell)$ matriz con columnas distintas y $3s(\ell)$ $1\text{s,}$ $3s(\ell)$ $0\text{s,}$ y $3s(\ell)$ $-1\text{s}$ en cada fila. Como $s(\ell+1)=3s(\ell)+1,$ para construir $M_{\ell+1}$ necesitamos un $1,$ $0,$ y $-1$ en cada fila. Una construcción de $M_{\ell+1}$ se puede conseguir de la siguiente manera: $$M_{\ell+1}=\left[\begin{array}{c|ccc|c|ccc|c|ccc}1 & 1 & \ldots & 1 & 0 & 0 & \ldots & 0 & -1 & -1 & \ldots & -1\\ \hline 0 & & & & -1 & & & & 1 & & & \\ \vdots & & M_\ell & & \vdots & & M_\ell & & \vdots & & M_\ell & \\ 0 & & & & -1 & & & & 1 & & & \end{array}\right].$$ Desde $M_\ell$ no contiene la columna de todos los ceros, la columna de todos los uno o la columna de todos los menos uno, ni tampoco $M_{\ell+1}.$ Desde $M_\ell$ no contiene columnas duplicadas, ni columnas que sean negaciones unas de otras, ni tampoco $M_{\ell+1}.$ Por tanto, se cumplen todas las condiciones. Aquí hay una imagen: 
He aquí un enfoque humano y libre de chanchullos.
Como el orden no puede ser de la materia, llenamos las filas superiores con 13 de cada uno en orden dando ( $-1 \times 13, 0 \times 13, 1 \times 13$ ) y las llamamos columnas-bloque A,B,C. Del mismo modo, si rellenamos la siguiente fila con ( $-1 \times 13, 1 \times 13, 0 \times 13$ ) (bloque-columna D,E,F), ya habríamos resuelto el problema por completo si se pidiera un $ (4) \times (3 \times 9) $ porque cada bloque-columna puede llenarse con el $9$ permutaciones que quedan para las dos filas restantes, mientras se satisfacen todas las condiciones automáticamente debido a nuestra elección de raíces y permutaciones que equilibran los dígitos por igual.
Pero esto ya es un buen resultado parcial, así que hacemos justo eso, excepto que dividimos D,E,F en (D,D'),(E,E'),(F,F') con D,E,F de tamaño $9$ columnas cada uno, y los otros de tamaño $13-9=4$ cada uno. Todavía tenemos que determinar cómo se llenan D',E',F'. Para evitar conflictos de negación, elegimos (para las segundas filas todavía) ( $1 \times 4, 0 \times 4, -1 \times 4$ ).
Hemos terminado si llenamos las dos últimas filas de D',E',F'. Se garantiza que E' está libre de conflictos (excepto $(0,0,0,0)$ ), por lo que lo utilizamos como "recolector de restos". En el caso de D',F', al ser sus raíces negativas, simplemente decidimos que el resto de las dos columnas sean iguales, y esto sí es posible. Necesitamos que cada fila utilice cuatro de cada dígito (para sumar $13$ ). Así que dividimos $-1$ dos para cada uno de D' y F', entonces tomamos una $0$ para cada uno y uno $1$ para cada uno, poniendo el resto en E'. Ya hemos terminado.
El resultado es el siguiente:
(Aunque probablemente esto no se generalice fácilmente).
.
Apéndice
Se me ocurrió este procedimiento general. Es muy aburrido y no es realmente elegante; pero se puede utilizar para generalizar la solución.
El enfoque es generar todas las permutaciones (no es mucho pedir, ya que necesitaremos la mitad de ellas de todos modos) en un orden específico. Normalmente generaría las permutaciones en un orden ascendente como este: $$ \pmatrix{-1 \cr -1 \cr -1 \cr -1},\pmatrix{-1 \cr -1 \cr -1 \cr 0},\pmatrix{-1 \cr -1 \cr -1 \cr 1},\pmatrix{-1 \cr -1 \cr 0 \cr -1},\pmatrix{-1 \cr -1 \cr 0 \cr 0},...\pmatrix{1 \cr 1 \cr 1 \cr 1}$$ En este caso, es mejor "intercalar el principio y el final", de modo que cada columna tenga su negativo justo después. Esto sucede automáticamente si procedemos como arriba, pero después de cada columna, añadimos su negativo. $$ \pmatrix{-1 \cr -1 \cr -1 \cr -1},\pmatrix{1 \cr 1 \cr 1 \cr 1},\pmatrix{-1 \cr -1 \cr -1 \cr 0},\pmatrix{1 \cr 1 \cr 1 \cr 0},\pmatrix{-1 \cr -1 \cr -1 \cr 1},\pmatrix{1 \cr 1 \cr 1 \cr -1},...\pmatrix{0 \cr 0 \cr 0 \cr 0}$$ La tarea queda entonces clara: de cada par tenemos que elegir sólo uno hasta llenar la matriz. Para ello, respetando la "restricción de 13 en una fila", simplemente llevamos la cuenta de cuántas opciones permitidas quedan para cada dígito en cada fila, lo que requiere $12=4 \times 3$ números a seguir. El proceso siempre funcionará, nunca tendremos que retroceder y nos aburriremos mucho.
Pero esto al menos permite generalizar la solución: funciona para cualquier matriz de tamaño $(n \times (floor(\dfrac {3^{n-1}} {2}) \times 3)) $ con el $13$ de la condición 4) sustituido por $floor(\dfrac {3^{n-1}} {2})$ .
He traducido las restricciones a un conjunto de expresiones booleanas. A continuación, las he traducido a la forma normal conjuntiva (CNF) y las he resuelto con un solucionador SAT.
El resultado:
Evidentemente, la solución de A.Schulz de "toquetear" ha requerido más inteligencia humana y me ha impresionado profundamente. Bien hecho.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
