[prinmat]

_Saludos cordiales:

Cada casilla de un tablero de 5x7 está pintada de rojo o azul, de tal modo que cada casilla (roja o azul) tiene al menos dos
casillas vecinas azules. ¿Cuántas casillas azules puede haber en el tablero como mínimo?

Aclaración: dos casillas son vecinas si tienen un lado en común.

ONEM 2024 Nivel 2

_Gracias

[Luis Fuentes]

Hola

Cada casilla de un tablero de 5x7 está pintada de rojo o azul, de tal modo que cada casilla (roja o azul) tiene al menos dos
casillas vecinas azules. ¿Cuántas casillas azules puede haber en el tablero como mínimo?

Aclaración: dos casillas son vecinas si tienen un lado en común.

ONEM 2024 Nivel 2

Este problema lo veo algo más peleón de lo que parece.

Spoiler

Yo he he encontrado esta configuración:



Con \( 35-11=24 \) casillas azules.

Sino me he equivocado cumple la condición y es minimal, en el sentido de que no se puede quitar ninguna casilla azul sin que la condición descrita falle. Pero eso no quiere decir que sea mínima.

El tablero no es muy grande. Es fácil ver que las casillas en las posiciones 1,2 y 2,1 y sus tres simétricas en las esquinas han de ser azules. Y a partir de ahí tirar del hilo viendo diferentes posibilidades... pero la causística se me termina por hacer larga.

[cerrar]

Saludos.

[sugata]

Hola

Cada casilla de un tablero de 5x7 está pintada de rojo o azul, de tal modo que cada casilla (roja o azul) tiene al menos dos
casillas vecinas azules. ¿Cuántas casillas azules puede haber en el tablero como mínimo?

Aclaración: dos casillas son vecinas si tienen un lado en común.

ONEM 2024 Nivel 2

Este problema lo veo algo más peleón de lo que parece.

Spoiler

Yo he he encontrado esta configuración:



Con \( 35-11=24 \) casillas azules.

Sino me he equivocado cumple la condición y es minimal, en el sentido de que no se puede quitar ninguna casilla azul sin que la condición descrita falle. Pero eso no quiere decir que sea mínima.

El tablero no es muy grande. Es fácil ver que las casillas en las posiciones 1,2 y 2,1 y sus tres simétricas en las esquinas han de ser azules. Y a partir de ahí tirar del hilo viendo diferentes posibilidades... pero la causística se me termina por hacer larga.

[cerrar]

Saludos.

Tengo que mirarlo bien, pero creo que de la fila central puedes poner en azul la 2 y la 4....

[Luis Fuentes]

Hola

Tengo que mirarlo bien, pero creo que de la fila central puedes poner en azul la 2 y la 4....

O todas azules. 

Se trata de buscar la configuración con el menor número posible de casillas azules.

Saludos.

[sugata]

Hola

Tengo que mirarlo bien, pero creo que de la fila central puedes poner en azul la 2 y la 4....

O todas azules. 

Se trata de buscar la configuración con el menor número posible de casillas azules.

Saludos.

Lo leí al revés....
 

[Guli-Guli]

Cada casilla de un tablero de 5x7 está pintada de rojo o azul, de tal modo que cada casilla (roja o azul) tiene al menos dos
casillas vecinas azules. ¿Cuántas casillas azules puede haber en el tablero como mínimo?

Aclaración: dos casillas son vecinas si tienen un lado en común.

Hice la resolución del problema y, efectivamente, Luis Fuentes tiene la razón: debe haber como mínimo 24 casillas azules en el tablero. Dado que en la demostración ilustro el tablero varias veces para explicarme mejor, opté por escribirlo a mano y pasarlo a un archivo PDF.
Está mal. Elimino, ya de paso, el archivo PDF adjuntado.

[Luis Fuentes]

Hola

Hice la resolución del problema y, efectivamente, Luis Fuentes tiene la razón: debe haber como mínimo 24 casillas azules en el tablero. Dado que en la demostración ilustro el tablero varias veces para explicarme mejor, opté por escribirlo a mano y pasarlo a un archivo PDF.

La idea de dividir el tablero el secciones para acotar el número de casillas azules y rojas es ingeniosa. Además como dije no es muy grande y no es imposible ir descartando casos.

Sin embargo no se si las cosas so tan inmediatas. Por ejemplo en la región 1 si no me pierdo algo, en principio y sin más argumentación, si cabrían tres rojas:



Saludos.

[geómetracat]

Está mal.

Una solución:

Spoiler

La idea básica es que como los bordes molestan, "compactificamos" el tablero a un toro y resolvemos el problema ahí, donde todo es mucho más uniforme.

Añadimos al tablero \( 5 \times 7 \) una fila y una columna con todas las casillas pintadas de rojo, e identificamos los extremos horizontales entre sí y los extremos verticales entre sí, de forma que tenemos un tablero \( 6 \times 8 \) en un toro, en el que cada casilla tiene cuatro vecinos.

Vamos a llamar a una configuración "admisible" si cada casilla tiene al menos dos vecinos azules.
Hay una correspondencia biyectiva entre las configuraciones admisibles del problema original en el plano \( 5 \times 7 \) y las configuraciones admisibles en el toro \( 6 \times 8 \) con una columna y una fila pintadas enteras de rojo. Esto es falso, pues una configuración admisible en el plano no da necesariamente una configuración admisible en el toro. De hecho, lo que es cierto es que hay una correspondencia biyectiva entre configuraciones admisibles del plano con las casillas del borde todas azules y configuraciones admisibles del toro con una columna y fila rojas. Por tanto todo lo que sigue está mal, solamente se obtiene una cota al número mínimo de casillas azules para configuraciones cuyo borde es todo azul.


Consideramos ahora el problema en el toro sin ninguna restricción, es decir, encontrar el máximo número de rojos en un tablero \( 6 \times 8 \) en el toro de manera que cada casilla tenga al menos dos vecinos azules. Aquí es relativamente sencillo ver que la solución óptima tiene \( 24 \) rojos. En efecto, si pintamos por ejemplo las columnas alternadas rojo, azul, rojo, azul... tenemos \( 24 \) rojos. Es imposible encontrar una configuración con más rojos, pues si consideramos por ejemplo la suma total del número de vecinos azules de cada casilla, el mínimo posible es cuando cada casilla tiene exactamente dos vecinos azules y la suma total es \( 6\cdot 8\cdot 2 = 96 \), mientras que partimos (con todo el tablero pintado de azul) de \( 6\cdot 8\cdot 4 = 192 \). A cada rojo que añadimos esta suma total de vecinos disminuye en \( 4 \). Por tanto el máximo de rojos que podemos tener son \( (192-96)/4 = 24 \).

Y ahora ya está. Como cada configuración admisible en el plano corresponde con una configuración admisible en el toro con una columna y una fila pintadas de rojo (que son \( 6+8-1=13 \) rojos), el máximo número de rojos posibles de una configuración admisible en el plano es \( 24-13=11 \) rojos, y por tanto el número mínimo de azules es \( 5\times 7 - 11=24 \).

Este argumento además tiene la ventaja de que generaliza a tableros de cualquier tamaño.

[cerrar]

[Guli-Guli]

Sin embargo no se si las cosas so tan inmediatas. Por ejemplo en la región 1 si no me pierdo algo, en principio y sin más argumentación, si cabrían tres rojas.

Sí, tienes razón. De hecho hallé una configuración del tablero con 23 casillas azules, por lo que tu tesis inicial es falsa.

Adjunto el PDF con la resolución del problema escrita a mano, donde demuestro que el tablero no puede tener menos de 23 casillas.

Una solución: (...)

Al final del PDF hallo la configuración del tablero con 12 casillas rojas, por lo que tu solución debe estar mal. A ver qué opinas.

[ani_pascual]

Hola:
Es cierto, algo debe de fallar en el razonamiento de geómetracat; he encontrado otro tablero con 12 casillas rojas y 23 azules, muy similar al de Guli-Guli

Añadido
El ejemplo no es válido, pues hay alguna casilla que no cumple las condiciones 
Saludos