OFO 2022 Problema 9

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
Johanna

OFO - Medalla de Plata-OFO 2015 OFO - Medalla de Plata-OFO 2017 FOFO 8 años - Jurado-FOFO 8 años OFO - Jurado-OFO 2019 FOFO Pascua 2019 - Jurado-FOFO Pascua 2019
COFFEE - Jurado-COFFEE Matías Saucedo OFO - Jurado-OFO 2020 OFO - Jurado-OFO 2021 OFO - Jurado-OFO 2022
Mensajes: 65
Registrado: Lun 22 Oct, 2012 9:38 pm
Medallas: 9
Nivel: Exolímpico

OFO 2022 Problema 9

Mensaje sin leer por Johanna »

Hallar la menor cantidad de casillas que se deben pintar en un tablero de $5\times 7$ de manera que cada casilla no pintada tenga exactamente una vecina pintada.

Aclaración: Dos casillas son vecinas si tienen un lado en común.
Avatar de Usuario
Johanna

OFO - Medalla de Plata-OFO 2015 OFO - Medalla de Plata-OFO 2017 FOFO 8 años - Jurado-FOFO 8 años OFO - Jurado-OFO 2019 FOFO Pascua 2019 - Jurado-FOFO Pascua 2019
COFFEE - Jurado-COFFEE Matías Saucedo OFO - Jurado-OFO 2020 OFO - Jurado-OFO 2021 OFO - Jurado-OFO 2022
Mensajes: 65
Registrado: Lun 22 Oct, 2012 9:38 pm
Medallas: 9
Nivel: Exolímpico

Re: OFO 2022 Problema 9

Mensaje sin leer por Johanna »

Aquí publicaremos la solución oficial.
sebach

Colaborador-Varias OFO - Medalla de Bronce-OFO 2017 OFO - Medalla de Bronce-OFO 2018 OFO - Medalla de Bronce-OFO 2020 OFO - Medalla de Plata-OFO 2021
OFO - Medalla de Plata-OFO 2022 OFO - Medalla de Plata-OFO 2023 OFO - Medalla de Oro-OFO 2024
Mensajes: 202
Registrado: Dom 06 Mar, 2011 11:49 am
Medallas: 8
Nivel: Exolímpico

Re: OFO 2022 Problema 9

Mensaje sin leer por sebach »

Me encantó este problema porque yo estaba queriendo demostrar que
Spoiler: mostrar
no se podía con menos de $14$, pintando segunda y cuarta fila, pensando “si quiero $13$, debe haber al menos una columna con menos de $2$”. Empecé pintando una casilla de la primera columna y dejando sin pintar las otras $4$, eso me fue forzando a algunas cosas,
y si bien primero probé algunas cosas sin éxito,
Spoiler: mostrar
después terminé llegando a un tablero donde pintaba $9$ casillas.
Digo eso de arriba también para comentar sobre el hecho de que no siempre (de hecho muy pocas veces) se llega a una solución de una, siguiendo la intuición inicial. Y puede ocurrir que viendo acá soluciones en el foro o en cualquier lado pensemos "uh nunca se me ocurriría eso" y está bueno, en mi opinión, recordar que siempre atrás de una solución pulida hay un montón de borradores, quizás frustración, etc. Así que si en algún momento están en esa situación, recuerden que la gente que lo resolvió (si es que alguien lo hizo) probablemente pasó por cosas similares.
Con esto no quiero decir que siempre que se frustren sigan y sigan hasta llegar a la respuesta, porque es verdad que pueden no llegar nunca. Pero bueno, digo para poner en perspectiva.


En fin, voy con mi solución:
Spoiler: mostrar
Ejemplo con $9$ casillas pintadas, las negras:
tablero_1.png
En la imagen podemos ver que hay $9$ casillas pintadas y todas las demás tienen exactamente una casilla vecina pintada.

Ahora, dividiendo el tablero como se ve en la figura de abajo, vemos que al menos una casilla de cada color deberá ser elegida como pintada, dado que en cada división hay una casilla cuyas todas celdas vecinas están incluidas con ella en la división, que significa que o bien pinto esa casilla o bien no la pinto, debiendo pintar una de sus vecinas que están en su división.
tablero_2.png
Esto demuestra que al menos habrá que pintar $8$ casillas.

Como ya tenemos un ejemplo con $9$, intentemos encontrar un ejemplo con exactamente $8$ casillas pintadas.

Como hay $8$ divisiones coloreadas, las casillas que no quedaron en ninguna división deberán no estar pintadas, ya que las $8$ pintadas corresponderán una a cada división.
Escribo una ‘x’ en las que necesariamente están sin pintar, y una ‘P’ en las que en nuestro caso estaré pintando, para más adelante.
tablero_3.png
De las parejas $(1, 2), (3, 4), (5, 6), (7, 8)$ puede verse que exactamente una de cada una deberá estar pintada. Esto es porque de esas casillas, las enumeradas con números pares ya tienen $3$ de sus $4$ casillas vecinas necesariamente sin pintar. Por lo que o las pinto a ellas o pinto a su última vecina que le quedaría.
Además, como la casilla central no está pintada, exactamente una de las casillas de su alrededor ($2, 4, 6, 8$) deberá estar pintada

Como las divisiones del tablero son simétricas con respecto a la columna del medio y a la fila del medio, y por lo último que dijimos sabemos que al menos una de las casillas $2, 4$ y una de las casillas $6, 8$ estará sin pintar. Podemos asumir sin pérdida de la generalidad que las casillas $2$ y $6$ están sin pintar, y ver adónde nos lleva eso.

Empezamos así:
tablero_4.png
Como las casillas que antes eran $2$ y $6$ ahora tienen a todas sus vecinas excepto una necesariamente sin pintar, debo pintar las $1$ y $5$. Y como dijimos que necesito pintar una por división colorida, esto determina lo siguiente:
tablero_5.png
Pero acá ya podemos ver que la casilla de arriba de la $2$ está sin pintar y todas sus vecinas necesariamente también, por lo que este tablero no será válido.

Esto demuestra que no existe un tablero con exactamente $8$ casillas pintadas, y ya vimos que con menos tampoco se puede.

Como tenemos un ejemplo con $9$, concluímos que esa es la respuesta.

No tienes los permisos requeridos para ver los archivos adjuntos a este mensaje.
Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial-FOFO 7 años OFO - Medalla de Oro-OFO 2019 FOFO 9 años - Jurado-FOFO 9 años COFFEE - Jurado-COFFEE Matías Saucedo OFO - Jurado-OFO 2020
FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber COFFEE - Jurado-COFFEE Iván Sadofschi FOFO 10 años - Jurado-FOFO 10 años
OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022 FOFO 12 años - Jurado-FOFO 12 años
OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años OFO - Jurado-OFO 2024
Mensajes: 2212
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 18
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: OFO 2022 Problema 9

Mensaje sin leer por Gianni De Rico »

Spoiler: mostrar
Ponemos aceitunas en el tablero de las siguientes formas (cada puntito representa una aceituna):\begin{array}{|c|c|c|c|c|c|c|}\hline
\color{green}\bullet & \quad & \quad & \color{green}\bullet & \quad & \quad & \color{green}\bullet \\
\hline
\quad & \quad & - & \quad & - & \quad & \quad \\
\hline
\quad & \color{green}\bullet & \quad & - & \quad & \color{green}\bullet & \quad \\
\hline
\quad & \quad & - & \quad & - & \quad & \quad \\
\hline
\color{green}\bullet & \quad & \quad & \color{green}\bullet & \quad & \quad & \color{green}\bullet \\
\hline
\end{array}\begin{array}{|c|c|c|c|c|c|c|}\hline
\quad & \quad & \color{green}\bullet & \quad & \quad & \quad & \color{green}\bullet \\
\hline
\color{green}\bullet & \quad & \quad & \quad & \color{green}\bullet & \quad & \quad \\
\hline
\quad & - & \quad & - & \quad & - & \quad \\
\hline
\quad & \quad & \color{green}\bullet & \quad & \quad & \quad & \color{green}\bullet \\
\hline
\color{green}\bullet & \quad & \quad & \quad & \color{green}\bullet & \quad & \quad \\
\hline
\end{array}\begin{array}{|c|c|c|c|c|c|c|}\hline
\color{green}\bullet & \quad & \quad & \color{green}\bullet & \quad & \quad & \color{green}\bullet \\
\hline
\quad & - & \quad & \quad & - & \quad & \quad \\
\hline
\quad & \quad & \color{green}\bullet & \quad & \quad & \color{green}\bullet & \quad \\
\hline
\quad & - & \quad & \quad & - & \quad & \quad \\
\hline
\color{green}\bullet & \quad & \quad & \color{green}\bullet & \quad & \quad & \color{green}\bullet \\
\hline
\end{array}\begin{array}{|c|c|c|c|c|c|c|}\hline
\color{green}\bullet & \quad & \quad & \color{green}\bullet & \quad & \quad & \color{green}\bullet \\
\hline
\quad & \quad & - & \quad & \quad & - & \quad \\
\hline
\quad & \color{green}\bullet & & \quad & \color{green}\bullet & \quad & \quad \\
\hline
\quad & \quad & - & \quad & \quad & - & \quad \\
\hline
\color{green}\bullet & \quad & \quad & \color{green}\bullet & \quad & \quad & \color{green}\bullet \\
\hline
\end{array}Notemos entonces que no hay ninguna casilla que sea vecina de dos casillas con aceitunas a la vez ni dos casillas con aceitunas que sean vecinas, luego, necesitamos pintar al menos $8$ casillas.

Supongamos que se puede con $8$ casillas. Los $-$ en los tableros son lugares en donde no puede ir una casilla pintada si usamos $8$ casillas, pues no tienen aceitunas ni son vecinas a una con aceituna. Combinando todas las distribuciones de aceitunas, tenemos que si usamos $8$ casillas, entonces en el siguiente tablero\begin{array}{|c|c|c|c|c|c|c|}\hline
\quad & \quad & \quad & \quad & \quad & \quad & \quad \\
\hline
\quad & - & - & \quad & - & - & \quad \\
\hline
\quad & - & \quad & - & \quad & - & \quad \\
\hline
\quad & - & - & \quad & - & - & \quad \\
\hline
\quad & \quad & \quad & \quad & \quad & \quad & \quad \\
\hline
\end{array}ninguna de las casillas con $-$ puede estar pintada.
Decimos que una casilla pintada cubre a una casilla si esta no está pintada y son vecinas. Notemos que cada casilla pintada cubre como mucho $4$ casillas. Además, por definición tenemos que cada casilla sin pintar está cubierta por exactamente una casilla pintada. Luego, la cantidad de casillas del tablero es la cantidad de casillas pintadas más la cantidad de casillas cubiertas, es decir, si $n$ es la cantidad de casillas cubiertas entonces $35=8+n$, de donde $n=27$.
Ahora, toda casilla que cubra $4$ está en el rectángulo central de $3\times 5$, por lo que debe estar en una de las casillas no marcadas con $-$ de dicho rectángulo. Cualquier casilla que cubra $4$ y esté en una de esas casillas, cubre a la casilla central del tablero, de modo que hay a lo sumo una casilla que cubre $4$, entonces las otras $7$ cubren a lo sumo $3$, luego$$27=n\leq 3\cdot 7+4=25$$absurdo.
El absurdo proviene de suponer que se puede con $8$, entonces no se puede con $8$, de modo que necesitamos al menos $9$ casillas.

Pintando las casillas marcadas con $\times$ en el siguiente tablero\begin{array}{|c|c|c|c|c|c|c|}\hline
\quad & \quad & \times & \quad & \quad & \times & \quad \\
\hline
\times & \quad & \quad & \quad & \quad & \times & \quad \\
\hline
\quad & \quad & \quad & \times & \quad & \quad & \quad \\
\hline
\quad & \times & \quad & \quad & \quad & \quad & \times \\
\hline
\quad & \times & \quad & \quad & \times & \quad & \quad \\
\hline
\end{array}obtenemos un ejemplo con $9$.
♪♫ do re mi función lineal ♪♫
Responder