Selectivo de IMO 2018 - Problema 3

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
Matías V5

Colaborador-Varias OFO - Jurado-OFO 2015 OFO - Jurado-OFO 2016 FOFO 6 años - Jurado-FOFO 6 años OFO - Jurado-OFO 2017
OFO - Jurado-OFO 2018 OFO - Jurado-OFO 2020 OFO - Jurado-OFO 2021
Mensajes: 1114
Registrado: Dom 17 Oct, 2010 4:44 pm
Medallas: 8
Nivel: Exolímpico

Selectivo de IMO 2018 - Problema 3

Mensaje sin leer por Matías V5 »

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.
We gave you a start so you'd know what to do
You've seen how it works, now it's over to you (...)
For there's so much more to explore!

Numberblocks - https://www.youtube.com/watch?v=KzTR72_srTU
Avatar de Usuario
enigma1234

OFO - Medalla de Oro-OFO 2018 FOFO 8 años - Medalla Especial-FOFO 8 años OFO - Medalla de Plata-OFO 2019 FOFO Pascua 2020 - Copa-FOFO Pascua 2020 OFO - Medalla de Oro-OFO 2024
Mensajes: 211
Registrado: Sab 03 Jun, 2017 8:07 pm
Medallas: 5
Nivel: Exolímpico

Re: Selectivo de IMO 2018 - Problema 3

Mensaje sin leer por enigma1234 »

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
No tienes los permisos requeridos para ver los archivos adjuntos a este mensaje.
Última edición por enigma1234 el Mar 14 Abr, 2020 4:45 pm, editado 1 vez en total.
3  
Teorema del Palomar
Mensajes: 5
Registrado: Mié 06 Sep, 2017 8:40 pm
Nivel: Exolímpico

Re: Selectivo de IMO 2018 - Problema 3

Mensaje sin leer por Teorema del Palomar »

Se entiende qué hay al menos uno o exactamente uno?
¿P=NP?
Avatar de Usuario
julianferres_

OFO - Medalla de Bronce-OFO 2015 OFO - Medalla de Plata-OFO 2016 OFO - Medalla de Plata-OFO 2017 OFO - Mención-OFO 2021
Mensajes: 388
Registrado: Sab 17 Sep, 2011 8:01 pm
Medallas: 4
Nivel: Exolímpico
Ubicación: Villa Ramallo, Buenos Aires

Re: Selectivo de IMO 2018 - Problema 3

Mensaje sin leer por julianferres_ »

Al menos uno
Avatar de Usuario
NPCPepe

FOFO 9 años - Mención Especial-FOFO 9 años COFFEE - Mención-COFFEE Matías Saucedo OFO - Medalla de Plata-OFO 2020 FOFO Pascua 2020 - Medalla-FOFO Pascua 2020 COFFEE - Mención-COFFEE Carolina González
COFFEE - Mención-COFFEE Ariel Zylber COFFEE - Mención-COFFEE Iván Sadofschi FOFO 10 años - Medalla-FOFO 10 años
Mensajes: 81
Registrado: Lun 17 Jun, 2019 9:22 pm
Medallas: 8
Nivel: 3
Ubicación: Argentina

Re: Selectivo de IMO 2018 - Problema 3

Mensaje sin leer por NPCPepe »

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 <span class="MathJax_Preview" style="color: inherit; display: none;"></span><span class="MathJax" id="MathJax-Element-11-Frame" tabindex="0" data-mathml="<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot ... /mn></math>" role="presentation" style="position: relative;"><nobr aria-hidden="true"><span class="math" id="MathJax-Span-69" style="width: 2.627em; display: inline-block;"><span style="display: inline-block; position: relative; width: 2.135em; height: 0px; font-size: 122%;"><span style="position: absolute; clip: rect(1.643em, 1002.13em, 2.791em, -999.996em); top: -2.537em; left: 0em;"><span class="mrow" id="MathJax-Span-70"><span class="mn" id="MathJax-Span-71" style="font-family: STIXGeneral;">2</span><span class="mo" id="MathJax-Span-72" style="font-family: STIXGeneral; padding-left: 0.25em;">×</span><span class="mn" id="MathJax-Span-73" style="font-family: STIXGeneral; padding-left: 0.25em;">2</span></span><span style="display: inline-block; width: 0px; height: 2.545em;"></span></span></span><span style="display: inline-block; overflow: hidden; vertical-align: -0.095em; border-left: 0px solid; width: 0px; height: 1.105em;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation"><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 <span class="MathJax_Preview" style="color: inherit; display: none;"></span><span class="MathJax" id="MathJax-Element-12-Frame" tabindex="0" data-mathml="<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot ... /mn></math>" role="presentation" style="position: relative;"><nobr aria-hidden="true"><span class="math" id="MathJax-Span-74" style="width: 2.627em; display: inline-block;"><span style="display: inline-block; position: relative; width: 2.135em; height: 0px; font-size: 122%;"><span style="position: absolute; clip: rect(1.643em, 1002.13em, 2.791em, -999.996em); top: -2.537em; left: 0em;"><span class="mrow" id="MathJax-Span-75"><span class="mn" id="MathJax-Span-76" style="font-family: STIXGeneral;">2</span><span class="mo" id="MathJax-Span-77" style="font-family: STIXGeneral; padding-left: 0.25em;">×</span><span class="mn" id="MathJax-Span-78" style="font-family: STIXGeneral; padding-left: 0.25em;">2</span></span><span style="display: inline-block; width: 0px; height: 2.545em;"></span></span></span><span style="display: inline-block; overflow: hidden; vertical-align: -0.095em; border-left: 0px solid; width: 0px; height: 1.105em;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation"><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 <span class="MathJax_Preview" style="color: inherit; display: none;"></span><span class="MathJax" id="MathJax-Element-13-Frame" tabindex="0" data-mathml="<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot ... /mi></math>" role="presentation" style="position: relative;"><nobr aria-hidden="true"><span class="math" id="MathJax-Span-79" style="width: 0.906em; display: inline-block;"><span style="display: inline-block; position: relative; width: 0.742em; height: 0px; font-size: 122%;"><span style="position: absolute; clip: rect(1.889em, 1000.74em, 2.791em, -999.996em); top: -2.537em; left: 0em;"><span class="mrow" id="MathJax-Span-80"><span class="mi" id="MathJax-Span-81" style="font-family: STIXGeneral; font-style: italic;">m</span></span><span style="display: inline-block; width: 0px; height: 2.545em;"></span></span></span><span style="display: inline-block; overflow: hidden; vertical-align: -0.095em; border-left: 0px solid; width: 0px; height: 0.705em;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation"><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 <span class="MathJax_Preview" style="color: inherit; display: none;"></span><span class="MathJax" id="MathJax-Element-14-Frame" tabindex="0" data-mathml="<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot ... rac></math>" role="presentation" style="position: relative;"><nobr aria-hidden="true"><span class="math" id="MathJax-Span-82" style="width: 3.119em; display: inline-block;"><span style="display: inline-block; position: relative; width: 2.545em; height: 0px; font-size: 122%;"><span style="position: absolute; clip: rect(0.66em, 1002.54em, 2.791em, -999.996em); top: -2.127em; left: 0em;"><span class="mrow" id="MathJax-Span-83"><span class="mfrac" id="MathJax-Span-84"><span style="display: inline-block; position: relative; width: 2.381em; height: 0px; margin-right: 0.086em; margin-left: 0.086em;"><span style="position: absolute; clip: rect(3.037em, 1002.22em, 4.266em, -999.996em); top: -4.504em; left: 50%; margin-left: -1.143em;"><span class="mrow" id="MathJax-Span-85"><span class="msubsup" id="MathJax-Span-86"><span style="display: inline-block; position: relative; width: 1.48em; height: 0px;"><span style="position: absolute; clip: rect(3.283em, 1001.07em, 4.266em, -999.996em); top: -4.012em; left: 0em;"><span class="mn" id="MathJax-Span-87" style="font-size: 70.7%; font-family: STIXGeneral;">999</span><span style="display: inline-block; width: 0px; height: 4.02em;"></span></span><span style="position: absolute; top: -4.258em; left: 1.07em;"><span class="mn" id="MathJax-Span-88" style="font-size: 65.6%; font-family: STIXGeneral;">2</span><span style="display: inline-block; width: 0px; height: 4.02em;"></span></span></span></span><span class="mo" id="MathJax-Span-89" style="font-size: 70.7%; font-family: STIXGeneral;">+</span><span class="mn" id="MathJax-Span-90" style="font-size: 70.7%; font-family: STIXGeneral;">1</span></span><span style="display: inline-block; width: 0px; height: 4.02em;"></span></span><span style="position: absolute; clip: rect(3.283em, 1000.33em, 4.266em, -999.996em); top: -3.602em; left: 50%; margin-left: -0.16em;"><span class="mn" id="MathJax-Span-91" style="font-size: 70.7%; font-family: STIXGeneral;">2</span><span style="display: inline-block; width: 0px; height: 4.02em;"></span></span><span style="position: absolute; clip: rect(0.742em, 1002.38em, 1.316em, -999.996em); top: -1.307em; left: 0em;"><span style="display: inline-block; overflow: hidden; vertical-align: 0em; border-top: 1.3px solid; width: 2.381em; height: 0px;"></span><span style="display: inline-block; width: 0px; height: 1.07em;"></span></span></span></span></span><span style="display: inline-block; width: 0px; height: 2.135em;"></span></span></span><span style="display: inline-block; overflow: hidden; vertical-align: -0.595em; border-left: 0px solid; width: 0px; height: 2.205em;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation"><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 <span class="MathJax_Preview" style="color: inherit; display: none;"></span><span class="MathJax" id="MathJax-Element-15-Frame" tabindex="0" data-mathml="<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;><mrow class=&quot;MJX-TeXAtom-ORD&quot;><msup><mn>999</mn><mn>2</mn></msup><mo>&#x2212;</mo><mn>1</mn></mrow><mrow class=&quot;MJX-TeXAtom-ORD&quot;><mn>2</mn></mrow></math>" role="presentation" style="position: relative;"><nobr aria-hidden="true"><span class="math" id="MathJax-Span-92" style="width: 5.168em; display: inline-block;"><span style="display: inline-block; position: relative; width: 4.184em; height: 0px; font-size: 122%;"><span style="position: absolute; clip: rect(1.398em, 1004.18em, 2.955em, -999.996em); top: -2.537em; left: 0em;"><span class="mrow" id="MathJax-Span-93"><span class="texatom" id="MathJax-Span-94"><span class="mrow" id="MathJax-Span-95"><span class="msubsup" id="MathJax-Span-96"><span style="display: inline-block; position: relative; width: 1.971em; height: 0px;"><span style="position: absolute; clip: rect(3.119em, 1001.48em, 4.266em, -999.996em); top: -4.012em; left: 0em;"><span class="mn" id="MathJax-Span-97" style="font-family: STIXGeneral;">999</span><span style="display: inline-block; width: 0px; height: 4.02em;"></span></span><span style="position: absolute; top: -4.422em; left: 1.48em;"><span class="mn" id="MathJax-Span-98" style="font-size: 70.7%; font-family: STIXGeneral;">2</span><span style="display: inline-block; width: 0px; height: 4.02em;"></span></span></span></span><span class="mo" id="MathJax-Span-99" style="font-family: STIXGeneral; padding-left: 0.25em;">−</span><span class="mn" id="MathJax-Span-100" style="font-family: STIXGeneral; padding-left: 0.25em;">1</span></span></span><span class="texatom" id="MathJax-Span-101"><span class="mrow" id="MathJax-Span-102"><span class="mn" id="MathJax-Span-103" style="font-family: STIXGeneral;">2</span></span></span></span><span style="display: inline-block; width: 0px; height: 2.545em;"></span></span></span><span style="display: inline-block; overflow: hidden; vertical-align: -0.295em; border-left: 0px solid; width: 0px; height: 1.405em;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation"><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></span></span><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 <span class="MathJax_Preview" style="color: inherit; display: none;"></span><span class="MathJax" id="MathJax-Element-16-Frame" tabindex="0" data-mathml="<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot ... /mn></math>" role="presentation" style="position: relative;"><nobr aria-hidden="true"><span class="math" id="MathJax-Span-104" style="width: 4.512em; display: inline-block;"><span style="display: inline-block; position: relative; width: 3.693em; height: 0px; font-size: 122%;"><span style="position: absolute; clip: rect(1.398em, 1003.61em, 2.873em, -999.996em); top: -2.537em; left: 0em;"><span class="mrow" id="MathJax-Span-105"><span class="msubsup" id="MathJax-Span-106"><span style="display: inline-block; position: relative; width: 1.971em; height: 0px;"><span style="position: absolute; clip: rect(3.119em, 1001.48em, 4.266em, -999.996em); top: -4.012em; left: 0em;"><span class="mn" id="MathJax-Span-107" style="font-family: STIXGeneral;">999</span><span style="display: inline-block; width: 0px; height: 4.02em;"></span></span><span style="position: absolute; top: -4.422em; left: 1.48em;"><span class="mn" id="MathJax-Span-108" style="font-size: 70.7%; font-family: STIXGeneral;">2</span><span style="display: inline-block; width: 0px; height: 4.02em;"></span></span></span></span><span class="mo" id="MathJax-Span-109" style="font-family: STIXGeneral; padding-left: 0.25em;">+</span><span class="mn" id="MathJax-Span-110" style="font-family: STIXGeneral; padding-left: 0.25em;">1</span></span><span style="display: inline-block; width: 0px; height: 2.545em;"></span></span></span><span style="display: inline-block; overflow: hidden; vertical-align: -0.195em; border-left: 0px solid; width: 0px; height: 1.305em;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation"><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 <span class="MathJax_Preview" style="color: inherit; display: none;"></span><span class="MathJax" id="MathJax-Element-17-Frame" tabindex="0" data-mathml="<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot ... /mi></math>" role="presentation" style="position: relative;"><nobr aria-hidden="true"><span class="math" id="MathJax-Span-111" style="width: 0.906em; display: inline-block;"><span style="display: inline-block; position: relative; width: 0.742em; height: 0px; font-size: 122%;"><span style="position: absolute; clip: rect(1.889em, 1000.74em, 2.791em, -999.996em); top: -2.537em; left: 0em;"><span class="mrow" id="MathJax-Span-112"><span class="mi" id="MathJax-Span-113" style="font-family: STIXGeneral; font-style: italic;">m</span></span><span style="display: inline-block; width: 0px; height: 2.545em;"></span></span></span><span style="display: inline-block; overflow: hidden; vertical-align: -0.095em; border-left: 0px solid; width: 0px; height: 0.705em;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation"><math xmlns="http://www.w3.org/1998/Math/MathML"><mi ... an><script type="math/tex" id="MathJax-Element-17">m </script> entonces <span class="MathJax_Preview" style="color: inherit; display: none;"></span><span class="MathJax" id="MathJax-Element-18-Frame" tabindex="0" data-mathml="<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot ... /mn></math>" role="presentation" style="position: relative;"><nobr aria-hidden="true"><span class="math" id="MathJax-Span-114" style="width: 7.053em; display: inline-block;"><span style="display: inline-block; position: relative; width: 5.742em; height: 0px; font-size: 122%;"><span style="position: absolute; clip: rect(1.398em, 1005.66em, 2.873em, -999.996em); top: -2.537em; left: 0em;"><span class="mrow" id="MathJax-Span-115"><span class="mi" id="MathJax-Span-116" style="font-family: STIXGeneral; font-style: italic;">m</span><span class="mo" id="MathJax-Span-117" style="font-family: STIXGeneral; padding-left: 0.332em;">=</span><span class="msubsup" id="MathJax-Span-118" style="padding-left: 0.332em;"><span style="display: inline-block; position: relative; width: 1.971em; height: 0px;"><span style="position: absolute; clip: rect(3.119em, 1001.48em, 4.266em, -999.996em); top: -4.012em; left: 0em;"><span class="mn" id="MathJax-Span-119" style="font-family: STIXGeneral;">999</span><span style="display: inline-block; width: 0px; height: 4.02em;"></span></span><span style="position: absolute; top: -4.422em; left: 1.48em;"><span class="mn" id="MathJax-Span-120" style="font-size: 70.7%; font-family: STIXGeneral;">2</span><span style="display: inline-block; width: 0px; height: 4.02em;"></span></span></span></span><span class="mo" id="MathJax-Span-121" style="font-family: STIXGeneral; padding-left: 0.25em;">+</span><span class="mn" id="MathJax-Span-122" style="font-family: STIXGeneral; padding-left: 0.25em;">1</span></span><span style="display: inline-block; width: 0px; height: 2.545em;"></span></span></span><span style="display: inline-block; overflow: hidden; vertical-align: -0.195em; border-left: 0px solid; width: 0px; height: 1.305em;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation"><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 <span class="MathJax_Preview" style="color: inherit; display: none;"></span><span class="MathJax" id="MathJax-Element-19-Frame" tabindex="0" data-mathml="<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot ... /mn></math>" role="presentation" style="position: relative;"><nobr aria-hidden="true"><span class="math" id="MathJax-Span-123" style="width: 7.053em; display: inline-block;"><span style="display: inline-block; position: relative; width: 5.742em; height: 0px; font-size: 122%;"><span style="position: absolute; clip: rect(1.398em, 1005.66em, 2.955em, -999.996em); top: -2.537em; left: 0em;"><span class="mrow" id="MathJax-Span-124"><span class="mi" id="MathJax-Span-125" style="font-family: STIXGeneral; font-style: italic;">m</span><span class="mo" id="MathJax-Span-126" style="font-family: STIXGeneral; padding-left: 0.332em;">=</span><span class="msubsup" id="MathJax-Span-127" style="padding-left: 0.332em;"><span style="display: inline-block; position: relative; width: 1.971em; height: 0px;"><span style="position: absolute; clip: rect(3.119em, 1001.48em, 4.266em, -999.996em); top: -4.012em; left: 0em;"><span class="mn" id="MathJax-Span-128" style="font-family: STIXGeneral;">999</span><span style="display: inline-block; width: 0px; height: 4.02em;"></span></span><span style="position: absolute; top: -4.422em; left: 1.48em;"><span class="mn" id="MathJax-Span-129" style="font-size: 70.7%; font-family: STIXGeneral;">2</span><span style="display: inline-block; width: 0px; height: 4.02em;"></span></span></span></span><span class="mo" id="MathJax-Span-130" style="font-family: STIXGeneral; padding-left: 0.25em;">−</span><span class="mn" id="MathJax-Span-131" style="font-family: STIXGeneral; padding-left: 0.25em;">1</span></span><span style="display: inline-block; width: 0px; height: 2.545em;"></span></span></span><span style="display: inline-block; overflow: hidden; vertical-align: -0.295em; border-left: 0px solid; width: 0px; height: 1.405em;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation"><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 <span class="MathJax_Preview" style="color: inherit; display: none;"></span><span class="MathJax" id="MathJax-Element-20-Frame" tabindex="0" data-mathml="<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot ... /mn></math>" role="presentation" style="position: relative;"><nobr aria-hidden="true"><span class="math" id="MathJax-Span-132" style="width: 2.627em; display: inline-block;"><span style="display: inline-block; position: relative; width: 2.135em; height: 0px; font-size: 122%;"><span style="position: absolute; clip: rect(1.643em, 1002.13em, 2.791em, -999.996em); top: -2.537em; left: 0em;"><span class="mrow" id="MathJax-Span-133"><span class="mn" id="MathJax-Span-134" style="font-family: STIXGeneral;">2</span><span class="mo" id="MathJax-Span-135" style="font-family: STIXGeneral; padding-left: 0.25em;">×</span><span class="mn" id="MathJax-Span-136" style="font-family: STIXGeneral; padding-left: 0.25em;">2</span></span><span style="display: inline-block; width: 0px; height: 2.545em;"></span></span></span><span style="display: inline-block; overflow: hidden; vertical-align: -0.095em; border-left: 0px solid; width: 0px; height: 1.105em;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation"><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)
$3=569936821221962380720^3+(-569936821113563493509)^3+(-472715493453327032)^3$: esta es la tercer menor solucion descubierta para la ecuación $a^3+b^3+c^3=3$ , las otras dos son $1^3+1^3+1^3=3$ y $4^3+4^3+(-5)^3=3$
BrunZo

OFO - Medalla de Bronce-OFO 2018 FOFO 8 años - Mención Especial-FOFO 8 años OFO - Medalla de Plata-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 FOFO Pascua 2020 - Copa-FOFO Pascua 2020 FOFO 10 años - Copa-FOFO 10 años OFO - Medalla de Oro-OFO 2021 FOFO 11 años - Medalla-FOFO 11 años
OFO - Medalla de Oro-OFO 2022 FOFO Pascua 2022 - Medalla-FOFO Pascua 2022 FOFO 12 años - Medalla-FOFO 12 años OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años
OFO - Jurado-OFO 2024
Mensajes: 414
Registrado: Mar 21 Nov, 2017 8:12 pm
Medallas: 16
Nivel: 3

Re: Selectivo de IMO 2018 - Problema 3

Mensaje sin leer por BrunZo »

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í.
Responder