¿Cómo podemos encontrar el número de 8 por 8 matrices en el que cada entrada es 0 o 1. Además, cada fila y cada columna contiene un número impar de 1's. Gracias por la ayuda.
Respuestas
¿Demasiados anuncios?
Per Hornshøj-Schierbeck
Puntos
4610
Sugerencias:
- Exactamente la mitad de los 8-tuplas de $0/1$s tiene un número impar de unos.
- Puede seleccionar las primeras siete filas entre el lote de los de arriba arbitrariamente. Entonces, las decisiones de la última fila son muy limitadas.
Una forma más corta es determinar de cuántas maneras puede completar arbitrariamente un lleno en $7\times7$ superior izquierdo del bloque en el fin de cumplir con las condiciones prescritas. Para todo el crédito también debe explicar, por qué es esencial que el número de filas y columnas tienen la misma paridad?
user30856
Puntos
11
Sugerencia: El número de formas de fi ll una determinada fila de 8 entradas con $0's$ $1's$ mediante el uso de un número impar de $1's$ es igual al número de subconjuntos de un $8$-element set con un número impar de elementos y la identificación de una determinada fila con el conjunto de etiquetas de 1 a 8 para el que las entradas correspondientes son iguales a 1).
Vamos a encontrar la solución para cualquier $n\times n$ matriz.
Como @Jyrki Lahtonen dijo, la estrategia es seleccionar arbitrariamente el primer $(n-1)$ filas y, a continuación, calcular el $n$-ésima fila.
El número total de combinaciones de cualquiera de las $(n-1)$ filas $2^n$. La mitad de ellos tienen un número impar de $1$'s en ella. Lo que significa que hay $\frac{2^n}{2}=2^{n-1}$ combinaciones posibles para cada uno de los primeros a $(n-1)$ filas.
Una vez que todas estas filas se han determinado, sólo hay una combinación posible para la última fila : para cada elemento de la fila, si el número de $1$ en la columna ya es extraño que poner un $0$, si ni siquiera poner un $1$.
Esto significa que el número total de $n\times n$ matrices de verificación de sus condiciones es:
$$N=\left(2^{n-1}\right)^{n-1}=2^{(n-1)(n-1)}$$
Sin embargo, hay algo que he asumido en esta prueba, que es el hecho de que el último de la fila siempre tendrá un número impar de $1$'s, cualquiera que sea el primero de $(n-1)$ filas.
Vamos a probar esto también:
Denotar $\left\{\begin{array}{cc}x_i && \mbox{the number of 1's in the i-th row} \\ X_p && \mbox{the total number of 1's in the first (n-1) rows} \\ X && \mbox{the total number of 1's in the matrix}\end{array}\right.$
Ha $\displaystyle X_p=\sum_{i=1}^{n-1} x_i$$\displaystyle X=\sum_{i=1}^n x_i=X_p+x_n$.
- Primer caso: $n$ incluso:
Ya que queremos que todos los $x_i$ a un ser extraño, $X$ tiene que ser incluso (como la suma de un número par de números impares).
De la misma manera, ya que $(n-1)$ es impar, $X_p$ tiene que ser impar.
Ahora desde $X=X_p+x_n$ y desde $X$ es incluso y $X_p$ es impar, $x_n$ tiene que ser impar. QED
- Segundo caso: $n$ es impar:
Ya que queremos que todos los $x_i$ a un ser extraño, $X$ tiene que ser impar (como la suma de un número impar de números impares).
De la misma manera, ya que $(n-1)$ es incluso, $X_p$ tiene que ser par.
Ahora desde $X=X_p+x_n$ y desde $X$ es impar y $X_p$ es incluso, $x_n$ tiene que ser impar. QED
