Palabras

marzo 28, 2007

En cierta ciudad hay solamente 3 letras y para cada n\geq 2 hay una mala palabra de largo n. Si una palabra contiene a una mala palabra entonces esta prohibida. El resto de las palabras estan permitidas. Probar que hay al menos 2^n palabras permitidas de largo n.

Solucion:

La idea es ir por induccion, pero “haciendo trampa”. Vamos a ir construyendo una familia de palabras permitidas tal que:

1) Hay 2^n palabras de largo n en la familia.
2) Cualquier segmento inicial de una palabra en la familia es a su vez una palabra en la familia.

Supongamos que ya construimos todas las palabras de largo menor a n de nuestra familia y veamos que podemos agregar 2^n palabras de largo n. Por la segunda condicion, estas deben obtenerse de una palabra de largo n-1 en la familia a la que le agregamos una letra al final. Como por hipotesis inductiva hay 2^{n-1} palabras de largo n-1 en la familia, entonces hay 3\cdot 2^{n-1} “candidatas”.

Por otro lado, entre estas candidatas hay varias que no son palabras permitidas. Mas precisamente, aquellas palabras que contienen una mala palabra que por la construccion debe usar la ultima letra (pues en caso contrario el segmento inicial de largo n-1 no seria una palabra permitida). Como para cada k hay una mala palabra de largo k y cada una de ellas mata a lo sumo 2^{n-k} candidatas (pues el segmento final de largo k debe ser la mala palabra y el segmento inicial de largo n-k debe estar en la familia). Luego la cantidad de candidatas que quedan es al menos

3\cdot2^{n-1}-2^{n-2}-2^{n-3}-...-2^2-2^1-2^0=2^n+1

Luego elegimos 2^n de estas y completamos el paso inductivo.

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: