Mateclubes 2019 - Nivel 5 - Problema 3

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: 159
Registrado: Dom 14 Sep, 2014 2:30 pm
Medallas: 3
Nivel: 1

Mateclubes 2019 - Nivel 5 - Problema 3

Mensaje sin leer por Monazo » Lun 02 Dic, 2019 11:53 am

En la ciudad de Biletralandia, las palabras están formadas únicamente por letras $A$ y $B$. En dicha ciudad, todas las palabras cumplen las siguientes propiedades:

$\ \ \ $ $\bullet$ Tienen $2019$ letras.
$\ \ \ $ $\bullet$ Ningún fragmento de la palabra es ABAB.

Todas las palabras que se pueden formar con esas propiedades existen en el idioma de Biletralandia. ¿La cantidad de palabras en el idioma de Biletralandia es par o impar?

Avatar de Usuario
Monazo

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

Re: Mateclubes 2019 - Nivel 5 - Problema 3

Mensaje sin leer por Monazo » Lun 02 Dic, 2019 8:45 pm

Uno de los problemas que más me gustó de la competencia!!
Spoiler: mostrar

Vamos a construirnos lo que se denomina una "Biyección". En la explicación voy a saltearme algunas formalidades pero quiero que el concepto quede para la resolución de otros problemas, porque es una idea que suele aparecer en varias pruebas.

Supongamos que tenemos una palabra la cual vamos a llamar $X$. Vamos a construirnos una operación $f(X)$ que realice las dos siguientes operaciones en simultáneo.

$\bullet$ Invertir cada letra. Es decir, cambiar las letras $A$ por las $B$ y viceversa.
$\bullet$ Dar vuelta la palabra. Es decir, la letra que ocupa la posición $j$, ahora ocupará la posición $2020-j$ con $1\leq j \leq 2019$. Más sencillo, escribir la palabra de derecha a izquierda.

Podemos notar las siguientes propiedades:

$1)$ $X \neq f(X)$. Es decir, no podemos obtener la misma palabra después de realizar la operación. Esto es debido a que la letra de la posición $1010$, al realizar la primera operación, tomará otro valor, pero cuando realizamos la segunda operación, ocupará la posición $1010$ nuevamente.
Fijense que $1010 = 2020 - 1010$. Por lo tanto vamos a estar seguros, que la palabra va a ser distinta al aplicar la operación, porque la letra de la posición $1010$ será otra.

$2)$ Si realizamos una operación en una palabra, y volvemos a realizar la operación en el resultado, obtenemos la palabra inicial, es decir, $f(f(X)) = X$ Es bastante intuitivo ver esta propiedad. Vemos que al invertir el valor de la letra $2$ veces, cada letra va a tomar su valor inicial (pueden pensar las letras como $1$ si es $A$ o $-1$ si es $B$, y la operación de invertir es multiplicar por $-1$, por lo tanto multiplicar dos veces por $-1$ es lo mismo que multiplicar por $1$). Y también las letras vuelven a su valor inicial, porque la posición sería $2019-(2019-j) = j$.

$3)$ Si la palabra contiene en algún intervalo $ABAB$, podemos notar que $f(X)$ también contendrá $ABAB$. También podemos decir que si la palabra no lo contiene, entonces $f(X)$ tampoco la contendrá.

Teniendo esto, es aquí que obtenemos la "Biyección". Podemos ver que a cada palabra le podemos asignar otra como su "parejita". Es decir las parejas estarán formada por $(X,f(x))$. Y aquí es donde muere el problema, como a cada palabra que contiene $ABAB$, le encontramos otra que también contiene $ABAB$, por lo tanto, como las soluciones aparecen "de a pares", podemos garantizar que la cantidad de combinaciones será PAR.



1  

Responder