OMA Foros

Publicado: **Vie 04 May, 2018 3:47 pm**

En un tablero de $100 \times 100$ cada casilla está coloreada de blanco o de negro, todas las casillas del borde del tablero son negras. Además ningún cuadrado de $2 \times 2$ contenido en el tablero tiene sus cuatro casillas del mismo color. Demostrar que el tablero contiene un cuadrado de $2 \times 2$ coloreado como el tablero de ajedrez.

Publicado: **Vie 04 May, 2018 11:03 pm**

Spoiler: mostrar: Pintamos cada segmento solo si este pertenece a 2 cuadrados que están pintados con distintos colores,por contradicción supongamos que no existe ningún cuadrado pintado como ajedrez,es claro que en vez de analizar un cuadrado de $2×2$ podemos analizar los segmentos que pasan por el centro de este cuadrado que forman "la cruz" de dicho punto (el del centro).

Analizando todas las formas de pintar un cuadrado de $2×2$ vemos que solo en la cruz puede haber 0 o 2 o 4 segmentos pintados,donde se da el primer caso si y solo si todas las casillas de ese cuadrado son del mismo color y el segundo caso es si y solo si el cuadrado tiene sus casillas como un tablero de ajedrez y dado que ningún caso puede darse por lo que hemos supuesto, entonces en una cruz siempre hay exactamente 2 segmentos pintados.
Es claro que como todas las casillas del borde son pintados de negro,entonces todos los segmentos del borde y los que pertenecen a 2 casillas del borde no están pintados,llamemos estos segmentos del tipo 1 y los demás del tipo 2 sea $m $ la cantidad de segmentos pintados en el tablero, esto es lo mismo que la cantidad de segmentos pintados del tipo 2 .
20180504_222656-1-1.jpg

En el tablero pintamos los vértices que no están en el borde de rojo y verde como ajedrez. Es facil ver que hay $\frac {999^2+1}{2} $ vertices rojos y $\frac{999^2-1}{2}$ vertices verdes. Es claro que todas las cruces de los vértices rojos son disjuntas entonces la cantidad de segmentos pintados en estas cruces es el doble de la cantidad de vértices que es $999^2+1$ y también es fácil ver que cada la union de estas cruces es todos los segmentos de tipo 2 más algunos del tipo 1 entonces como los del tipo 1 no están pintados la cantidad de segmentos pintados en la unión es la cantidad de segmentos pintados del tipo 2 que es $m $ entonces $m=999^2+1$.
No es difícil ver que podemos hacer un análisis similar con los vértices verdes y con estos llegamos a que $m=999^2-1$ uniendo ambos resultados tenemos una contradicción.

Por lo tanto si existe un cuadrado de $2×2$ de ese tipo

Publicado: **Vie 09 Nov, 2018 7:10 pm**

Se entiende qué hay al menos uno o exactamente uno?

Publicado: **Sab 10 Nov, 2018 10:43 am**

Al menos uno

Publicado: **Jue 13 Feb, 2020 12:11 am**

enigma1234 escribió: ↑Vie 04 May, 2018 11:03 pm
Spoiler: mostrar
Pintamos cada segmento solo si este pertenece a 2 cuadrados que están pintados con distintos colores,por contradicción supongamos que no existe ningún cuadrado pintado como ajedrez,es claro que en vez de analizar un cuadrado de </math>" role="presentation" style="position: relative;">2×2<math xmlns="http://www.w3.org/1998/Math/MathML"><mn ... an><script type="math/tex" id="MathJax-Element-11">2×2</script> podemos analizar los segmentos que pasan por el centro de este cuadrado que forman "la cruz" de dicho punto (el del centro).

Analizando todas las formas de pintar un cuadrado de </math>" role="presentation" style="position: relative;">2×2<math xmlns="http://www.w3.org/1998/Math/MathML"><mn ... an><script type="math/tex" id="MathJax-Element-12">2×2</script> vemos que solo en la cruz puede haber 0 o 2 o 4 segmentos pintados,donde se da el primer caso si y solo si todas las casillas de ese cuadrado son del mismo color y el segundo caso es si y solo si el cuadrado tiene sus casillas como un tablero de ajedrez y dado que ningún casa puede darse por lo que hemos supuesto, entonces en una cruz siempre hay exactamente 2 segmentos pintados.
Es claro que como todas las casillas del borde son pintados de negro,entonces todos los segmentos del borde y los que pertenecen a 2 casillas del borde no están pintados,llamemos estos segmentos del tipo 1 y los demás del tipo 2 sea </math>" role="presentation" style="position: relative;">m<math xmlns="http://www.w3.org/1998/Math/MathML"><mi ... an><script type="math/tex" id="MathJax-Element-13">m </script> la cantidad de segmentos pintados en el tablero, esto es lo mismo que la cantidad de segmentos pintados del tipo 2 .
20180504_222656-1-1.jpg

En el tablero pintamos los vértices que no están en el borde de rojo y verde como ajedrez. Es facil ver que hay </math>" role="presentation" style="position: relative;">9992+12<math xmlns="http://www.w3.org/1998/Math/MathML"><mf ... an><script type="math/tex" id="MathJax-Element-14">\frac {999^2+1}{2} </script> vertices rojos y <mrow class="MJX-TeXAtom-ORD"><msup><mn>999</mn><mn>2</mn></msup><mo>−</mo><mn>1</mn></mrow><mrow class="MJX-TeXAtom-ORD"><mn>2</mn></mrow></math>" role="presentation" style="position: relative;">9992−12<math xmlns="http://www.w3.org/1998/Math/MathML"><mrow class="MJX-TeXAtom-ORD"><msup><mn>999</mn><mn>2</mn></msup><mo>−</mo><mn>1</mn></mrow><mrow class="MJX-TeXAtom-ORD"><mn>2</mn></mrow></math><script type="math/tex" id="MathJax-Element-15">{999^2-1}{2}</script> vertices verdes. Es claro que todas las cruces de los vértices rojos son disjuntas entonces la cantidad de segmentos pintados en estas cruces es el doble de la cantidad de vértices que es </math>" role="presentation" style="position: relative;">9992+1<math xmlns="http://www.w3.org/1998/Math/MathML"><ms ... an><script type="math/tex" id="MathJax-Element-16">999^2+1</script> y también es fácil ver que cada la union de estas cruces es todos los segmentos de tipo 2 más algunos del tipo 1 entonces como los del tipo 1 no están pintados la cantidad de segmentos pintados en la unión es la cantidad de segmentos pintados del tipo 2 que es </math>" role="presentation" style="position: relative;">m<math xmlns="http://www.w3.org/1998/Math/MathML"><mi ... an><script type="math/tex" id="MathJax-Element-17">m </script> entonces </math>" role="presentation" style="position: relative;">m=9992+1<math xmlns="http://www.w3.org/1998/Math/MathML"><mi ... an><script type="math/tex" id="MathJax-Element-18">m=999^2+1</script>.
No es difícil ver que podemos hacer un análisis similar con los vértices verdes y con estos llegamos a que </math>" role="presentation" style="position: relative;">m=9992−1<math xmlns="http://www.w3.org/1998/Math/MathML"><mi ... an><script type="math/tex" id="MathJax-Element-19">m=999^2-1</script> uniendo ambos resultados tenemos una contradicción.

Por lo tanto si existe un cuadrado de </math>" role="presentation" style="position: relative;">2×2<math xmlns="http://www.w3.org/1998/Math/MathML"><mn ... an><script type="math/tex" id="MathJax-Element-20">2×2</script> de ese tipo

eso de que haciendo un analisis similar con los vértices verdes da $\frac{99^2-1}2$ y por eso hay una contradiccion creo que esta mal porque si fuera así entonces aunque los bordes no esten pintados de negro, el problema tendría la misma solución, y esto es falso porque en ese caso hay un ejemplo que lo refuta (podés pintar rayas y funciona)

Publicado: **Sab 26 Dic, 2020 6:16 pm**

A ver...

Spoiler: mostrar: No sé si está bien... otra vez estaba entre mis borradores ya olvidados, jeje... igual tiene un aire a varios problemas... como el 9 de la FOFO de este año

Supongamos que no existe ninguna casilla tipo ajedrez. Numeramos filas y columnas con los números del 0 al 99. Decimos que una casilla es par si y sólo si (fila + columna) es par y decimos que es impar si no.

Un salto es un movimiento desde una casilla hacia otra que comparte exactamente un vértice pero de distinto color (notar que los saltos siempre nos llevan de casillas pares a casillas pares y viceversa). Supongamos que existe una serie de saltos que nos lleva de un lado del tablero hacia el otro. Supongamos que el camino lleva de la izquierda a la derecha.

Como se empieza en la columna 0, la fila inicial es par, y como se termina en la columna 99, la fila final es impar. Ahora, como cada salto cambia la fila en 1, se sigue que la cantidad de saltos es impar. Además, como cada salto cambia el color de la casilla en la que se está, si la primera casilla era negra, entonces la última será blanca, lo cual es absurdo puesto que todas las casillas del borde son negras. De esto se sigue que tal serie de saltos no puede existir.

Ahora, marquemos de verde todas las casillas a las que se puede llegar con una serie de saltos empezando desde cualquier casilla par de la columna 0. Vamos entonces a hacer algo raro con nuestro tablero: Tomamos todas las casillas pares y las rotamos $45^{\circ}$ alrededor de su centro y las agrandamos con un factor de $\sqrt{2}$. El resultado es que estas casillas forman ahora una red de casillas cuyos lados coinciden. Si consideramos las casillas verdes en esta nueva red, vemos lo siguiente: (a) A la izquierda hay $50$ casillas verdes alineadas en sus vértices, (b) el camino que llevaba de una casilla verde a otra a través de diagonales, ahora es un camino por casillas adyacentes (que comparten un lado). De estas dos se deduce que las casillas verdes forman una forma conexa, y por lo tanto que existe un único perímetro que lo recorre todo.

Es claro que este perímetro interseca a los bordes de arriba y abajo al menos una vez. Tomemos la intersección con el borde de arriba que esté más a la derecha y recorramos el perímetro yendo hacia abajo, hasta encontrarnos con un borde. Si este borde es el superior, entonces las casillas contenidas en el perímetro no estarían conectadas con las casillas de la izquierda, lo cual es absurdo. Similarmente, si este borde fuese el izquierdo, entonces habría dos partes separadas sobre él, absurdo también. Por otro lado, si el borde fuese el derecho, entonces se podría viajar desde una casilla verde de la izquierda a una de la derecha, pero dijimos que esto no se podía. Entonces, por descarte tenemos que este borde es el inferior.

Veamos ahora qué es lo que representa este camino desde el borde superior hasta el inferior en el tablero original: Notemos que cada vértice del tablero modificado corresponde a una casilla impar del tablero original, por lo que este recorrido sería una serie de movimientos en diagonal. Veamos que estos movimientos son saltos: Si no lo fueran, es porque las casillas son del mismo color. Ahora, si nos fijamos en el 2x2 que las contiene, como estas dos casillas eran el perímetro, de un lado vamos a tener una casilla verde y del otro lado una que no es verde. Ahora, si estas fuesen de distinto color, entonces de la casilla verde se podría saltar a la no verde, pero entonces ésta habría sido verde para empezar, por lo que tienen que ser del mismo color. Ahora, tenemos un 2x2 en el que ambos pares de casillas opuestas son del mismo color, luego o todas las casillas son iguales (imposible por enunciado) o el tablero es un ajedrez (asumimos que esto no ocurría), luego la proposición anterior es falsa y los movimientos son efectivamente saltos (¡al fin usamos la condición del enunciado!)

Para finalizar, notemos que el párrafo anterior implica la existencia de una serie de saltos que lleva desde una casilla superior a una inferior, pero esto vendría a ser lo mismo que un camino de izquierda a derecha, así que también tendríamos el mismo absurdo que antes y se nos agotaron las posibilidades.

De este modo, la proposición inicial debe ser falsa y el tablero de ajedrez debe existir sí o sí.

OMA Foros

Selectivo de IMO 2018 - Problema 3

Selectivo de IMO 2018 - Problema 3

Re: Selectivo de IMO 2018 - Problema 3

Re: Selectivo de IMO 2018 - Problema 3

Re: Selectivo de IMO 2018 - Problema 3

Re: Selectivo de IMO 2018 - Problema 3

Re: Selectivo de IMO 2018 - Problema 3