Provincial 2018 - Nivel 3 - Problema 1

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

OFO - Medalla de Plata OFO - Medalla de Oro FOFO Pascua 2019 - Mención
Mensajes: 120
Registrado: Dom 14 Sep, 2014 2:30 pm
Medallas: 3
Nivel: 1

Provincial 2018 - Nivel 3 - Problema 1

Mensaje sin leer por Monazo » Sab 25 Ago, 2018 4:16 pm

En un tablero de $5$ $X$ $9$ se juega el siguiente juego. Inicialmente se colocan fichas en algunas casillas (ninguna casilla puede tener más de una ficha). Una $movida$ consiste en mover simultáneamente todas las fichas según las siguientes reglas.
$\bullet$ Cada ficha se mueve a una casilla vecina siempre que la casilla de llegada esté vacía al recibir la ficha y que al finalizar la movida en cada casilla haya a los sumo una ficha.
$\bullet$ Si una ficha se movió hacia $\uparrow$ ó $\downarrow$, luego se debe mover hacia $\rightarrow$ ó $\leftarrow$ en la siguiente movida y viceversa.
El juego termina cuando es imposible hacer una movida.
i) Demostrar que si inicialmente hay $33$ fichas el juego terminará.
ii) Demostrar que es posible ubicar $32$ fichas de modo que el juego no termine nunca.
$Nota.$ Dos casillas son vecinas si comparten un lado.

Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial OFO - Medalla de Oro
Mensajes: 1042
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 2
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Provincial 2018 - Nivel 3 - Problema 1

Mensaje sin leer por Gianni De Rico » Sab 25 Ago, 2018 11:12 pm

i)
Spoiler: mostrar
Pintamos así:
Provincial 2018 N3 P1.png
Notemos que cada $4$ turnos toda ficha debe pasar al menos una vez por una casilla verde, como hay $33$ fichas y $4$ turnos, por Palomar en algún turno hay $9$ fichas en casillas verdes. Nuevamente por Palomar, como hay $9$ fichas y $8$ casillas, entonces hay alguna casilla con $2$ fichas. Luego, el juego termina.
ii)
Spoiler: mostrar
Nos olvidamos de la última fila y la última columna. Nos queda un tablero de $4\times 8$, lo separamos en $8$ subtableros disjuntos de $2\times 2$. En cada subtablero hacemos rotar las fichas en sentido antihorario. Estos movimientos son válidos y cada subtablero de $2\times 2$ puede repetir su movimiento infinitamente. Como los subtableros son disjuntos, el juego no termina nunca.
No tienes los permisos requeridos para ver los archivos adjuntos a este mensaje.
[math]

Peznerd
Mensajes: 42
Registrado: Jue 07 Jul, 2016 1:04 pm
Nivel: 3
Contactar:

Re: Provincial 2018 - Nivel 3 - Problema 1

Mensaje sin leer por Peznerd » Mar 27 Ago, 2019 2:50 pm

Gianni De Rico escribió:
Sab 25 Ago, 2018 11:12 pm
i)
Spoiler: mostrar
Pintamos así:
Provincial 2018 N3 P1.png
Notemos que cada <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-40" style="width: 0.66em; display: inline-block;"><span style="display: inline-block; position: relative; width: 0.492em; height: 0px; font-size: 122%;"><span style="position: absolute; clip: rect(1.29em, 1000.46em, 2.459em, -1000em); top: -2.213em; left: 0em;"><span class="mrow" id="MathJax-Span-41"><span class="mn" id="MathJax-Span-42" style="font-family: MathJax_Main;">4</span></span><span style="display: inline-block; width: 0px; height: 2.213em;"></span></span></span><span style="display: inline-block; overflow: hidden; vertical-align: -0.1em; border-left: 0px solid; width: 0px; height: 1.026em;"></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">4</script> turnos toda ficha debe pasar al menos una vez por una casilla verde, como hay <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 ... /mn></math>" role="presentation" style="position: relative;"><nobr aria-hidden="true"><span class="math" id="MathJax-Span-43" style="width: 1.234em; display: inline-block;"><span style="display: inline-block; position: relative; width: 0.984em; height: 0px; font-size: 122%;"><span style="position: absolute; clip: rect(1.302em, 1000.94em, 2.481em, -1000em); top: -2.213em; left: 0em;"><span class="mrow" id="MathJax-Span-44"><span class="mn" id="MathJax-Span-45" style="font-family: MathJax_Main;">33</span></span><span style="display: inline-block; width: 0px; height: 2.213em;"></span></span></span><span style="display: inline-block; overflow: hidden; vertical-align: -0.127em; border-left: 0px solid; width: 0px; height: 1.038em;"></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-13">33</script> fichas y <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 ... /mn></math>" role="presentation" style="position: relative;"><nobr aria-hidden="true"><span class="math" id="MathJax-Span-46" style="width: 0.66em; display: inline-block;"><span style="display: inline-block; position: relative; width: 0.492em; height: 0px; font-size: 122%;"><span style="position: absolute; clip: rect(1.29em, 1000.46em, 2.459em, -1000em); top: -2.213em; left: 0em;"><span class="mrow" id="MathJax-Span-47"><span class="mn" id="MathJax-Span-48" style="font-family: MathJax_Main;">4</span></span><span style="display: inline-block; width: 0px; height: 2.213em;"></span></span></span><span style="display: inline-block; overflow: hidden; vertical-align: -0.1em; border-left: 0px solid; width: 0px; height: 1.026em;"></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-14">4</script> turnos, por Palomar en algún turno hay <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 ... /mn></math>" role="presentation" style="position: relative;"><nobr aria-hidden="true"><span class="math" id="MathJax-Span-49" style="width: 0.66em; display: inline-block;"><span style="display: inline-block; position: relative; width: 0.492em; height: 0px; font-size: 122%;"><span style="position: absolute; clip: rect(1.301em, 1000.45em, 2.481em, -1000em); top: -2.213em; left: 0em;"><span class="mrow" id="MathJax-Span-50"><span class="mn" id="MathJax-Span-51" style="font-family: MathJax_Main;">9</span></span><span style="display: inline-block; width: 0px; height: 2.213em;"></span></span></span><span style="display: inline-block; overflow: hidden; vertical-align: -0.127em; border-left: 0px solid; width: 0px; height: 1.039em;"></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-15">9</script> fichas en casillas verdes. Nuevamente por Palomar, como hay <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-52" style="width: 0.66em; display: inline-block;"><span style="display: inline-block; position: relative; width: 0.492em; height: 0px; font-size: 122%;"><span style="position: absolute; clip: rect(1.301em, 1000.45em, 2.481em, -1000em); top: -2.213em; left: 0em;"><span class="mrow" id="MathJax-Span-53"><span class="mn" id="MathJax-Span-54" style="font-family: MathJax_Main;">9</span></span><span style="display: inline-block; width: 0px; height: 2.213em;"></span></span></span><span style="display: inline-block; overflow: hidden; vertical-align: -0.127em; border-left: 0px solid; width: 0px; height: 1.039em;"></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-16">9</script> fichas y <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 ... /mn></math>" role="presentation" style="position: relative;"><nobr aria-hidden="true"><span class="math" id="MathJax-Span-55" style="width: 0.66em; display: inline-block;"><span style="display: inline-block; position: relative; width: 0.492em; height: 0px; font-size: 122%;"><span style="position: absolute; clip: rect(1.301em, 1000.45em, 2.481em, -1000em); top: -2.213em; left: 0em;"><span class="mrow" id="MathJax-Span-56"><span class="mn" id="MathJax-Span-57" style="font-family: MathJax_Main;">8</span></span><span style="display: inline-block; width: 0px; height: 2.213em;"></span></span></span><span style="display: inline-block; overflow: hidden; vertical-align: -0.127em; border-left: 0px solid; width: 0px; height: 1.039em;"></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-17">8</script> casillas, entonces hay alguna casilla con <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-58" style="width: 0.66em; display: inline-block;"><span style="display: inline-block; position: relative; width: 0.492em; height: 0px; font-size: 122%;"><span style="position: absolute; clip: rect(1.301em, 1000.44em, 2.459em, -1000em); top: -2.213em; left: 0em;"><span class="mrow" id="MathJax-Span-59"><span class="mn" id="MathJax-Span-60" style="font-family: MathJax_Main;">2</span></span><span style="display: inline-block; width: 0px; height: 2.213em;"></span></span></span><span style="display: inline-block; overflow: hidden; vertical-align: -0.1em; border-left: 0px solid; width: 0px; height: 1.013em;"></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-18">2</script> fichas. Luego, el juego termina.
ii)
Spoiler: mostrar
Nos olvidamos de la última fila y la última columna. Nos queda un tablero de <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-61" style="width: 2.627em; display: inline-block;"><span style="display: inline-block; position: relative; width: 2.131em; height: 0px; font-size: 122%;"><span style="position: absolute; clip: rect(1.29em, 1002.09em, 2.481em, -1000em); top: -2.213em; left: 0em;"><span class="mrow" id="MathJax-Span-62"><span class="mn" id="MathJax-Span-63" style="font-family: MathJax_Main;">4</span><span class="mo" id="MathJax-Span-64" style="font-family: MathJax_Main; padding-left: 0.222em;">×</span><span class="mn" id="MathJax-Span-65" style="font-family: MathJax_Main; padding-left: 0.222em;">8</span></span><span style="display: inline-block; width: 0px; height: 2.213em;"></span></span></span><span style="display: inline-block; overflow: hidden; vertical-align: -0.127em; border-left: 0px solid; width: 0px; height: 1.053em;"></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-19">4\times 8</script>, lo separamos en <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-66" style="width: 0.66em; display: inline-block;"><span style="display: inline-block; position: relative; width: 0.492em; height: 0px; font-size: 122%;"><span style="position: absolute; clip: rect(1.301em, 1000.45em, 2.481em, -1000em); top: -2.213em; left: 0em;"><span class="mrow" id="MathJax-Span-67"><span class="mn" id="MathJax-Span-68" style="font-family: MathJax_Main;">8</span></span><span style="display: inline-block; width: 0px; height: 2.213em;"></span></span></span><span style="display: inline-block; overflow: hidden; vertical-align: -0.127em; border-left: 0px solid; width: 0px; height: 1.039em;"></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">8</script> subtableros disjuntos de <span class="MathJax_Preview" style="color: inherit; display: none;"></span><span class="MathJax" id="MathJax-Element-21-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.131em; height: 0px; font-size: 122%;"><span style="position: absolute; clip: rect(1.301em, 1002.08em, 2.459em, -1000em); top: -2.213em; left: 0em;"><span class="mrow" id="MathJax-Span-70"><span class="mn" id="MathJax-Span-71" style="font-family: MathJax_Main;">2</span><span class="mo" id="MathJax-Span-72" style="font-family: MathJax_Main; padding-left: 0.222em;">×</span><span class="mn" id="MathJax-Span-73" style="font-family: MathJax_Main; padding-left: 0.222em;">2</span></span><span style="display: inline-block; width: 0px; height: 2.213em;"></span></span></span><span style="display: inline-block; overflow: hidden; vertical-align: -0.1em; border-left: 0px solid; width: 0px; height: 1.013em;"></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-21">2\times 2</script>. En cada subtablero hacemos rotar las fichas en sentido antihorario. Estos movimientos son válidos y cada subtablero de <span class="MathJax_Preview" style="color: inherit; display: none;"></span><span class="MathJax" id="MathJax-Element-22-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.131em; height: 0px; font-size: 122%;"><span style="position: absolute; clip: rect(1.301em, 1002.08em, 2.459em, -1000em); top: -2.213em; left: 0em;"><span class="mrow" id="MathJax-Span-75"><span class="mn" id="MathJax-Span-76" style="font-family: MathJax_Main;">2</span><span class="mo" id="MathJax-Span-77" style="font-family: MathJax_Main; padding-left: 0.222em;">×</span><span class="mn" id="MathJax-Span-78" style="font-family: MathJax_Main; padding-left: 0.222em;">2</span></span><span style="display: inline-block; width: 0px; height: 2.213em;"></span></span></span><span style="display: inline-block; overflow: hidden; vertical-align: -0.1em; border-left: 0px solid; width: 0px; height: 1.013em;"></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-22">2\times 2</script> puede repetir su movimiento infinitamente. Como los subtableros son disjuntos, el juego no termina nunca.
¿Qué significa disjunto? Me gustaría que me pases teoría sobre esa clase de palabras.
En "ii)" no dijiste dónde pusiste las fuchas, supongo que llenaste todos los subtableros de $2*2$
Creo que en "ii)" te confundís diciendo que las jugadas son válidas, porque claramente en ningún momento puede haber más de una ficha en una misma casilla.
Muy buena resolución en "i)" quedé flipando que usaste Palomar.

Responder