Olimpíada de Mayo 2022 N1 P4

[Matías V5]

Ana y Bruno tienen un tablero cuadriculado de $8 \times 8$. Ana pinta cada una de las $64$ casillas con algún color. Después Bruno elige dos filas y dos columnas del tablero y mira las $4$ casillas donde se cruzan. El objetivo de Bruno es que estas $4$ casillas sean del mismo color.
¿Cuántos colores como mínimo debe usar Ana para que Bruno no pueda cumplir su objetivo?
Mostrar cómo puede pintar el tablero con esa cantidad de colores y explicar por qué si usa menos colores entonces Bruno siempre puede cumplir su objetivo.

[Ulis7s]

Spoiler: mostrar

CamScanner 17-04-2024 17.01_01.jpg

[BR1]

@Ulis7s Cuidado que tu ejemplo para $n=2$ no anda.

Mayo2022N1P4.png

[BR1]

Ahora sí, mi solución

Spoiler: mostrar

La cantidad mínima de colores es $3$. Primero vemos un ejemplo con $3$ colores que satisface las condiciones del enunciado.

Mayo2022N1P4B.png

Veamos que no es posible pintar el tablero con $2$ colores, digamos blanco y negro. Miremos la primera fila, supongamos que hay al menos $4$ casillas negras (concluimos análogamente si hay al menos $4$ casillas blancas). En la segunda fila en las casillas que coinciden en la columna con casillas negras de la primera fila puede haber a lo sumo $1$ casilla negra, por lo tanto hay al menos $3$ columnas que tienen una casilla negra en la primera fila y una casilla blanca en la segunda. Luego miramos la tercera fila, entonces en las columnas antes destacadas, que son al menos $3$, vamos a tener $2$ casillas negras o $2$ casillas blancas, y usando estas Bruno va a poder cumplir su objetivo.