Torneo de las Ciudades - Octubre 2018 - NM P4

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

OFO - Medalla de Plata-OFO 2018 FOFO 8 años - Medalla Especial-FOFO 8 años OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 FOFO 9 años - Medalla Especial-FOFO 9 años
OFO - Medalla de Oro-OFO 2020
Mensajes: 304
Registrado: Jue 12 Oct, 2017 10:17 pm
Medallas: 6
Nivel: Exolímpico
Ubicación: Ciudad Gotica

Torneo de las Ciudades - Octubre 2018 - NM P4

Mensaje sin leer por Joacoini » Mar 17 Mar, 2020 2:55 pm

Una cantidad finita de casillas de un tablero infinito están pintadas de negro; todas las demás casillas son blancas. Consideramos un polígono de papel colocado sobre el tablero con sus lados a lo largo de líneas del tablero que contiene por lo menos dos casillas del tablero. El polígono se puede trasladar (pero no se puede rotar) en cualquier dirección y distancia de modo que después de la traslación los lados del polígono estén nuevamente a lo largo de líneas del tablero. Si al completar una traslación exactamente una casilla cubierta por el polígono es blanca entonces esa casilla se pinta de negro. Demostrar que existe una casilla blanca que jamás será pintada de negro, no importa cuántas traslaciones sucesivas se realicen.
NO HAY ANÁLISIS.

Avatar de Usuario
Joacoini

OFO - Medalla de Plata-OFO 2018 FOFO 8 años - Medalla Especial-FOFO 8 años OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 FOFO 9 años - Medalla Especial-FOFO 9 años
OFO - Medalla de Oro-OFO 2020
Mensajes: 304
Registrado: Jue 12 Oct, 2017 10:17 pm
Medallas: 6
Nivel: Exolímpico
Ubicación: Ciudad Gotica

Re: Torneo de las Ciudades - Octubre 2018 - NM P4

Mensaje sin leer por Joacoini » Mié 18 Mar, 2020 8:55 pm

Spoiler: mostrar
Nuestro polígono se debería ver así
Poligono.jpeg
Ya que en caso de que no haya una casilla que sea la que este más arriba, por ejemplo, entonces hay una dirección en la que no podríamos avanzar.
Nombramos $W$, $A$, $S$ y $D$ a estas casillas que sobresalen (ver imagen)
Puede suceder que $W=D$, por ejemplo, pero no que las cuatro sean la misma o que tres sean la misma.

Seleccionamos un rectángulo que contenga a todas las casillas negras y lo pintamos de negro, total aumentar la cantidad de casillas negras del inicio no influye en nada.
Plano.jpeg
Si colocamos el polígono en el rectángulo pintado de tal forma que solo sobresalgan $W$ y $A$ y trazamos la columna en la que esta $W$ y la fila en la que esta $A$ estas nos delimitan un sector al que vamos a llamar sector 1 y de manera análoga definimos los sectores 2, 3 y 4.
Llamamos zona w al espacio entre el sector 1 y el sector 2 y definimos de forma análoga las zonas a, s y d.

Notemos que si en algún momento no podemos pintar más entonces el cambiar lo que hicimos antes y pintar de otra forma no va a cambiar este resultado ya que si podemos hacer el movimiento $M$ que pinta la casilla $C$ y decidimos hacer otros movimientos en vez de $M$ entonces luego de estos movimientos todavía podemos hacer $M$ a no ser que la casilla que íbamos a pintar con $M$ la hayamos pintado con los otros movimientos lo cual no cambia el resultado final.

Vamos a empezar a pintar con la siguiente restricción, pintamos solamente usando $W$ (o sea que poniendo el polígono cubierto de casillas negras y $W$ en una blanca) todas las casillas que podamos de la zona w y hacemos lo mismo con $A, S$ y $D$ en sus respectivas zonas.

Una vez que no podemos pintar más con la restricción la sacamos y sea $X$ la primera casilla que pinto sin la restricción.

Con el rectángulo negro nos podemos definir cuatro semiplanos, el superior, el inferior, el izquierdo y el derecho, por ejemplo el semiplano superior son todas las casillas que están por encima del rectángulo (contiene la zona w y parte del sector 1 y del sector 2).

WLOG podemos asumir que $X$ esta en el semiplano superior.

Si $X$ esta en la zona w entonces ubicamos el polígono encima de tal forma que esta todo negro excepto la casilla sobre $X$. La casilla sobre $X$ no puede ser $W$ ya que sino $X$ debió de haber sido pintada antes así que $W$ esta en una casilla negra $Y$ ubicada en el semiplano superior pero todas las casillas negras de ese semiplano fueron pintadas usando $W$ lo cual implica que al momento de pintar $Y$ el polígono estaba en la misma posición por lo que $X$ debería se estar pintada de negra en ese momento, contradicción.

Si $X$ esta en uno de los sectores 1 ó 2, WLOG esta en el sector 1, tenemos que si no es $W$ la parte del polígono que usamos para pintar $X$ entonces $W$ va a estar sobre una casilla negra $Y$ en plano superior y por un razonamiento análogo al anterior llegamos a la misma contradicción. Así que $W$ es la que pinta $X$ pero no hay forma de poner $W$ en el sector 1 y semiplanos superior sin que este $A$ en el sector 1 y como $X$ es la primera casilla que voy a pintar del sector tenemos que $A$ esta sobre una casilla sin pintar por lo que llegamos a una contradicción.

Al no haber forma de pintar una nueva casilla $X$ y al tener los sectores (que al menos existen dos) completamente vacíos llegamos a la conclusión de que hay casillas blancas que jamás serán pintadas de negro.
No tienes los permisos requeridos para ver los archivos adjuntos a este mensaje.
NO HAY ANÁLISIS.

Responder