CLASE 1 - LUNES 09-08-21 - EJERCICIOS DE CLASE

SAVE OFFLINE

´ COMBINATORIA - CONTEO BASICO Ejercicios realizados en la 1◦ Clase - Lunes 09/08/21 Ejemplo 1 Una peluquer´ıa para mascotas ofrece cortes para gatos y perros. Para perros ofrece tres opciones distintas para la cola, tres para las patas, dos para la cabeza y dos para el resto del cuerpo. Para gatos ofrece dos opciones para la cola, dos para la cabeza y una u ´nica opci´ on para el resto del cuerpo. ¿Cu´ antos tipos de corte ofrece la peluquer´ıa en total? Resoluci´ on: Definamos el conjunto C cuyos elementos son los distintos tipos de cortes que realiza la peluquer´ıa de mascotas. Como se ofrecen cortes para gatos y para perros, definamos los subcojuntos G cuyos elementos son los distintos tipos de cortes para gatos, y P formado por los distintos tipos de cortes para perros que se realizan en la peluquer´ıa. Notemos que P ∪ G = C y que P ∩ G = ∅, es decir, los subconjuntos G y P son una partici´ on del conjunto C, por lo tanto usando el principio aditivo se tiene que |C| = |G| + |P | . Calculemos cada cardinal para as´ı obtener la respuesta del ejercicio. ˆ |G| =?

Para gatos se ofrecen dos opciones de cortes para la cola, dos para la cabeza y una u ´nica opci´on para el resto del cuerpo. Como hay independencia entre qu´e opci´on se tome para una parte del cuerpo, respecto al tipo de corte de otra parte del cuerpo del animal, por principio multiplicativo se tiene que |G| = 2 · 2 · 1 = 4. ˆ |P | =?

Para perros se ofrecen tres opciones distintas para la cola, tres para las patas, dos para la cabeza y dos para el resto del cuerpo. Como hay independencia entre qu´e opci´on se tome para una parte del cuerpo, respecto al tipo de corte de otra parte del cuerpo, usando el principio multiplicativo se tiene que |P | = 3 · 3 · 2 · 2 = 36.

Finalmente usando el principio aditivo se tiene que |C| = |G| + |P | = 4 + 36 = 40

Ejemplo 2 Se sabe que en un determinado diccionario hay 1300 palabras con una u ´nica letra “a”, 4000 con dos letras “a” y 12000 con m´ as de dos “a”. Si el diccionario contiene 80000 palabras ¿Cuantas de ellas no contienen la letra “a”? Resoluci´ on: Comencemos definiendo los siguientes conjuntos: ˆ Sea S el conjunto de todas las palabras del diccionario. ˆ Sea A el conjunto de todas las palabras del diccionario que contienen la letra “a” al menos una vez. ˆ Sea A1 el conjunto de todas las palabras del diccionario que contienen la letra “a” exactamente una vez. ˆ Sea A2 el conjunto de todas las palabras del diccionario que contienen la letra “a” exactamente dos veces. ˆ Sea A3 el conjunto de todas las palabras del diccionario que contienen la letra “a” m´ as de dos veces.

Notemos que lo que buscamos calcular es el cardinal de A. Cabe aclarar que A est´ a definido con respecto a S de la siguiente forma A = {x ∈ S : x ∈ / A}. Sabemos por principio de sustracci´on que |A| = |S| − |A|. Por enunciado sabemos que |S| = 80000 con lo cual nos resta calcular |A|. Es claro que si una palabra tiene al menos una “a” tendr´a una, dos o m´as de dos. Es decir, ocurre que A = A1 ∪ A2 ∪ A3 . Por otro lado notemos que si una palabra tiene exactamente una “a” no tendr´a ni dos ni m´as de dos, asimismo, si tiene exactamente dos “a” no tendr´a exactamente una ni m´as de dos y finalmente si tiene m´as de dos no tendr´a ni una ni dos. Es decir, ocurre que A1 ∩ A2 = ∅, A1 ∩ A3 = ∅ y A2 ∩ A3 = ∅. Con estas observaciones es claro que A1 , A2 y A3 forman una partici´on de A. Luego, por principio aditivo resulta que |A| = |A1 | + |A2 | + |A3 |. Por enunciado tenemos que |A1 | = 1300, |A2 | = 4000 y |A3 | = 12000. Con lo cual resulta que |A| = 1300 + 4000 + 12000 = 17300.

Finalmente |A| = 80000 − 17300 = 62700 . Ejemplo 3 Una p´ agina web requiere del uso de una contrase˜ na de 6 caracteres. Los mismos pueden ser letras (may´ usculas o min´ usculas) de un abecedario de 26 letras. ¿Cu´ antas contrase˜ nas posibles hay que no contengan exactamente una letra “f ”? Comencemos notando que la clave se conforma con 6 caracteres elegidos de un conjunto de 52 elementos (las 26 letras del abecedario en min´ usculas y las 26 letras en may´ usculas). Denominemos U al conjunto de claves formadas bajo estas condiciones. En el enunciado del ejercicio no se hace ninguna referencia sobre alguna restricci´on del uso de caracteres, por lo tanto ellos pueden repetirse. Por otro lado, es claro que cada ordenamiento de los caracteres en las seis posiciones determinan claves distintas. Notemos que el conjunto de claves se puede particionar en aquellas que contienen exactamente una letra “f ” , que llamaremos conjunto F, y aquellas que no contienen exactamente una letra “f ” que queda determinado por la notaci´ on F . Por definici´ on de complemento de un conjunto en un determinado conjunto universal, sabemos que el conjunto y su complemento son una partici´on del conjunto univesal, es decir, se puede utilizar el principio de sustracci´on para calcular el cardinal de uno de los dos subconjuntos del conjunto univesal. En este caso se tiene que F ∪ F = U y F ∩ F = ∅, por lo tanto |U| = |F| + F =⇒ F = |U| − |F| . Calculemos cada cardinal para encontrar la respuesta al problema: ˆ |U| =?

La clave est´ a conformada por seis caracteres elegidos de entre 52 opciones. Para la primera posici´on del clave se disponen de 52 opciones. Independientemente de cu´al sea el caracter que se utilice en la primera posici´ on, para la siguiente tambi´en hay 52 opciones ya que los caracteres se pueden repetir. De igual forma existen 52 opciones para cada una de las seis posiciones de la clave.

Debido a que hay independencia en la elecci´on del caracter en cada posici´ on de la clave, por principio multiplicativo se tiene que |U| = 52 · 52 · 52 · 52 · 52 · 52 = 526 .

ˆ |F| =?

Sabemos que la clave contiene exactamente una letra “f ”, por lo tanto debemos primero contar de cu´antas formas distintas se puede ubicar dicha letra “f ”. Como son seis posiciones en la clave, existen 6 opciones en la cual es puede ubicar la´u ´nica letra “f ” que habr´a en la clave. Cualquiera sea la posici´on que ocupe la letra “f ” en la clave, para la primera posici´ on vac´ıa hay 51 opciones de caracteres (ya que la letra “f ” no puede volver a usarse pues la clave debe contenerla una sola vez), para la segunda tambi´ıen hay 51 opciones, y as´ı con cada una de las cinco posiciones que deben completarse para armar la clave. Como hay independencia, usando el principio multiplicativo, tenemos que |F| = 6 · 51 · 51 · 51 · 51 · 51 = 6 · 515 . Finalmente, usando el principio de sustracci´on se tiene que F = |U| − |F| = 526 − 6 · 515 .