En el planeta Alfa usan un alfabeto de [math]100 letras. Una palabra es una secuencia de letras que satisface las siguientes dos condiciones:
No hay dos letras consecutivas iguales. Por ejemplo, [math]\text{BELLEZA} no es una palabra, porque tiene [math]\text{LL}, y [math]\text{COOPERAR} no es una palabra porque tiene [math]\text{OO}.
No hay dos letras distintas [math]\text{U} y [math]\text{V} que figuren en el orden [math]\text{UVUV}, ni siquiera si entre cada dos de ellas se intercalan otras letras. Por ejemplo, [math]\text{RESPUESTA} no es palabra porque tiene [math]\text{ESES}, y [math]\text{CINCUENTA} no es palabra porque tiene [math]\text{CNCN}.
Determinar la máxima longitud que puede tener una palabra.
Guía de $\LaTeX$ (sirve para escribir ecuaciones como $2^{3\times 2}+1=13\cdot 5$)
Cuando escribimos una palabra, si ya se escribieron [math]i letras, definimos [math]f(i) como la cantidad de letras que no pueden ocupar el lugar [math]i+1. Entonces, [math]f(0)=0 es la cantidad de letras "prohibidas" para ocupar el primer lugar de la palabra, [math]f(1) es la cantidad de letras "prohibidas" para el segundo lugar. Es claro que [math]f(1)=1 puesto que la única letra que no se puede usar es la que se colocó en el primer lugar.
Vamos a definir a la letra de una posición [math]i como "loquita" si nunca apareció antes en la palabra y como "cajetilla" si ya había aparecido en otras posiciones anteriores a [math]i.
Ahora, vamos a demostrar que para todo [math]i \geq 2, si la letra de la posición [math]i es "loquita", entonces [math]f(i) = f(i-1) y si es "cajetilla" entonces [math]f(i) \geq f(i-1)+1. Sea [math]a la letra de la posición [math]i-1 y [math]b la de la posición [math]i.
Si [math]b es "loquita", las letras prohibidas para la posición [math]i+1 son [math]b, para evitar [math]bb, más todas las que estaban prohibidas en [math]i para evitar [math]uvuv salvo [math]a que ya no está prohibida, asi que es [math]f(i) = 1+f(i-1)-1 = f(i-1).
Si [math]b es "cajetilla", las letras prohibidas para la posición [math]i+1 son [math]b, para evitar [math]bb, más todas las que estaban prohibidas para la posición [math]i para evitar [math]uvuv más la letra [math]a que estaba prohibida en la posición [math]i, ahora está prohibida para evitar [math]baba. Puede haber otras letras prohibidas, que ya aparecieron pero después de la primera vez que apareció [math]b. Entonces, [math]f(i) es al menos [math]1+f(i-1).
Si en una palabra se escribieron ya [math]k letras, con [math]k mayor que [math]100, al menos [math]k-100 de ellas son "cajetillas", por palomar. Entonces, [math]f(k) \geq 1+k-100 = k-99, puesto que [math]f(1)=1 y [math]f y como demostramos antes, aumentó por lo menos en [math]1 al pasar por cada letra "cajetilla". Si [math]k-99 \geq 100 significa que todas las letras del alfabeto este loco que tienen están prohibidas para la posición [math]k+1, entonces, si [math]k \geq 199 no se puede seguir. Por lo tanto, no existen palabras de más de [math]199 letras.
Ahora, con un ejemplo de palabra de [math]199 letras ya estamos:
Sean [math]a_1, \cdots , a_{100} las letras del alfabeto.
Un ejemplo de palabra es: [math]a_1 a_2 a_1 a_3 a_1 a_4 \cdots a_1 a_{99} a_1 a_{100} a_1
Y así acabamos la solución.
Siendo [math]n el numero de letras que se permiten en una palabra.
A simple vista se puede notar que [math]n \geqslant 100, puesto que el numero de letras de las que se dispone es [math]100
Luego, al ir agregando letras repetidas: ([math]A en este caso), se puede ver que aparecen distintas formas de distribuirlos
1)[math]AA\cdots
2)[math]A \cdots A\cdots
3)[math]A \cdots A
Las formas 2 y 3 son las que se permiten.
Añadiendo otra letra [math]B se puede hacer de la forma:
1)[math]AB\cdots B
2)[math]AB\cdots B\cdots
Ambas se pueden
Si añado otra letra [math]A: (las aparente mente permitidas son)
1)[math]A \cdots A \cdots A\cdots
2)[math]A \cdots A \cdots A
Y de esta forma ninguna de las 2 formas puede permitirse, porque se repite en forma [math]AA-AA (La tercer [math]A comparte 2 pares)
Pero en el caso de añadir 2 letras ya sabemos que no puenden se iguales (explicado anteriormente).
1)[math]ABC \cdots AB
2)[math]ABC \cdots AC
3)[math]ABC \cdots BA
4)[math]ABC \cdots CA
Se puede ver que se deben poner en orden inverso a como empiezan.
Siguiendo...
1)[math]ABC \cdots CBA
2)[math]ABCD \cdots DCBA
3)etc..
Entonces se puede hacer:
*Solo en orden inverso
*Una letra no se repite más de 2 veces
Si seguimos de esta forma llegaremos a usar las 100 letras hasta que llegemos a: [math]ABCD \cdots XYZZYX \cdots CBA
Por lo que la ultima letra no se podrá repetir.
Tampoco se puede añadir otra letra más o cambiar la letra del medio por otra, porque nos quedaría 3 letras iguales.
Entonces el maximo de letras que puede tener una palabra es 199.
Bueno, no es una explicacion muy matematica pero quería ver si había otra forma de explicarlo.
Lo que hiciste es encontrar un ejemplo con [math]199 que no se puede extender agregando letras o cambiando una letra por otra, pero eso no quiere decir que no exista un ejemplo con [math]200 o más letras. Lo que pide el problema es demostrar eso, que no puede haber una palabra con más de [math]199 letras.
Guía de $\LaTeX$ (sirve para escribir ecuaciones como $2^{3\times 2}+1=13\cdot 5$)
Afirmación: Una palabra válida en un alfabeto de $k$ letras tiene longitud a lo sumo $2k-1$.
Lo vamos a probar por inducción (o sea suponemos que vale para todos los numeros menores o iguales que $n-1$ y lo probamos para $n$).
Para $n=1$ es claro que vale la afirmación.
Supongamos que la afirmación vale para todos los números menores o iguales a $n$.
Sea $P$ una palabra válida cualquiera en un alfabeto de $n$ letras. Vamos a construir una palabra válida $Q$ de la misma longitud donde cada letra se use a lo sumo $2$ veces.
Supongamos que una letra $L$ aparece más de $2$ veces en la palabra $P$. Entonces se puede escribir del siguiente modo:
$P= \text{Pedazo}_1 \: L \: \text{Pedazo}_2 \: L \: \text{Pedazo}_3 \: L \: \text{Pedazo}_4$
donde los pedazos $2$ y $3$ no son la palabra vacía (los pedazos $1$ y $4$ pueden ser vacíos). Además supongamos que la letra $L$ no aparece en $\text{Pedazo}_2$.
El siguiente paso es construir una palabra de la misma longitud que $P$ donde la letra $L$ aparezca una vez menos que en $P$.
Supongamos que las letras que aparecen en $\text{Pedazo}_2$ son $L_1, \ldots L_k$.
Tenemos que $\text{Pedazo}_2$ es una palabra válida (por ser subpalabra de $P$). Además $k<n$, ya que por ejemplo la letra $L$ no aparece en $\text{Pedazo}_2$. Entonces podemos usar la hipótesis inductiva, y tenemos que $\left|\text{Pedazo}_2\right|\leq 2k-1$ (las barritas quieren decir "cantidad de letras").
Notemos que las letras $L_i$ no pueden aparecer en otra parte de la palabra que no sea $\text{Pedazo}_2$, ya que $P$ es válida.
Consideremos la palabra
$P'=L_1\ldots L_k \: \text{Pedazo}_1 \: L \: \text{Pedazo}_3 \: L \: \text{Pedazo}_4 \: L_k\ldots \L_1$
Notemos que $P'$ es una palabra válida (es algo medio molesto de chequear pero sale).
Además notemos que $\left|P\right|\leq \left|P'\right|$ (las barritas significan cantidad de letras).
Entonces construimos una palabra $P'$ donde la letra $L$ aparece exactamente una vez menos que en $P$, con más letras que $P$.
Haciendo esto repetidas veces llegamos a una palabra $Q$ donde cada letra aparece a lo sumo dos veces, que tiene mayor o igual longitud que $P$.
Entonces probamos que si $P$ es una palabra en un alfabeto de $n$ letras hay una palabra $Q$ que tiene al menos tantas letras como $P$ y donde cada letra aparece a lo sumo dos veces (o sea probamos que $\left|P\right|\leq 2n$).
Veamos que ese $2n$ se puede cambiar por un $2n-1$, que es lo que queremos para completar el paso inductivo.
Supongamos que
$Q= M_1\ldots M_k \: M_{k+1}\ldots M_r$
con las primeras $k$ letras todas distintas y la letra $k+1$ igual a una letra anterior, digamos $j$.
Afirmo que la letra $M_k$ aparece exactamente una vez en $Q$. En efecto si apareciera de nuevo seria en una posición mayor a $k+1$, digamos $t$ y tendríamos la subpalabra: $M_j \: M_k \: M_{k+1} \: M_t$, pero esa subpalabra estaba prohibida.
Entonces sigue que una de las letras de $Q$ aparece una vez, y tenemos la cota $\left| P \right|\leq \left| Q\right| \leq 2n-1$, que completa la inducción
Veamos que si tenemos el par de letras AB...AB no cumplimos con la segunda consigna, sin embargo podemos poner AB...BA sin ningún problema, logrando así, tener 2 letras de cada una.
Primero ponemos
AB
Ahora agregamos la siguiente letra, es decir C, y completamos el primer par:
AB |C| BA
Hasta ahora tenemos 2 letras de A y 2 de B. Si seguimos completando siguiendo la misma idea llegamos a esto:
AB |C| BA D|E| DC F |G| FE...
El objetivo de esta distribución es tener 2 letras iguales de cada una.
Los números |n| son los que uso para evitar tener UVVU juntos, ya que no puede haber dos letras iguales consecutivas
Cuando llegamos al final por quedarnos sin letras va a pasar esto:
YZ |?| ZY
Claro, como nos quedamos sin letras no podemos evitar el caso de tener dos letras consecutivas YZZY. Entonces lo que vamos a hacer es sacar la ultima Z. Finalmente nos queda que cada letra se repite 2 veces (Salvo la ultima) y tenemos 100 letras, por lo tanto $2.100-1 = 199$ es máxima cantidad de letras.
Nota final: Para separar n letras iguales necesitamos n-1 de otro tipo de letra, por lo tanto si n es mayor que 3 vamos a necesitar 2 letras, lo cual implica que en el final de la palabra tengamos que quitar 2 letras en vez de una sola.
