La selección de las células, de manera que todos los $2\times 2$ plaza es impar, entonces

Question

Jacob selecciona algunas de las células de un a $12\times9$ tabla, de modo que cada $2\times 2$ subsquare contiene un número impar de celdas seleccionadas. Él, a continuación, selecciona algunos de los más células, de modo que todos los $2\times 2$ subsquare ahora contiene un número par de celdas seleccionadas. ¿Cuál es el número mínimo de celdas seleccionadas en la final?

[Fuente: la competencia rusa problema]

Answer 1

Si, al final, todos los $2\times2$ subsquare ahora contiene un número par de celdas seleccionadas, luego cada $2\times2$ subsquare contiene ahora bien $2$ o $4$ de las células. (A $2\times2$ subsquare no ha $0$ celdas seleccionadas, ya que en la primera etapa había al menos $1$ celda seleccionada.)

Teniendo en cuenta el $24$ discontinuo $2\times2$ subsquares que componen a la izquierda de $12\times8$ sección de la tabla, cada uno tiene al menos $2$ celdas seleccionadas en la final. Por lo que estos representan al menos el $48$ celdas seleccionadas. Por lo $48$ es un límite inferior para la respuesta. Pero en realidad podemos llevar a cabo la selección de una manera que selecciona a $48$ de las células.

Considere si estas $48$ celdas seleccionadas fueron el contenido de cada columna, a partir de la segunda. Esto es compatible con nosotros después de haber pasado por la primera etapa, donde cada $2\times2$ subsquare contiene un número impar de celdas seleccionadas? Seguro, simplemente anular la selección de todas las otras filas.

Por lo $48$ es el mínimo número de celdas seleccionadas en la final. Aquí es un proceso de selección para la que esto funciona.

$$\begin{array}{|c|c|c|c|c|c|c|c|c|} \hline \phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}\\ \hline \phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}\\ \hline \phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}\\ \hline \phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}\\ \hline \phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}\\ \hline \phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}\\ \hline \phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}\\ \hline \phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}\\ \hline \phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}\\ \hline \phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}\\ \hline \phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}\\ \hline \phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}\\ \hline\end{array} $$

$$\begin{array}{|c|c|c|c|c|c|c|c|c|} \hline \phantom{\checkmark}&\checkmark&\phantom{\checkmark}&\checkmark&\phantom{\checkmark}&\checkmark&\phantom{\checkmark}&\checkmark&\phantom{\checkmark}\\ \hline \phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}\\ \hline \phantom{\checkmark}&\checkmark&\phantom{\checkmark}&\checkmark&\phantom{\checkmark}&\checkmark&\phantom{\checkmark}&\checkmark&\phantom{\checkmark}\\ \hline \phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}\\ \hline \phantom{\checkmark}&\checkmark&\phantom{\checkmark}&\checkmark&\phantom{\checkmark}&\checkmark&\phantom{\checkmark}&\checkmark&\phantom{\checkmark}\\ \hline \phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}\\ \hline \phantom{\checkmark}&\checkmark&\phantom{\checkmark}&\checkmark&\phantom{\checkmark}&\checkmark&\phantom{\checkmark}&\checkmark&\phantom{\checkmark}\\ \hline \phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}\\ \hline \phantom{\checkmark}&\checkmark&\phantom{\checkmark}&\checkmark&\phantom{\checkmark}&\checkmark&\phantom{\checkmark}&\checkmark&\phantom{\checkmark}\\ \hline \phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}\\ \hline \phantom{\checkmark}&\checkmark&\phantom{\checkmark}&\checkmark&\phantom{\checkmark}&\checkmark&\phantom{\checkmark}&\checkmark&\phantom{\checkmark}\\ \hline \phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}&\phantom{\checkmark}\\ \hline\end{array} $$

$$\begin{array}{|c|c|c|c|c|c|c|c|c|} \hline \phantom{\checkmark}&\checkmark&\phantom{\checkmark}&\checkmark&\phantom{\checkmark}&\checkmark&\phantom{\checkmark}&\checkmark&\phantom{\checkmark}\\ \hline \phantom{\checkmark}&\checkmark&\phantom{\checkmark}&\checkmark&\phantom{\checkmark}&\checkmark&\phantom{\checkmark}&\checkmark&\phantom{\checkmark}\\ \hline \phantom{\checkmark}&\checkmark&\phantom{\checkmark}&\checkmark&\phantom{\checkmark}&\checkmark&\phantom{\checkmark}&\checkmark&\phantom{\checkmark}\\ \hline \phantom{\checkmark}&\checkmark&\phantom{\checkmark}&\checkmark&\phantom{\checkmark}&\checkmark&\phantom{\checkmark}&\checkmark&\phantom{\checkmark}\\ \hline \phantom{\checkmark}&\checkmark&\phantom{\checkmark}&\checkmark&\phantom{\checkmark}&\checkmark&\phantom{\checkmark}&\checkmark&\phantom{\checkmark}\\ \hline \phantom{\checkmark}&\checkmark&\phantom{\checkmark}&\checkmark&\phantom{\checkmark}&\checkmark&\phantom{\checkmark}&\checkmark&\phantom{\checkmark}\\ \hline \phantom{\checkmark}&\checkmark&\phantom{\checkmark}&\checkmark&\phantom{\checkmark}&\checkmark&\phantom{\checkmark}&\checkmark&\phantom{\checkmark}\\ \hline \phantom{\checkmark}&\checkmark&\phantom{\checkmark}&\checkmark&\phantom{\checkmark}&\checkmark&\phantom{\checkmark}&\checkmark&\phantom{\checkmark}\\ \hline \phantom{\checkmark}&\checkmark&\phantom{\checkmark}&\checkmark&\phantom{\checkmark}&\checkmark&\phantom{\checkmark}&\checkmark&\phantom{\checkmark}\\ \hline \phantom{\checkmark}&\checkmark&\phantom{\checkmark}&\checkmark&\phantom{\checkmark}&\checkmark&\phantom{\checkmark}&\checkmark&\phantom{\checkmark}\\ \hline \phantom{\checkmark}&\checkmark&\phantom{\checkmark}&\checkmark&\phantom{\checkmark}&\checkmark&\phantom{\checkmark}&\checkmark&\phantom{\checkmark}\\ \hline \phantom{\checkmark}&\checkmark&\phantom{\checkmark}&\checkmark&\phantom{\checkmark}&\checkmark&\phantom{\checkmark}&\checkmark&\phantom{\checkmark}\\ \hline\end{array} $$