Selectivo de IMO 2018 - Problema 4

Avatar de Usuario
Matías V5

Colaborador OFO - Jurado FOFO 6 años - Jurado
Mensajes: 890
Registrado: Dom 17 Oct, 2010 4:44 pm
Medallas: 6
Nivel: Exolímpico

Selectivo de IMO 2018 - Problema 4

Mensaje sin leer por Matías V5 » Vie 04 May, 2018 3:36 pm

Se tiene un tablero de $10 \times 10$ dividido en casillas de $1 \times 1$. Un punto luminoso en un vértice de un cuadrado de $1 \times 1$ ilumina a todos los cuadrados de $1 \times 1$ a los que ese vértice pertenece. Hallar la cantidad mínima de puntos luminosos que se necesitan para que todos los cuadrados de $1 \times 1$ del tablero estén iluminados aún en el caso de que uno cualquiera de los puntos luminosos, no sabemos cuál, deje de funcionar.
"La geometría es el arte de hacer razonamientos correctos a partir de figuras incorrectas." -- Henri Poincaré

Avatar de Usuario
Martín Vacas Vignolo
Mensajes: 399
Registrado: Mié 15 Dic, 2010 6:57 pm
Nivel: Exolímpico

Re: Selectivo de IMO 2018 - Problema 4

Mensaje sin leer por Martín Vacas Vignolo » Vie 04 May, 2018 6:02 pm

Creo que está todo
Spoiler: mostrar
Tenemos una cuadrícula de $11\times 11$ puntos. Si pintamos las columnas pares tendremos pintados $11\times 5=55$ puntos y es claro que ese ejemplo funciona porque cada cuadrado tiene $2$ puntos pintados.

Ahora probemos que $55$ es el mínimo: consideramos una fila de cuadrados. Tenemos 3 posibilidades:

1) Hay 11 o más pintados.
2) Hay 10 pintados. En este caso la única forma de que todos los cuadrados tengan al menos 2 puntos pintados es pintando las columnas pares de esa fila.
3) Hay menos de 10 pintados. En este caso nos aseguramos tener un cuadrado con un sólo punto pintado y fallaría. Por lo tanto no puede haber menos de 10 pintados en cada fila de cuadrados.

Si todas las filas tienen 11 o más pintados, entonces mirando las filas de cuadrados 2, 4, 6, 8, 10, que son disjuntas, tendríamos al menos $55$ puntos pintados, como queríamos.

Si hay filas con 10, vimos que la única configuración posible de esa fila es tener pintadas las columnas pares. Supongamos que hay una fila de cuadrados, la $i$, de 10 puntos pintados y entonces están pintados los puntos $(i,2),(i,4),...,(i,10),(i+1,2),...,(i+1,10)$.

Miramos cualquier columna de cuadrados $j$, y esa columna no puede tener 10 puntos pintados, porque en ese caso esa columna debería tener sólo las filas de puntos pares pintadas $(2,j),...,(10,j),(2,j+1),...,(10,j+1)$ y eso no ocurre porque sabemos que están pintados o bien los puntos $(i,j)$ e $(i+1,j)$ o bien los puntos $(i,j+1)$ e $(i+1,j+1)$.

Por lo tanto, si hay una fila de cuadrados con 10 puntos pintados, todas las columnas deben tener al menos 11 puntos pintados. Seleccionando las columnas 2, 4, 6, 8, 10, tenemos al menos $55$ puntos pintados.
1  
[math]

Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial
Mensajes: 683
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 1
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Selectivo de IMO 2018 - Problema 4

Mensaje sin leer por Gianni De Rico » Sab 05 May, 2018 1:02 pm

Spoiler: mostrar
Sea $n\in \mathbb{N}$. Un tablero $T_n$ es un tablero de $n\times n$. Un tablero $L_n$ es el tablero que se obtiene al quitar un tablero $T_{n-1}$ de un tablero $T_n$, es decir, una $L$ de lados $n$. Escribo $T_n=T_{n-1}+L_n$.
Llamo fichas a los puntos luminosos, digo que una casilla está cubierta cuando tiene al menos dos fichas en sus vértices y que un tablero está lleno cuando todas sus casillas están cubiertas. Que una casilla esté cubierta es equivalente a que esté iluminada aunque uno de sus puntos luminosos falle, y no podemos asegurar que una casilla no cubierta se mantenga iluminada, pues podría fallar el único punto que la ilumina, o no tener ningún punto que la ilumine. Luego, que un tablero esté lleno es equivalente a que todas las casillas del tablero estén iluminadas aunque alguno de los puntos luminosos falle.
Sea $X$ un tablero dividido en cuadrados de $1\times 1$, en el que cada cuadrado comparte un lado con al menos otro cuadrado. Llamo $C(X)$ a la mínima cantidad de fichas que necesito para llenar $X$.


Dividimos el problema en $2$ partes

Parte $1$: Demostrar que $C(L_{2n})=4n-1$
Spoiler: mostrar
Lo probaremos por inducción

Caso base: $n=1$
Tenemos que poner $2$ fichas en $a$ y $2$ fichas en $b$, luego, necesitamos al menos $4$ fichas. Pero hay a lo sumo (puede ser que no la coloquemos ahí) una ficha que estamos contando tanto en $a$ como en $b$, que es la que está en el vértice en común de las $3$ casillas de $L_2$. Luego, necesitamos al menos $4-1=3$ fichas.
Caso base L.png
Paso inductivo: Supongamos que vale para $n=k$, veamos que vale para $k+1$
El $L_{2k+2}$ se forma agregando $2$ casillas en cada extremo de $L_{2k}$
L_(2k+2).png
Por hipótesis inductiva podemos cubrir $L_{2k}$ con $4k-1$ fichas. La última casilla a la derecha y la última casilla arriba de $L_{2k+2}$ no están en contacto con ninguna casilla de $L_{2k}$, por lo tanto, no están en contacto con ninguna ficha, luego $C(L_{2k+2})\geqslant C(L_{2k})+C(T_1)+C(T_1)$. Como $C(T_1)=2$, entonces $C(L_{2k+2})\geq 4k-1+2+2=4(k+1)-1$.
Con este ejemplo vemos que nos alcanza con $4(k+1)-1$ fichas.
L.png
Como todas las casillas están cubiertas, el tablero está lleno y el ejemplo funciona.
La inducción está completa.
Parte $2$: Demostrar que $C(T_{2n})=\binom{2n+1}{2}$
Spoiler: mostrar
Lo probaremos por inducción

Caso base: $n=1$
Si no ponemos ninguna ficha en el centro de $T_2$, cada ficha toca a lo sumo $2$ casillas. Tenemos $4$ casillas, entonces necesitamos por lo menos $8$ fichas para llenar $T_2$, pero como las fichas tocan a lo sumo $2$ casillas, estamos contando cada ficha a lo sumo dos veces, por lo tanto necesitamos al menos $\frac{8}{2}=4$ fichas.
Si ponemos una ficha en el centro de $T_2$, cada casilla necesita al menos una ficha más, entonces necesitamos al menos $4$ fichas más; pero como las fichas tocan a lo sumo $2$ casillas, estoy contando cada ficha a lo sumo $2$ veces, luego, necesitamos por lo menos $\frac{4}{2}=2$ fichas más. Por lo tanto necesitamos al menos $1+2=3=\binom{3}{2}$ fichas.
Caso base T.png
Paso inductivo: Supongamos que vale para $n=k$, veamos que vale para $k+1$.
Por definición de $T_{2k+2}$ tenemos $T_{2k+2}=T_{2k+1}+L_{2k+2}$ (*)
Por definición de $T_{2k+1}$ tenemos $T_{2k+1}=T_{2k}+L_{2k+1}$ (**)
De (*) y (**) tenemos $T_{2k+2}=T_{2k}+L_{2k+1}+L_{2k+2}$
T_(2k+2).png
Ninguna de las casillas de $L_{2k+2}$ está en contacto con alguna casilla de $T_{2k}$, entonces no tienen ninguna ficha en común. Luego, $C(T_{2k+2})\geqslant C(T_{2k})+C(L_{2k+2})$. Por hipótesis inductiva tenemos $C(T_{2k})=\binom{2k+1}{2}$, por lo demostrado en la Parte $1$ tenemos $C(L_{2k+2})=4(k+1)-1$.
Entonces $C(T_{2k+2})\geqslant C(T_{2k})+C(L_{2k+2})=\binom{2k+1}{2}+4(k+1)-1=\frac{2k(2k+1)}{2}+4(4k+1)-1=\frac{2k(2k+1)+8(k+1)-2}{2}=\frac{4k^2+2k+8k+8-2}{2}=\frac{4k^2+4k+6k+6}{2}=\frac{2k(2k+2)+3(2k+2)}{2}=\frac{(2k+2)(2k+3)}{2}=\binom{2k+3}{2}=\binom{2(k+1)+1}{2}$
Con este ejemplo vemos que nos alcanza con $\binom{2(k+1)+1}{2}$ fichas.
T.png
Como todas las casillas están cubiertas, el tablero está lleno y el ejemplo funciona.
La inducción está completa.
Por lo tanto para $n=5$ tenemos $C(T_{10})=\binom{11}{2}=55$
No tienes los permisos requeridos para ver los archivos adjuntos a este mensaje.
[math]

Avatar de Usuario
Joacoini

OFO - Medalla de Plata
Mensajes: 77
Registrado: Jue 12 Oct, 2017 10:17 pm
Medallas: 1
Nivel: 2

Re: Selectivo de IMO 2018 - Problema 4

Mensaje sin leer por Joacoini » Sab 05 May, 2018 6:38 pm

Generalizo los tableros de $2n\times 2n$, seguro se puede una solución parecida para los impares.
Spoiler: mostrar
Si hay $2$ puntos luminosos en un mismo cuadrado pintamos el segmento que los une, vamos a tener dos tipos de segmentos, las rayas son los que coinciden un un lado del cuadrado mientras que las diagonales unen los vértices opuestos del cuadrado.
Una diagonal nos asegura solo un cuadrado mientras que la raya uno o dos.
Como hay $4n^2$ casillas se necesitan al menos $2n^2$ rayas para asegurar todas las casillas.
Llamamos segmento de longitud $L$ a $L$ rayas unidas donde solo se forman ángulos de 180 grados, la mayor longitud de uno de estos segmentos es de $2n$
Un segmento de longitud $L$ utiliza $L+1$ puntos luminosos.
Si dos segmentos comparten un punto luminoso debe haber una casilla con $2$ rayas por lo tanto si se utilizan $2n^2$ rayas va a haber una casilla que no tiene ninguna raya por lo que se va a tener que agregar una raya o diagonal más y agregar una de estas implica agregar uno o dos puntos luminosos por lo tanto el punto luminoso que comparten los dos segmentos mencionados va a aparecer por algún lado y tal ves con alguno extra.
Llamamos $a_i$ a la cantidad de segmentos de longitud $i$.
$a_1+2a_2+...+2na_{2n}\geq 2n^2$
Sea $p$ la cantidad de puntos luminosos.
$p\geq 2a_1+3a_2+...+(2n+1)a_{2n}\geq 2n^2+a_1+a_2+...+a_{2n}$
Por lo tanto $p$ es mínimo cuando se utiliza la menor cantidad de segmentos, lo cual pasa cuando usas $n$ segmentos de longitud $2n$, entonces $p\geq 2n^2+n$.
En el caso $2n=10$, $p\geq 2\times 5^2+5=55$, el ejemplo es el mismo que Martin.
NO HAY ANÁLISIS.

tuvie

Colaborador OFO - Medalla de Oro FOFO 6 años - Medalla Especial OFO - Jurado
Mensajes: 547
Registrado: Dom 09 Sep, 2012 11:58 am
Medallas: 6
Nivel: Exolímpico

Re: Selectivo de IMO 2018 - Problema 4

Mensaje sin leer por tuvie » Jue 10 May, 2018 12:55 pm

Solucion conjunta con @lucasdeamorin :
Spoiler: mostrar
Marquemos las siguientes casillas:

$$\begin{array}{|c|c|c|c|c|c|c|c|c|c|} \hline
\blacksquare & & & \blacksquare & & \blacksquare & & \blacksquare & & \blacksquare \\ \hline
& \blacksquare & & & & & & & & \\ \hline
& & & \blacksquare & & \blacksquare & & \blacksquare & & \blacksquare \\ \hline
\blacksquare & & \blacksquare & & & & & & & \\ \hline
& & & & & \blacksquare & & \blacksquare & & \blacksquare \\ \hline
\blacksquare & & \blacksquare & & \blacksquare & & & & & \\ \hline
& & & & & & & \blacksquare & & \blacksquare \\ \hline
\blacksquare & & \blacksquare & & \blacksquare & & \blacksquare & & & \\ \hline
& & & & & & & & & \blacksquare \\ \hline
\blacksquare & & \blacksquare & & \blacksquare & & \blacksquare & & \blacksquare & \\ \hline
\end{array}$$

Notemos que la condicion del enunciado se traduce en que cada casilla tenga al menos dos vertices como puntos luminosos. Por lo tanto la cantidad de puntos luminosos es al menos el doble de la cantidad de casillas marcadas en el tablero, menos la cantidad de vertices que son comunes a dos casillas marcadas. Como hay $30$ casillas marcadas, y $5$ vertices son comunes a $2$ casillas, la cantidad de puntos luminosos es al menos $55$.

Para el ejemplo, me robo alguno de los de arriba.
2  

Responder