Provincial 2019 - Nivel 3 - Problema 2

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 2019 - Nivel 3 - Problema 2

Mensaje sin leer por Monazo » Jue 29 Ago, 2019 10:54 pm

Julián tiene en la mano un mazo con $52$ cartas, todas boca abajo, y realiza la siguiente operación: toma las primeras $7$ cartas del mazo, las da vuelta, y las coloca al fondo del mazo (esas $7$ están boca arriba). Así las $52$ cartas están nuevamente en una única pila, algunas boca abajo y otras boca arriba. Julián repite esta operación: "toma las $7$ cartas de arriba, las da vuelta y las coloca al fondo del mazo".
Determinar la menos cantidad de operaciones que debe hacer para lograr que todas las cartas que vuelvan a quedar boca abajo (como al inicio del juego).

Avatar de Usuario
¿hola?

OFO - Mención OFO - Medalla de Bronce OFO - Medalla de Plata
Mensajes: 99
Registrado: Vie 01 Ene, 2016 1:12 am
Medallas: 4
Nivel: 3

Re: Provincial 2019 - Nivel 3 - Problema 2

Mensaje sin leer por ¿hola? » Sab 07 Sep, 2019 7:05 pm

Spoiler: mostrar
Sean $1,2,3,...,52$ las posiciones de las cartas en la pila y sera el turno $t$ luego de aplicar $t$ operaciones. Veamos que la carta que esta en la posición $46,47,48,49,50,51$ ó $52$ van a la posición $7,6,5,4,3,2$ ó $1$ respectivamente, luego de aplicar una operación (y cambian de estado), ademas luego de esta operación las cartas en las posiciones $x$ en $1,2,...,45$ van a la posición $x+7$ ya que introducimos $7$ cartas bajo ellas (no cambian estado). Ahora es fácil ver que los restos (modulo $7$) de las posiciones de una carta en una posición de resto $r$ (modulo $7$) después de varias operaciones serán alguno de los siguientes ciclos

$1$-ciclo $r= 4 \rightarrow 4 \rightarrow ... \rightarrow 4 \rightarrow 0 \rightarrow 0 \rightarrow ... \rightarrow 0 \rightarrow 4 \rightarrow ... $
$2$-ciclo $r= 5 \rightarrow 5 \rightarrow ... \rightarrow 5 \rightarrow 6 \rightarrow 6 \rightarrow ... \rightarrow 6 \rightarrow 5 \rightarrow ... $
$3$-ciclo $r= 1 \rightarrow 1 \rightarrow ... \rightarrow 1 \rightarrow 3 \rightarrow 3 \rightarrow ... \rightarrow 3 \rightarrow 1 \rightarrow ... $
$4$-ciclo $r= 2 \rightarrow 2 \rightarrow ... \rightarrow 2 \rightarrow ...$

Ya que una carta en la posición de resto $r$ recorrerá todas las posiciones de resto $r$ hasta llegar a una de las posiciones $46,47,48,49,50,51$ ó $52$
y luego recorrerá todas las congruencias de resto $r´$ desde la posición $7,6,5,4,3,2$ ó $1$ respectivamente y vemos que en todos los casos hay un ciclo de $r$ a $r´$ a $r$.

La carta inicialmente en la posición $1$ tendrá el estado de "boca abajo" durante los turnos congruentes con $0,1,2,3,4,5,6,7$ modulo $16$, ya que el $3$-ciclo tiene $16$ elementos y después de $8$ turnos estará en la posición $3$ con el estado "boca arriba", análogamente la carta inicialmente en la posición $50$ estará en el estado "boca abajo" durante los turnos congruentes con $0,9,10,11,12,13,14,15$ modulo $16$, deducimos que ambas cartas estarán "boca abajo" si y solo si el turno es múltiplo de $16$.

La carta inicialmente en la posición $4$ tendrá el estado de "boca abajo" durante los turnos congruentes con $0,1,2,3,4,5,6$ modulo $14$, ya que el
$1$-ciclo tiene $14$ elementos y después de $7$ turnos estará en la posición $7$ con el estado "boca arriba", análogamente la carta inicialmente en la posición $46$ estará en el estado "boca abajo" durante los turnos congruentes con $0,8,9,10,11,12,13$ modulo $14$, deducimos que ambas cartas estarán "boca abajo" si y solo si el turno es múltiplo de $14$.

Luego, el mínimo turno múltiplo de $14$ y $16$ es $112$, es claro que después de $112$ operaciones todas las cartas estarán "boca abajo" ya que en cada ciclo luego de $14,14,16$ y $16$ operaciones respectivamente cada carta estará nuevamente en su posición inicial y con su estado inicial.

comenterio: vemos que después de $112$ operaciones las cartas no solo están boca abajo sino que en el mismo orden que al principio y también es el mínimo turno para esto.
2  
Yes, he who

Responder