OMEO 2020 NB P3

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
Tomás Morcos Porras

COFFEE - Mención-COFFEE Matías Saucedo OFO - Mención-OFO 2020
Mensajes: 82
Registrado: Dom 13 Oct, 2019 5:04 pm
Medallas: 2
Nivel: 2
Ubicación: Córdoba, Córdoba

OMEO 2020 NB P3

Mensaje sin leer por Tomás Morcos Porras » Vie 07 Feb, 2020 3:02 pm

En un tablero de $3\times 3$ se tiene una serpiente. Una serpiente de longitud $k$ es un animal que inicialmente ocupa una tira ordenada de casillas distintas del tablero, a la que llamaremos $(s_1, s_2, . . . , s_k)$, de modo que las casillas $s_i$ y $s_{i+1}$ comparten un lado para todo $i = 1, 2, . . . , k−1$. Tras ser posicionada en el tablero, si la serpiente actualmente ocupa $(s_1, s_2, . . . , s_k$) y $s$ es una casilla desocupada que comparte un lado con $s_1$, la serpiente puede realizar un movimiento para pasar a ocupar $(s, s_1, . . . , s_{k−1})$. Decimos que la serpiente se dio vuelta si inicialmente ocupaba las casillas $(s_1, s_2, . . . , s_k)$ y tras realizar una serie de movimientos terminó ocupando las casillas $(s_k, s_{k−1}, . . . , s_1)$.
Hallar el entero más grande $k$ tal que se puede posicionar una serpiente en un tablero de
$3\times 3$ de longitud $k$ tal que esta pueda darse vuelta.
¡Feliz cumpleaños a todos los que cumplen hoy y feliz no cumpleaños a todos los que no cumplen hoy!

Avatar de Usuario
¿hola?

OFO - Mención-OFO 2016 OFO - Medalla de Bronce-OFO 2017 OFO - Medalla de Bronce-OFO 2018 OFO - Medalla de Plata-OFO 2019 OFO - Medalla de Oro-OFO 2020
COFFEE - Mención-COFFEE Ariel Zylber
Mensajes: 141
Registrado: Vie 01 Ene, 2016 1:12 am
Medallas: 6
Nivel: 3
Contactar:

Re: OMEO 2020 NB P3

Mensaje sin leer por ¿hola? » Dom 09 Feb, 2020 1:46 am

Spoiler: mostrar
El ejemplo con $k=5$ es sencillo, asi que demostraremos que si $k \geq 6$ no se podrá ubicar una serpiente y que se de vuelta.
Primero veamos que si se puede ubicar una serpiente de longitud $k$ y que se de vuelta entonces se puede ubicar una de longitud $k-1$ y que se de vuelta. Sean $p_1, p_2,... p_k$ las partes de la serpiente
Spoiler: mostrar
Vemos que en el ultimo movimiento la parte $p_i$ terminara en la casilla $s_{k-i+1}$ (ya que al principio estaba en $s_i$ y al final la serpiente se dio vuelta) por lo que en el penúltimo movimiento la parte $p_i$ estará en la casilla $s_{k-i}$ para $i \leq k-1$ y $p_k$ estará en una casilla que al principio estuvo vacía (ya que las casillas vacías del principio son las mismas y cuando $p_k$ se mueve nadie ocupara su posición), por lo que si hacemos este mismo recorrido sacando $p_k$ y obteniendo $k'=k-1$ tendremos que en este penúltimo movimiento la posición de la parte $p_i$ sera $s_{k'-i+1}$ con $i \leq k'$ por lo que la serpiente de longitud $k'=k-1$ y partes $p_1, p_2,... p_{k'}$ se habrá dado vuelta.
Por lo que resta demostrar que con $k=6$ no se puede dar vuelta una serpiente. Pintemos el tablero de ajedrez con esquinas negras. Ahora Procederemos a reducir al absurdo.
Es claro que la serpiente tendrá siempre $3$ partes de ella en casillas blancas y $3$ partes de ella en casillas negras y que ademas siempre habrá una casilla blanca vacía en el tablero (la que inicialmente esta vacía se llamara $s_v$ y pondremos inicialmente en ella una ficha $v$ en ella que se va a mover eventualmente y determinara que su casilla esta vacía). Ahora veamos como se mueven las partes $p_1, p_3, p_5$ y $v$ si están en casillas blancas y pasan dos movimientos (volviendo a casillas blancas), $p_5$ va a donde estaba $p_3$, $p_3$ a donde estaba $p_1$, $p_1$ a donde estaba $v$ (ya que no puede ir a donde estaba $p_5$ porque al realizar el segundo movimiento en ella esta $p_6$) y $v$ va a donde estaba $p_5$, osea el siguiente ciclo...
$v \rightarrow p_5 \rightarrow p_3 \rightarrow p_1 \rightarrow v$

Si $s_1$ es blanca
Spoiler: mostrar
Veamos que por el ciclo anterior y porque al empezar $p_1, p_3, p_5$ y $v$ están en $s_1, s_3, s_5$ y $s_v$ respectivamente (que son blancas) $p_1$ estará en $s_5$ si y solo si $p_3$ esta en $s_v$ pero en el penúltimo movimiento $p_1$ estará en $s_5$ y $p_3$ en $s_3$ lo que es absurdo.
si $s_1$ es negra
Spoiler: mostrar
Veamos que por el ciclo anterior y porque en el segundo movimiento $p_1, p_3, p_5$ y $v$ están en $s_v, s_2, s_4$ y $s_6$ respectivamente (que son blancas) $p_1$ estará en $s_6$ si y solo si $p_3$ esta en $s_v$ pero en el ultimo movimiento $p_1$ estará en $s_6$ y $p_3$ en $s_4$ lo que es absurdo.
Yes, he who

Avatar de Usuario
Marco V

OFO - Medalla de Bronce-OFO 2018 FOFO 8 años - Mención Especial-FOFO 8 años OFO - Mención-OFO 2019 FOFO Pascua 2019 - Mención-FOFO Pascua 2019 OFO - Mención-OFO 2020
Mensajes: 56
Registrado: Lun 07 Nov, 2016 3:08 pm
Medallas: 5
Nivel: Exolímpico

Re: OMEO 2020 NB P3

Mensaje sin leer por Marco V » Dom 09 Feb, 2020 5:29 pm

El enunciado está mal, se supone que la serpiente pueda llegar a ocupar el lugar en donde se encontraba la cola

Avatar de Usuario
¿hola?

OFO - Mención-OFO 2016 OFO - Medalla de Bronce-OFO 2017 OFO - Medalla de Bronce-OFO 2018 OFO - Medalla de Plata-OFO 2019 OFO - Medalla de Oro-OFO 2020
COFFEE - Mención-COFFEE Ariel Zylber
Mensajes: 141
Registrado: Vie 01 Ene, 2016 1:12 am
Medallas: 6
Nivel: 3
Contactar:

Re: OMEO 2020 NB P3

Mensaje sin leer por ¿hola? » Dom 09 Feb, 2020 6:14 pm

Marco V escribió:
Dom 09 Feb, 2020 5:29 pm
El enunciado está mal, se supone que la serpiente pueda llegar a ocupar el lugar en donde se encontraba la cola
F
5  
Yes, he who

Avatar de Usuario
Tomás Morcos Porras

COFFEE - Mención-COFFEE Matías Saucedo OFO - Mención-OFO 2020
Mensajes: 82
Registrado: Dom 13 Oct, 2019 5:04 pm
Medallas: 2
Nivel: 2
Ubicación: Córdoba, Córdoba

Re: OMEO 2020 NB P3

Mensaje sin leer por Tomás Morcos Porras » Lun 10 Feb, 2020 10:57 pm

Marco V escribió:
Dom 09 Feb, 2020 5:29 pm
El enunciado está mal, se supone que la serpiente pueda llegar a ocupar el lugar en donde se encontraba la cola
Em... Creo que dice eso.
¡Feliz cumpleaños a todos los que cumplen hoy y feliz no cumpleaños a todos los que no cumplen hoy!

Avatar de Usuario
¿hola?

OFO - Mención-OFO 2016 OFO - Medalla de Bronce-OFO 2017 OFO - Medalla de Bronce-OFO 2018 OFO - Medalla de Plata-OFO 2019 OFO - Medalla de Oro-OFO 2020
COFFEE - Mención-COFFEE Ariel Zylber
Mensajes: 141
Registrado: Vie 01 Ene, 2016 1:12 am
Medallas: 6
Nivel: 3
Contactar:

Re: OMEO 2020 NB P3

Mensaje sin leer por ¿hola? » Lun 10 Feb, 2020 11:59 pm

Tomás Morcos Porras escribió:
Lun 10 Feb, 2020 10:57 pm
Marco V escribió:
Dom 09 Feb, 2020 5:29 pm
El enunciado está mal, se supone que la serpiente pueda llegar a ocupar el lugar en donde se encontraba la cola
Em... Creo que dice eso.
Dice que $s_1$ se mueve a una casilla desocupada (no ocupada por su cola) con la que comparta un lado.
1  
Yes, he who

Avatar de Usuario
Tomás Morcos Porras

COFFEE - Mención-COFFEE Matías Saucedo OFO - Mención-OFO 2020
Mensajes: 82
Registrado: Dom 13 Oct, 2019 5:04 pm
Medallas: 2
Nivel: 2
Ubicación: Córdoba, Córdoba

Re: OMEO 2020 NB P3

Mensaje sin leer por Tomás Morcos Porras » Mar 11 Feb, 2020 1:29 am

¿hola? escribió:
Lun 10 Feb, 2020 11:59 pm
Tomás Morcos Porras escribió:
Lun 10 Feb, 2020 10:57 pm
Marco V escribió:
Dom 09 Feb, 2020 5:29 pm
El enunciado está mal, se supone que la serpiente pueda llegar a ocupar el lugar en donde se encontraba la cola
Em... Creo que dice eso.
Dice que $s_1$ se mueve a una casilla desocupada (no ocupada por su cola) con la que comparta un lado.
Dónde están los admins cuando uno los necesita (?
¡Feliz cumpleaños a todos los que cumplen hoy y feliz no cumpleaños a todos los que no cumplen hoy!

Responder