Sí, podemos.
Dejemos que $P(n)$ sea el siguiente :
$P(n)$ : En el $4\times n$ podemos elegir algunas columnas de tal manera que para al menos tres filas, el número de celdas marcadas elegidas y el número de celdas marcadas no elegidas difieran como máximo en $1$ .
En lo siguiente, $[a,b]$ representa la celda en el $a$ -y en la fila $b$ -en la columna. También, $[a,b]=[c,d]$ significa que, o bien que ambos $[a,b]$ y $[c,d]$ están marcados o que ambos $[a,b]$ y $[c,d]$ están sin marcar.
Reclamación : Si $P(7),P(8)$ son verdaderos, entonces $P(n)$ es cierto para todos los $n\ge 9$ .
Prueba :
Hay $2^3=8$ posibilidades de que tres celdas estén marcadas o no. Así, si $n\ge 9$ entonces, por el principio de encasillamiento, hay al menos un par de enteros distintos $(s,t)$ tal que $[1,s]=[1,t],$$ [2,s]=[2,t]$ y $[3,s]=[3,t]$ . Podemos suponer que $[1,1]=[1,2],$$ [2,1]=[2,2]$ y $[3,1]=[3,2]$ . Ahora, considere el $4\times (n-2)$ hecha por el $(n-2)$ columnas de la tercera a la $n$ -th. Supongamos que $P(n-2)$ es verdadera. Entonces, podemos elegir algunas columnas (llámelas $p$ columnas) que satisfacen nuestra condición. Ahora, volvamos a la $4\times n$ matriz. Si se elige la primera columna y la $p$ columnas funciona, entonces hemos terminado. Si no funciona, entonces la elección de la segunda columna y la $p$ columnas funciona. Así que, $P(n)$ es cierto. $\quad\square$
A continuación, vamos a demostrar que $P(1),P(2),\cdots,P(8)$ son ciertas.
Utilizamos los dos lemas siguientes (las pruebas están escritas al final de la respuesta) :
Lema 1 : Si $P(n-1)$ es verdadera y hay al menos una columna cuyas cuatro celdas no están marcadas, entonces $P(n)$ es cierto.
Lema 2 : Si $P(n-2)$ es verdadera y hay un par de enteros distintos $(s,t)$ tal que al menos tres de $[i,s]=[i,t]\ (i=1,2,3,4)$ mantener, entonces $P(n)$ es cierto.
De los lemas,
$\ \ (\star)$ podemos suponer que hay al menos una celda marcada en cada columna y que no hay ningún par de enteros distintos $(s,t)$ tal que al menos tres de $[i,s]=[i,t]\ (i=1,2,3,4)$ aguantar.
Este $(\star)$ reduce el número de casos a considerar.
-
Para $n=1$ podemos elegir la columna.
-
Para $n=2$ podemos elegir la primera columna.
-
Para $n=3$ Si la elección de la primera y la segunda columna funciona, entonces hemos terminado. Si no funciona, entonces podemos suponer que $[1,1],[1,2],[2,1],[2,2],[3,1]$ están marcados y $[1,3],[2,3],[3,2]$ están sin marcar. Entonces, elegir la primera columna funciona.
-
Para $n=4$ si hay un par de enteros distintos $(s,t)$ tal que $[1,s]=[1,t]$ y $[2,s]=[2,t]$ entonces podemos suponer que $[3,s]$ está marcado y que $[3,t]$ está sin marcar.
caso 1 : Si $[3,u]=[3,v]$ donde $u\not=v$ son diferentes de $s$ y $t$ y, a continuación, elegir el $s$ -y el $u$ -las columnas funcionan.
caso 2 : Si $[3,u]$ está marcado y $[3,v]$ no está marcado, entonces la elección del $s$ -y el $v$ -las columnas funcionan.
Si no hay ningún par de enteros distintos $(s,t)$ tal que $[1,s]=[1,t]$ y $[2,s]=[2,t]$ entonces podemos suponer que $[1,1],[1,3],[2,1],[2,4]$ están marcados y $[1,2],[1,4],[2,2],[2,3]$ están sin marcar. Si la elección de la primera y la segunda columna funciona, entonces hemos terminado. Si no funciona, entonces de $(\star)$ La elección de la primera columna funciona.
-
Para $n=5$ si hay dos pares de números enteros distintos $(s,t),(u,v)$ tal que $[1,s]=[1,t],$$ [2,s]=[2,t], $$[1,u]=[1,v]$ y $[2,u]=[2,v]$ y, a continuación, elegir el $s$ -y el $v$ -las columnas funcionan.
Si sólo hay un par de enteros distintos $(s,t)$ tal que $[1,s]=[1,t]$ y $[2,s]=[2,t]$ entonces podemos suponer que tenemos los siguientes tres casos :
caso 1 : $[1,1],[1,2],[2,1],[2,2],[3,1]$ están marcados y $[3,2],[1,5],[2,5]$ están sin marcar. Si la elección de la primera y la tercera columna funciona, entonces hemos terminado. Si no funciona, entonces elegir la segunda y la tercera columna funciona.
caso 2 : $[1,1],[1,2],[1,3],[2,3],[2,4],[3,1]$ están marcados y $[1,4],[1,5],[2,1],[2,2],[3,2]$ están sin marcar. Si la elección de la primera y la tercera columna funciona, entonces hemos terminado. Si no funciona, entonces elegir la segunda y la tercera columna funciona.
caso 3 : $[1,3],[1,5],[2,4],[2,5],[3,1]$ están marcados y $[1,1],[1,2],[1,4],[2,1],[2,2],[2,3],[3,2]$ están sin marcar. Si la elección de la primera y la tercera y cuarta columnas funciona, entonces hemos terminado. Si no funciona, entonces elegir la primera y la quinta columna funciona.
-
Para $n=6$ podemos suponer que hay dos pares de enteros distintos $(s,t),(u,v)$ tal que $[1,s]=[1,t],$$ [2,s]=[2,t], $$[1,u]=[1,v]$ y $[2,u]=[2,v]$ . Entonces, podemos suponer que $[3,s],[3,u]$ están marcados y que $[3,t],[3,v]$ están sin marcar. Ahora, eligiendo el $s$ -y el $v$ -a y la de las dos columnas restantes funciona.
-
Para $n=7$ podemos suponer que hay tres pares distintos de enteros distintos $(a,b),(c,d),(e,f)$ tal que $[1,a]=[1,b],$$ [2,a]=[2,b], $$[1,c]=[1,d],$$ [2,c]=[2,d], $$[1,e]=[1,f]$ y $[2,e]=[2,f]$ . Entonces, podemos suponer que $[3,a],[3,c],[3,e]$ están marcados y que $[3,b],[3,d],[3,f]$ están sin marcar. Si $[3,g]$ está marcado donde $g$ es diferente de $a,b,c,d,e$ y $f$ y, a continuación, elegir el $a$ -a, el $c$ -y el $f$ -las columnas funcionan. Si $[3,g]$ no está marcado, entonces la elección del $a$ -a, el $d$ -y el $f$ -las columnas funcionan.
-
Para $n=8$ podemos suponer que hay cuatro pares distintos de enteros distintos $(a,b),(c,d),(e,f),(g,h)$ tal que $[1,a]=[1,b],$$ [2,a]=[2,b], $$[1,c]=[1,d],$$ [2,c]=[2,d], $$[1,e]=[1,f],$$ [2,e]=[2,f], $$[1,g]=[1,h]$ y $[2,g]=[2,h]$ . Entonces, podemos suponer que $[3,a],[3,c],[3,e],[3,g]$ están marcados y que $[3,b],[3,d],[3,f],[3,h]$ están sin marcar. Ahora, eligiendo el $a$ -a, el $d$ -a, el $e$ -y el $h$ -las columnas funcionan.
Por último, demostremos los dos lemas :
Lema 1 : Si $P(n-1)$ es verdadera y hay al menos una columna cuyas cuatro celdas no están marcadas, entonces $P(n)$ es cierto.
Prueba del lema 1 :
Considere la $4\times (n-1)$ excluyendo la columna. Dado que $P(n-1)$ es verdadera, podemos elegir las columnas adecuadas (llamarlas $p$ columnas) para el $4\times (n-1)$ matriz. Ahora, volviendo a la $4\times n$ vemos que la elección de la matriz $p$ las columnas funcionan. $\quad\square$
Lema 2 : Si $P(n-2)$ es verdadera y hay un par de enteros distintos $(s,t)$ tal que al menos tres de $[i,s]=[i,t]\ (i=1,2,3,4)$ mantener, entonces $P(n)$ es cierto.
Prueba del lema 2 :
Considere la $4\times (n-2)$ excluyendo el $s$ -y el $t$ -a las columnas. Dado que $P(n-2)$ es verdadera, podemos elegir las columnas adecuadas (llamarlas $p$ columnas) para el $4\times (n-2)$ matriz. Ahora, volvamos a la $4\times n$ matriz. Si se elige el $s$ -y la columna $p$ columnas funciona, entonces hemos terminado. Si no funciona, entonces la elección de la $t$ -y la columna $p$ las columnas funcionan. $\quad\square$
0 votos
Creo que puedo estar entendiendo mal este problema. En el ejemplo dado, ¿por qué no es aceptable elegir simplemente, digamos, la primera columna? De este modo se obtienen dos celdas marcadas y una sin marcar, una diferencia de exactamente 1.
1 votos
@mhum: porque la segunda fila tiene dos celdas marcadas no elegidas y ninguna elegida, por lo que la diferencia es $2$ .
0 votos
@RossMillikan ¡Ah, ya veo! De alguna manera se me había escapado la distinción entre elegido/unchosen en medio de la distinción entre marcado/no marcado.