Ejercicios Discretas

82

Capítulo 3

Conteo

(b) Secuencias contienen exactamente tres cruces, suponiendo n £ 3? (c) secuencias contienen exactamente k caras, suponiendo n £ kl 18. Si se lanza n dados legales de seis caras y se anota los números que aparecen en las caras superiores, ¿cuántas (a) secuencias de registro son posibles? (b) secuencias contienen exactamente un seis? (c) secuencias contienen exactamente cuatro doses, suponiendo n > 4?

19. ¿De cuántas maneras puede usted escoger tres de siete libros de ficción y dos de seis libros de temas formales para llevar consigo en sus vacaciones? 20. Para manejar en carretera durante sus vacaciones, va a escoger usted 6 de las 35 casetes de rock de su colección,.3 de las 22 casetes de música clásica y 1 de las 8 casetes de música romántica. ¿De cuántas maneras puede hacer usted sus selecciones?

3.3. Principio de las casillas En esta sección se introduce otra técnica de demostración, en la cual se utiliza los métodos de conteo que han sido estudiados. ' Teorema 1 (El principió de las casillas). Si se asigna n objetos a m casillas, y m4 Observe usted que el principio de las casillas proporciona una prueba de existencia; debe haber un objeto u objetos con una cierta característica. En el ejemplo 1, esta característica es haber nacido en el mismo día de la semana. El principio de las casillas garantiza que hay por lo menos dos personas con está característica, pero no da información sobre la identificación de estas personas. Sólo queda garantizada su existencia. En contraste, una prueba constructiva garantiza la existencia de un objeto u objetos que tengan una cierta característica, construyendo realmente tal objeto u objetos. Por ejemplo, se podría de mostrar que, dados dos números racionales;» y q, existe un número racional entre ellos, si se demuestra que (p + q)/2 está comprendido entre p y g. > Para usar el principio de las casillas, se debe identificar los objetos y las casillas

GRUPO DE EJERCICIOS 3.2 1. Calcule cada una de las siguientes combinaciones. (a) 7C7 (b) 7C4 (c) 16C5 (d) nCn-1 (e)nCn-2 (f) n+ 1Cn-i 2. Demuestre que nCr = nCn -r 3. ¿De cuántas maneras puede seleccionarse un comité de tres miembros de facultad y dos estudiantes, tomándolos de siete miembros de facultad y ocho estudiantes?' 4. ¿De cuántas maneras puede darse una mano de 6 cartas si se tiene una baraja de 52 cartas? , 5 . En un cierto colegio, la oficina de alojamientos ha decidido nombrar, para cada piso, un consejero " residente masculino y uno femenino. ¿Cuántos pares diferentes de consejeros puede seleccionarse para un, edificio de siete pisos, de 12 candidatos del sexo • 'masculino y 15 del sexo femenino? 6. Un fabricante de microcomputadoras que está preparando una campaña de publicidad, está considerando seis revistas, tres periódicos, dos estaciones de televisión y cuatro estaciones de radio. ¿De cuántas maneras puede difundirse seis anuncios si (á) los seis deben ser hechos en revistas? (b) dos deben aparecer en revistas, dos en periódicos, uno en televisión y uno por radio? 7. ¿Cuántas manos diferentes de 8 cartas con 5 cartas ' rojas y 3 negras puede repartirse de una baraja de 52 cartas? '. < 8. (a) Encuentre el número de subconjuntos de cada tamaño posible de un conjunto que contiene • cuatro elementos (b) Encuentre el número de subconjuntos de cada tamaño posible para un conjunto que contiene n 'elementos. 39. Una urna contiene 15 bolas, 8 de las cuales son rojas y 7 son negras. ¿De cuántas maneras puede escogerse 5 bolas de manera que (a) las 5 sean rojas?. (b) las 5 sean negras? • (c). 2 sean rojas y 3 sean negras? (d) 3 sean rojas y 2 sean negras?

10. ¿De cuántas maneras puede seleccionarse un comité de 6 personas de un conjunto de 10, si una de las personas debe ser nombrada como presidente del comité? 11. Un certificado de obsequio de una librería local permite al poseedor escoger 6 libros de la lista combinada de 10 libros de ficción de los de mayor venta y 10 libros de temas formales también de los de mayor venta; ¿De cuántas maneras diferentes puede hacerse la selección de 6 libros? 12. El plan de alimentos del colegio permite "a cada estudiante escoger tres piezas de fruta cada día. Las frutas disponibles son manzanas, plátanos, duraznos, peras y ciruelas. ¿Por cuántos días puede un estudiante hacer una selección diferente? 13. Demuestre que n+1Cr = nCr-1 + nCr. 14. (a) ¿De cuántas maneras puede un estudiante escoger 8 de 10 preguntas para contestar en un examen? -.'•'" (b) ¿De cuántas maneras puede un estudiante escoger 8 de 10 preguntas para contestar en un examen si las primeras 3 preguntas deben ser contestadas? 15. Se lanza al aire cinco monedas legales y se registra los resultados. (a) ¿Cuántas secuencias diferentes de caras y cruces son posibles? (b) ¿Cuántas de las secuencias de la parte (a) tienen exactamente una cara registrada? (c) ¿Cuántas de las secuencias de la parte (a) tienen exactamente tres caras registradas? 16. Se lanza tres dados legales de seis caras y se registra los números que aparecen en las caras superiores. (a) ¿Cuántas secuencias registradas diferentes son posibles? (b) ¿Cuántos de los registros de la parte (a) contienen exactamente un seis? (c) ¿Cuántos de los registros de la parte (a) contienen exactamente dos cuatros? 17. Si se lanza n monedas legales y se registra los resultados, ¿cuántas (a) secuencias de registro son posibles?

GRUPO DE EJERCICIOS 3.1 1. Una clave de admisión de un banco consta de dos letras del alfabeto seguidas por dos dígitos. ¿Cuántas claves diferentes hay? .2. En un experimento psicológico, una persona debe acomodar en hilera un cuadrado, un cubo, un círculo, un triángulo y un pentágono. ¿Cuántos acomodos diferentes son posibles? 3. Se lanza al aire una moneda cuatro veces y se registra el resultado de cada lanzamiento. ¿Cuántas secuencias diferentes de cara y cruz son posibles? 4. Un menú de opciones incluye una sopa, un platillo fuerte, un postre y una bebida. Suponga que un cliente puede hacer su elección entre cuatro sopas, cinco platillos fuertes, tres postres y dos bebidas. ¿Cuántos menús diferentes puede seleccionarse? 5. Un dado legal de seis caras es lanzado cuatro veces, y se anota los números obtenidos en una secuencia . ¿Cuántas secuencias diferentes hay? 6. Calcule cada uno de los siguientes casos. (a) 4P4 (b) 6P5 (c) 7P2 d P e P ( ) n n-l ( ) n n-1 (f) n + 1Pn-1 7. ¿Cuántas permutaciones hay de cada uno de los siguientes conjuntos? (a) {r,s,t,u} . (b) {1, 2, 3, 4, 5} (c) {a, b, l, 2, 3, c} 8. Para cada conjunto A, encuentre el número de permutaciones de A tomando los elementos r a la vez. (a) A = {l, 2, 3, 4, 5, 6,7}, r = 3 (b) A = {x | x es un entero y X2 < 16}, r = 4 9. ¿De cuántas maneras pueden seis hombres y seis mujeres sentarse en línea si (a) cualquier persona puede sentarse en seguida de cualquier otra? (b) los hombres y las mujeres deben ocupar asientos alternados? 10. Encuentre el número de permutaciones diferentes de las letras de la palabra GROUP.

11. ¿Cuántos acomodos diferentes de las letras de la palabra BOUGHT puede formarse si las vocales deben conservarse juntas? 12. (a) Encuentre el número de permutaciones distinguibles de las letras de BOOLEAN. (b) Encuentre el número de permutaciones distinguibles de las letras de PASCAL. 13. (a) Encuentre el número de permutaciones distinguibles de las letras de ASSOCIATTVE. (b) Encuentre el número de permutaciones distinguibles de las letras de REQUIREMENTS. 14. ¿De cuántas maneras pueden sentarse siete personas en un círculo? 15. Se va a usar un librero para exhibir seis nuevos libros. Supóngase que hay ocho libros de ciencia de computación y cinco libros franceses de dónde escoger. Si se decide exhibir cuatro libros de ciencia de computación y dos libros franceses, y se pide" mantener juntos los libros de cada tema ¿cuántos acomodos diferentes es posible hacer? . 16. Se lanzan tres dados legales de seis caras y se anotan los números que aparecen en las caras superiores como lanzamientos triples. ¿Cuántos reportes diferentes son posibles? 17. Demuestre que n • n-1 P n-1 = nPn 18. La mayoría de las versiones de Pascal permite formar nombres de variables de ocho letras o dígitos, con la condición de que el primer carácter debe ser una letra. ¿Cuántos nombres de variables de ocho caracteres son posibles? 19. Actualmente, los códigos de área telefónicos son de tres dígitos, pero el dígito intermedio debe ser O o 1. Los códigos cuyos últimos dos dígitos son 1 están siendo usados para otros fines, por ejemplo, 911. Con estas condiciones ¿cuántos códigos de área hay disponibles? 20. ¿Cuántos números de Seguridad Social (EU) puede asignarse en cualquier tiempo dado? Identifique las suposiciones que haya hecho.