Única matriz de ceros y unos

Question

Tenemos una matriz de ceros y unos $a_{ij}$ con 16 filas y 30 columnas. ($a_{ij}=\{0$ o $1\}$).

1. Para cualquier filas $i=m$ : $\sum\limits_{j=1}^{30}a_{mj} \leq 15$.
2. Para cualquier columna $j=n$ : $\sum\limits_{i=1}^{16}a_{in} \geq 8$.
3. Cualquiera de los 2 filas tienen exactamente k ("1") en la misma columna.

k = ? Utilizando la fuerza bruta, me parece $k=7$. Estoy buscando algo bonito y simple solución matemática de cómo probar esto.

Answer 1

Tenemos $\binom{16}{2}=120$ diferentes pares de raws. Cada uno de 30 columna 8, por lo que una columna se utilizará en $\binom{8}{2}=28$ pares. Así que tenemos nuestra respuesta $120\cdot k = 28 \cdot 30 \ \Rightarrow \ k=7.$

El uso de la matriz de

$$ A= \left( \begin{array}{cccccc} 1 & 0 & 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 1 & 1 & 0 & 0 & 1 \end{array} \right) $$

podemos construir la matriz de

$$ A_1=\left( \begin{array}{cccccccccccccc} 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 \end{array} \right) $$

Y ejemplo de matriz $A_2$

$$ \scriptsize \left( \begin{array}{cccccccccccccccccccccccccccccc} 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 \end{array} \right) $$

Upd Un aviso. Podemos colocar 2 en 4 posiciones por $\binom{4}{2}=6$ diferentes maneras y esto nos da: $(1,1,0,0); (0,0,1,1);(1,0,0,1);(0,1,1,0);(1,0,1,0);(0,1,0,1)$. Eso es lo que obtenemos la matriz de $A$$k=1$. Si podemos cambiar las pares de columnas con los números impares columnas obtenemos la matriz $A^r$. Deje $a_4=(1,1,1,1); b_4=(0,0,0,0)$. A continuación, con $k=3$.

$$ A_1=\left( \begin{array}{cccc} A & A & a_4 & b_4 \\ A & A^r & b_4 & a_4 \end{array} \right) $$

Y con $k=7$

$$ A_2=\left( \begin{array}{cccc} A_1 & A_1 & a_8 & b_8 \\ A_1 & A_1^r & b_8 & a_8 \end{array} \right) $$

Y con $k=15$

$$ A_3=\left( \begin{array}{cccc} A_2 & A_2 & a_{16} & b_{16} \\ A_2 & A_2^r & b_{16} & a_{16} \end{array} \right) $$

y así sucesivamente...

Answer 2

He estado pensando acerca de tu pregunta acerca de una combinatoria camino para la construcción de la matriz. A continuación se muestra un diagrama para que me ayude a explicar lo que hice, lo que representa el 1 como cajas y el 0 como un espacio vacío.

Usted sabe que usted va a terminar con exactamente quince 1 en cada fila y exactamente ocho 1 en cada columna. No importa el orden de las filas y columnas se encuentran, por lo tanto, sin pérdida de generalidad podemos reunir el 1 en la primera fila, a la izquierda (es decir, $a_{1j}=1$ si y sólo si $j \leq 15$). Usted sabe que usted desea que la segunda fila para compartir exactamente 7 1 con la primera, así que, de nuevo sin pérdida de generalidad podemos dejar $a_{2j}=1$$j=1,\ldots,7$. Debemos tener 0 para el resto de los espacios debajo de la primera fila de la 1, así que los otros ocho 1 vaya a la derecha.

Ahora, se convierte en útil para notar la simetría de la matriz que estamos tratando de hacer. Estamos también haciendo una matriz con exactamente quince 0 en cada fila y ocho 0 en cada columna, y mediante la recopilación de la 1 a la izquierda, estamos reuniendo el 0 a la derecha. Por lo tanto, cualquier fila que tomamos debe ser capaz de ser simétrica en el "espacio negativo", como un artista podría decir - en otras palabras, podríamos invertir el orden de la fila, interruptor de la 1 y 0, y obtener la misma cosa de nuevo.

Yo continuaba de esta manera, tratando de poner la mayor cantidad de 1 en la izquierda como pude. Porque necesitamos de 15 a 1 en una fila, no podía traer 5 en la izquierda, mientras que el mantenimiento de la simetría. Así me encontré dos filas con 3 a la izquierda. Sabiendo que la mitad superior de las columnas debe añadir a 4 (de nuevo por simetría), las filas 5 a 8 eran obligados a rellenar como se ilustra. Después de la fila 8, yo simplemente reflejaba la mitad superior de las columnas en la mitad inferior, entonces se invierte el 1 y 0 en la mitad inferior de cada columna para exigir que los acuerdos eran únicas.