Se nos da una tabla de $18\times 18$, todos cuyas células pueden ser negro o blanco.

Question

Se nos da una $18\times 18$ tabla, todos los de cuyas células pueden ser de color negro o blanco. Inicialmente, todas las células se de color blanco. Podemos realizar la siguiente operación: elige uno de los columna o una fila y cambiar el color de todas las celdas de esta columna o fila. Es posible repetir la operación para obtener un tabla con exactamente $16$ negro células?

Ahora me pregunto si el siguiente solución es la correcta?

---

Todos los de la matriz de aquí se $18\times 18$. Deje $S$ ser una matriz con todas las de entrada de $1$ $F$ ser una matriz con exactamente $16$ entradas con $0$ y el resto de las entradas son a $1$.

Deje $A_i$ ser una matriz con todas las entradas $1$ $i$- ésima fila, por $1\leq i\leq 18$ and the other are 0 and with all entries $1$ en $(i-18)$-ésima columna de a $19\leq i\leq 36$ y el otro son cero. Así, por ejemplo: $$A_2 =\begin{bmatrix} 0 & 0 & \dots & 0&0\\ 1&1&\dots &1&1\\ 0 & 0 & \dots & 0&0\\ \vdots & \vdots & \dots & \vdots &\vdots\\ 0 & 0 & \dots & 0&0 \end{bmatrix} \;\;\;{\rm y}\;\;\; A_{19} =\begin{bmatrix} 1 & 0 & \dots & 0&0\\ 1&0&\dots &0&0\\ 1 & 0 & \dots & 0&0\\ \vdots & \vdots & \dots & \vdots &\vdots\\ 1 & 0 & \dots & 0&0 \end{bmatrix} $$

Podemos entender una tabla como una matriz con la entrada $1$ si celda correspondiente es de color blanco y $0$ si es negro. Por lo $S$ es un a partir de la matriz y $F$ final de la matriz. Ahora cada cambio de color de un dada la matriz de $M$ se $M+A_i$ algunos $i\leq 36$

Así que después de algunas transformaciones que hemos igualdad como esta $$F = S + a_1A_1+a_2A_2+...+a_{36}A_{36}$$ where $a_i\in \{ 0,1\}$ para todos $i$. Mark $F-S = D$, lo $D$ es una matriz con exactamente $16$.

Ahora, ¿qué podemos decir acerca de $a_1,a_2,...$? Desde $D$ tiene exactamente $16$ se debe tener al menos dos columnas y dos filas con sólo ceros. Podemos asumir que todas las entradas en primera $2$ filas y primera $2$ las columnas se $0$, lo $D$ es como: $$ D =\begin{bmatrix} 0 & 0 & 0&\dots & 0&0\\ 0 & 0 &0 &\dots &0&0\\ 0 & 0 & *& \dots & *&*\\ \vdots & \vdots & \vdots & \dots &\vdots& \vdots\\ 0 & 0 & *&\dots & *&* \end{bmatrix} $$ Si $a_1=1$, a continuación, cada una de las $a_{19},a_{20},...a_{36}$ debe también ser $1$ ya que en la primera fila debe ser de todos los $0$. Pero entonces debemos también $a_2,...,a_{18}$ $1$ ya que en la primera columna sólo se $0$. Este significa que $D$ es una matriz cero lo cual no es cierto. Por lo $a_1=0$ y por lo tanto todos los $a_{19},a_{20},...a_{36}$$0$, y también todos los $a_2,...,a_{18}$ $0$ $D$ es la matriz cero de nuevo. Un contradicción.

---

Esto no es un duplicado. No quiero una solución, como en ese enlace, yo quiero una prueba de verificación!

Answer 1

Cambiar todas las entradas de una fila o columna es equivalente a la adición de una fila de todos los 1 a la fila o la adición de una columna de todos los 1 a la columna (modulo 2). Supongamos que hemos añadido a $k$ filas y $l$ columnas de todos los 1 para la matriz cero y se ha obtenido una matriz con exactamente 16 entradas iguales a 1. En primer lugar observamos que podemos eliminar dos hileras iguales (adición es conmutativa y dos hileras iguales se suman cero modulo 2). Así, podemos asumir que todas las filas son diferentes y todas las columnas son diferentes. En particular,$0\leq k,l\leq 18$.

Ahora, mediante la adición de $k$ diferentes filas de todos los 1 y $l$ diferentes columnas de todos los 1 obtenemos exactamente $18k+18l-kl$ entradas iguales a 1. Así que queremos $$18k+18l-kl=16,~0\leq k,l \leq 18.$$ Para solucionar esto, volver a escribir como $(18-k)(18-l)=18^2-16=4*7*11$. Ya que el producto de cada dos de los números 4, 7, y 11 supera los 18 años, esta ecuación no tiene soluciones dentro del rango requerido.

Answer 2

Deje $V$ ser el espacio vectorial sobre el campo con dos elementos, $\Bbb F_2$, generado por todas las matrices de la forma $N\times N$, $N=18$, que tiene exactamente una fila o una columna con una de las entradas, todas las demás entradas son cero. Consideramos el siguiente mapa de$V$$\Bbb F_2$:

$X$ $V$ se asigna a $$ f(X)= (x_{11}+x_{22}+\dots+x_{N-1,N-1}+x_{N,N}) + (x_{12}+x_{23}+\dots+x_{N-1,N}+x_{N,1})\ . $$ (La suma de dos consecutivos fijo diagonales de $X$, donde los índices se consideran modulo $N$.)

A continuación, cada generador de $V$ se asigna a cero, ya que los "bits" tomado en $f(X)$ son exactamente dos en cada fila y/o columna. Por lo $f$ se desvanece en $V$. Pero no desaparecer en cualquier cuadrática submatriz $A=A(I)$ con exactamente en las posiciones $I\times I$, $I$ un intervalo de $\{1,2,\dots,N\}$. (Por ejemplo, $I=\{1,\dots,16\}$ nuestro $N=18$.)

En nuestro caso la respuesta al problema es negativo. (El "cambio de color en una línea/columnas" corresponde a la adición de un generador de $V$ a una matriz. Estamos empezando con una matriz cero. Las matrices que se pueden obtener son exactamente las mismas que en el espacio vectorial $V$ de la dimensión de $N+N-1$.)

Nota: me puede proporcionar un poco simple comprobación del equipo en sabio, si es necesario.

---

Más tarde edit: es más sencillo para la prueba de las ecuaciones $$ x_{es}-x_{js}-x_ {}+x_{jt}=0\ ,\qquad 1\le i<j\le N\ ,\ 1\le s<t\le N\ , $$ que se puede extraer de todos los $2\times 2$ menores de una matriz de $X$ con el fin de probar/decidir si una matriz $X$ puede ser realizado. (El signo menos es un plus, pero hace que sea más sencillo ver que, por ejemplo, cada uno de los de arriba "una fila de la matriz de" satisfacer la ecuación, de manera explícita $1-1-0+0=0$, y, en consecuencia, para la columna de las matrices en la base de $V$...)

Answer 3

Sí, esta prueba se ve bien para mí.