Olimpiada de Mayo - 2017 N2P5

Avatar de Usuario
Violeta

OFO - Mención FOFO 7 años - Medalla Especial OFO - Medalla de Bronce
Mensajes: 389
Registrado: Sab 04 Jun, 2016 11:50 pm
Medallas: 3
Ubicación: Puerto Rico

Olimpiada de Mayo - 2017 N2P5

Mensaje sin leer por Violeta » Mar 30 May, 2017 8:12 pm

Ababa juega un juego con las letras de su nombre:

Si hay un AB, lo puede reemplazar por BAA.

Si hay dos Bs consecutivas, las puede borrar.

Si hay tres As consecutivas, las puede borrar.

Si al comenzar el juego está la secuencia ABABABAABAAB, hallar la menor cantidad de letras que pueden haber en el juego en cualquier momento y explicar por qué no pueden haber menos.
Para todo [math], existen [math] primos en sucesión aritmética.

Avatar de Usuario
enigma1234

OFO - Medalla de Oro
Mensajes: 47
Registrado: Sab 03 Jun, 2017 8:07 pm
Medallas: 1
Nivel: 2

Re: Olimpiada de Mayo - 2017 N2P5

Mensaje sin leer por enigma1234 » Dom 04 Jun, 2017 10:06 pm

Spoiler: mostrar
veamos que Ababa puede obtener una palabra de 2 letras de la siguiente forma:
ABABABAABAAB [math] BAAABABAABAAB [math] BBABAABAAB [math] ABAABAAB [math] BAAAABAAB [math] BABAAB [math] BBAAAAB [math] BBAB [math] AB
Ahora veamos que necesariamente debe haber al menos un A y al menos un B en cualquier palabra a la que pueda llegar Ababa,con lo que tendríamos lo pedido
Llamemos jugada 1,2 y 3 a las posibles jugadas de Ababa en el orden en el que aparecen en el problema
(1)Hay al menos un B:
Veamos que al realizar la jugada 1 o 3 no cambia la cantidad de B's ,y que al realizar la jugada 2 la cantidad de B's disminuye en 2,de esto tenemos que la cantidad de B's siempre mantiene su paridad y como empieza con 5 B's entonces la cantidad de B's siempre es impar y tenemos lo que queríamos.
(2)Hay al menos un A:
Sea X una palabra posible,y llamemos a los B's como [math],[math],...,[math] de izquierda a derecha,y llamemos [math],[math],...,[math] a la cantidad de A's entre dos B's consecutivos(o a la izquierda del primero([math]) o a la derecha del ultimo([math])) en ese orden, ahora consideremos [math]=[math] en [math],
es claro que empezamos con [math]=[math] en la primera palabra,ahora veamos que [math] no varia con cualquier jugada,esto porque con la jugada 1 y 3 la suma varia en 3 o -3 y como [math] esta en [math] no varia,realiza la jugada 2,entonces como se eliminan 2 B's seguidos(digamos [math] y [math]) entonces [math] se suma a [math] y al ser [math]=0 la suma no varia se mantiene [math].
Entonces [math] no varia [math] es decir luego de cualquier cantidad de jugadas [math] lo cual no seria posible si la cantidad de A's fuera 0,dado que en este caso [math] y habría contradicción,entonces siempre hay al menos un A luego de cualquier cantidad de jugadas realizadas por Ababa
entonces siempre hay al menos un A y al menos un B con lo que tendríamos que el mínimo numero de letras que pueden haber en el juego en cualquier momento es 2, con el ejemplo inicial acaba el problema.
One in a millon...my lucky strike! :D

Avatar de Usuario
Joacoini

OFO - Medalla de Plata
Mensajes: 83
Registrado: Jue 12 Oct, 2017 10:17 pm
Medallas: 1
Nivel: 2

Re: Olimpiada de Mayo - 2017 N2P5

Mensaje sin leer por Joacoini » Sab 28 Jul, 2018 1:40 am

Spoiler: mostrar
Vamos a darle un valor a la palabra dependiendo de sus letras.
La $A$ le suma un punto a la palabra.
La $B$ le suma a la palabra lo que está a la izquierda de la $B$, unos ejemplos:
$BAA$, acá la $B$ tiene un valor de 0.
$ABAAA$, acá la $B$ tiene un valor de 1.
$AAABA$, acá la $B$ tiene un valor de 3.
$AABAAAB$, acá la última $B$ tiene un valor de 7.

Cuando borramos 3 $A$s, si estás tienen $n$ $B$s a la derecha, le restamos $3×2^n$ a la palabra (la primera $B$ se le bajan 3 puntos por perder a las $A$, la segunda se le bajan 3 por perder a las $A$ y 3 porque bajo la $B$ de la izquierda y así).

Cuando borramos 2 $B$s, si la de la izquierda tiene un puntaje de $N$ la de la derecha tendrá un puntaje de $2N$ (los primeros $N$ puntos los consigue de lo que está a la izquierda de la $B$ que tiene a la izquierda y los otros $N$ de la $B$ que tiene a la izquierda) y si a la derecha de las 2 $B$s hay $n$ $B$s, le restamos $3N×2^n$ a la palabra (la primera $B$ se le bajan $3N$ puntos por perder a las $B$s, la segunda se le bajan $3N$ por perder a las $B$s y $3N$ porque bajo la $B$ de la izquierda y así).

Pasar de $AB$ a $BAA$ no altera el puntaje porque a la $B$ se me resta un punto el cual se recupera al agregar una $A$.

Todas las acciones que ejercemos mantiene la congruencia en módulo 3 y como la palabra original tiene un puntaje congruente a 2 en mod 3 (68 para ser exactos) está congruencia es invariante y las palabras más cortas con la misma congruencia son $AA$ y $AB$ ambas de 2 dígitos.
2  
NO HAY ANÁLISIS.

Responder