2.9: Ejercicios

1. El alfabeto hawaiano consta de 12 letras. ¿Cuántas cadenas de seis caracteres se pueden hacer usando el alfabeto hawaiano?
2. \(2n\)¿Cuántos enteros positivos de dígitos se pueden formar si los dígitos en posiciones impares (contando el dígito más a la derecha como posición 1) deben ser impares y los dígitos en posiciones pares deben ser pares y positivos?
3. Matt está diseñando un sistema de autenticación de sitios web. Sabe que las contraseñas son más seguras si contienen letras, números y símbolos. No obstante, no entiende del todo que esta seguridad adicional sea derrotada si especifica en qué posiciones aparece cada tipo de personaje. Decide que las contraseñas válidas para su sistema comenzarán con tres letras (mayúsculas y minúsculas ambas permitidas), seguidas de dos dígitos, seguido de uno de 10 símbolos, seguido de dos letras mayúsculas, seguido de un dígito, seguido de uno de 10 símbolos. ¿Cuántas contraseñas diferentes hay para su sistema de sitio web? ¿Cómo se compara esto con el número total de cadenas de longitud 10 hechas del alfabeto de todas las letras inglesas en mayúsculas y minúsculas, dígitos decimales y 10 símbolos?
4. ¿Cuántas cadenas ternarias de longitud\(2n\) hay en las que los ceros aparecen solo en posiciones impares?
5. Supongamos que estamos haciendo placas de la forma\(l_1l_2l_3 - d_1d_2d_3\) donde\(l_1,l_2,l_3\) están mayúsculas en el alfabeto inglés y\(d_1,d_2,d_3\) son dígitos decimales (es decir, elementos del conjunto\(\{0,1,2,3,4,5,6,7,8,9\})\) sujetos a la restricción de que al menos un dígito es distinto de cero y al menos una letra es\(K\). ¿Cuántas placas podemos hacer?
6. La clase de tercer grado de la señora Steffen cuenta con 30 alumnos en ella. Los alumnos se dividen en tres grupos (numerados 1, 2 y 3), cada uno con 10 alumnos.

a) Los alumnos del grupo 1 obtuvieron 10 minutos extra de recreo al ganar una competencia de clase. Antes de salir por su tiempo extra de recreo, forman una sola línea de archivo. ¿De cuántas maneras pueden alinearse?

b) Cuando los 30 alumnos llegan juntos del recreo, vuelven a formar una sola línea de archivo. No obstante, esta vez los alumnos están dispuestos para que el primer alumno sea del grupo 1, el segundo del grupo 2, el tercero del grupo 3, y a partir de ahí, los alumnos sigan alternando por grupo en este orden. ¿De cuántas maneras pueden alinearse para entrar del receso?

7. Cuantas cadenas de la forma\(l_1l_2d_1d_2d_3l_3l_4d_4l_5l_6\) hay donde

• para\(1 \leq i \leq 6\),\(l_i\) es una letra mayúscula en el alfabeto inglés
• para\(1 \leq i \leq 4\),\(d_i\) es un dígito decimal
• \(l_2\)no es una vocal (es decir,\(l_2 \notin \{A,E,I,O,U\}\))
• los dígitos\(d_1,d_2\), y\(d_3\) son distintos (es decir,\(d_1 \neq d_2 \neq d_3 \neq d_1\))

8. En este ejercicio, consideramos cadenas hechas de letras mayúsculas en el alfabeto inglés y dígitos decimales. ¿Cuántas cadenas de longitud 10 se pueden construir en cada uno de los siguientes escenarios?

a) El primer y último carácter de la cadena son letras.

b) El primer carácter es una vocal, el segundo carácter es una consonante y el último carácter es un dígito.

c) Las vocales (no necesariamente distintas) aparecen en las posiciones tercera, sexta y octava y ninguna otra posición.

d) Las vocales (no necesariamente distintas) aparecen exactamente en dos posiciones.

e) Precisamente cuatro caracteres en la cadena son dígitos y ningún dígito aparece más de una vez.

9. Una base de datos utiliza cadenas de 20 caracteres como identificadores de registro. Los caracteres válidos en estas cadenas son letras mayúsculas en el alfabeto inglés y dígitos decimales. (Recordemos que hay 26 letras en el alfabeto inglés y 10 dígitos decimales.) Cuántos identificadores de registro válidos son posibles si un identificador de registro válido debe cumplir con todos los siguientes criterios:

• Las letras del conjunto\(\{A,E,I,O,U\}\) aparecen exactamente en tres posiciones de la cadena.
• Los tres últimos caracteres de la cadena son dígitos decimales distintos que no aparecen en otra parte de la cadena.
• Los caracteres restantes de la cadena se pueden rellenar con cualquiera de las letras o dígitos decimales restantes.

10. Dejar\(X\) ser el conjunto de las 26 letras inglesas minúsculas y 10 dígitos decimales. \(X\)¿Cuántas cadenas de longitud 15 satisfacen todas las siguientes propiedades (al mismo tiempo)?

• El primer y último símbolo de la cadena son dígitos distintos (que pueden aparecer en otra parte de la cadena).
• Precisamente cuatro de los símbolos de la cadena son la letra '\(t\)'.
• Precisamente tres caracteres en la cadena son elementos del conjunto\(\{a,e,i,o,u\}\) y estos caracteres son todos distintos.

11. Una tienda de donas vende 12 tipos de donas. Un gerente quiere comprar seis donas, una cada una para él y sus cinco empleados.

a) Supongamos que lo hace seleccionando un tipo específico de donut para cada persona. (Puede seleccionar el mismo tipo de donut para más de una persona.) ¿De cuántas maneras puede hacer esto?

b) ¿De cuántas maneras podría seleccionar las donas si quiere asegurarse de que elige un tipo diferente de donut para cada persona?

c) Supongamos en cambio que desea seleccionar un donut de cada uno de seis tipos diferentes y colocarlos en la sala de descanso. ¿De cuántas maneras puede hacer esto? (El orden de las donas en la caja es irrelevante.)

12. El deporte del korfball lo juegan equipos de ocho jugadores. Cada equipo cuenta con cuatro hombres y cuatro mujeres en él. La Preparatoria Halliday cuenta con siete hombres y 11 mujeres interesadas en jugar korfball. ¿De cuántas maneras pueden formar un equipo korfball a partir de sus 18 alumnos interesados?

13. Veinte estudiantes compiten en un concurso de programación en el que los cuatro mejores estudiantes son reconocidos con trofeos por los primeros, segundos, terceros y cuartos lugares.

a) ¿Cuántos resultados diferentes hay para los cuatro primeros lugares?

b) A última hora, los jueces deciden que otorgarán certificados de mención honorífica a cuatro individuos que no recibieron trofeos. ¿De cuántas maneras se pueden seleccionar los destinatarios de la mención honorífica (después de que se hayan determinado los cuatro primeros lugares)? ¿Cuántos resultados totales (trofeos más certificados) hay entonces?

14. Una heladería tiene un especial de banana splits, y Xing lo está aprovechando. Está asombrado de todas las opciones que tiene para construir su split de banano:

• Debe elegir tres sabores diferentes de helado para colocar en el bol asimétrico en el que se sirve el banano split. La tienda cuenta con 20 sabores de helado disponibles.
• Cada cucharada de helado debe estar coronada por una salsa, elegida entre seis opciones diferentes. Xing es libre de poner el mismo tipo de salsa en más de una cucharada de helado.
• Hay 10 coberturas rociadas disponibles, y debe elegir tres de ellas para haber rociado sobre toda la división de plátano.

a) ¿Cuántas formas diferentes hay para que Xing construya un banano split en esta heladería?

b) Supongamos que en lugar de requerir que Xing elija exactamente tres coberturas rociadas, se le permite elegir entre cero y tres coberturas rociadas. En este escenario, ¿de cuántas formas diferentes hay para que construya un split de banano?

15. Supongamos que un maestro desea distribuir 25 lápices idénticos a Ahmed, Barbara, Casper y Dieter de tal manera que Ahmed y Dieter reciban al menos un lápiz cada uno, Casper recibe no más de cinco lápices, y Barbara recibe al menos cuatro lápices. ¿De cuántas maneras se puede hacer tal distribución?

16. ¿Cuántas soluciones de valor entero existen para cada una de las siguientes ecuaciones y desigualdades?

a)\(x_1+x_2+x_3+x_4+x_5=63\), todos\(x_i > 0\)

b)\(x_1+x_2+x_3+x_4+x_5=63\), todos\(x_i \geq 0\)

c)\(x_1+x_2+x_3+x_4+x_5 \leq 63\), todos\(x_i \geq 0\)

d)\(x_1+x_2+x_3+x_4+x_5=63\), todos\(x_i \geq 0, x_2 \geq 10\)

e)\(x_1+x_2+x_3+x_4+x_5=63\), todos\(x_i \geq 0, x_2 \leq 9\)

17. ¿Cuántas soluciones enteras hay para la ecuación?

\(x_1+x_2+x_3+x_4 = 132\)

siempre que\(x_1 > 0\), y\(x_2,x_3,x_4 \geq 0\)? ¿Y si agregamos la restricción que\(x_4 < 17\)?

18. ¿Cuántas soluciones enteras hay para la desigualdad?

\(x_1+x_2+x_3+x_4+x_5 \leq 782\)

siempre que\(x_1,x_2 > 0\),\(x_3 \geq 0\), y\(x_4,x_5 \geq 10\)?

19. Un maestro tiene 450 piezas idénticas de dulces. Quiere distribuirlos a su clase de 65 alumnos, aunque está dispuesto a llevarse algunos dulces sobrantes a casa. (No insiste en llevarse ningún caramelo a casa, sin embargo.) El alumno que ganó un concurso en la última clase es recibir al menos 10 piezas de dulces como recompensa. De los estudiantes restantes, 34 de ellos insisten en recibir al menos una pieza de caramelo, mientras que los 30 estudiantes restantes están dispuestos a no recibir dulces.

a) ¿De cuántas maneras puede distribuir los dulces?

b) ¿De cuántas formas puede distribuir los dulces si, además de las condiciones anteriores, uno de sus alumnos es diabético y puede recibir como máximo 7 piezas de caramelo? (Este alumno es uno de los 34 que insisten en recibir al menos una pieza de caramelo).

20. Dar un argumento combinatorio para probar la identidad

\(k\dbinom{n}{k} = n\dbinom{n-1}{k-1}\).

Pista

Piensa en elegir un equipo con un capitán.

21. Dejar\(m\) y\(w\) ser enteros positivos. Dar un argumento combinatorio para probar que para los enteros\(k \geq 0\),

\(\displaystyle \sum_{j=0}^k \dbinom{m}{j} \dbinom{w}{k-j} = \dbinom{m+w}{k}\).

22. ¿Cuántas trayectorias de celosía hay de (0,0) a (10,12)?

23. ¿Cuántas trayectorias de celosía hay de (3,5) a (10,12)?

24. ¿Cuántas trayectorias de celosía hay de (0,0) a (10,12) que pasan por (3,5)?

25. ¿Cuántas trayectorias de celosía de (0,0) a (17,12) hay que pasan por (7,6) y (12,9)?

26. ¿Cuántos caminos de celosía de (0,0) a (14,73) hay que no pasan por (6,37)?

27. Un ladrón de bancos de un pequeño pueblo conduce su auto de huida del banco que acaba de robar hasta su escondite. El banco se encuentra en la intersección de la Calle 1 y la Avenida 1. Necesita regresar a su escondite en la intersección de la calle 7 y la avenida 5. No obstante, uno de sus miradores ha informado que el único policía de la localidad está estacionado en la intersección de la calle 4 y la avenida 4. Suponiendo que el ladrón de bancos no quiere que lo arresten y conduzca solo por calles y avenidas, ¿de cuántas maneras puede regresar con seguridad a su escondite? (Calles y avenidas están uniformemente espaciadas y numeradas consecutivamente en este pequeño pueblo.)

28. El escenario de este problema es el pueblo ficticio de Mascotiville, que se presenta como una cuadrícula. A las mascotas se les permite viajar solo por las calles, y no “como vuela la chaqueta amarilla”. Buzz, la mascota de Georgia Tech, quiere ir a visitar a su amigo Thundar, la mascota de la Universidad Estatal de Dakota del Norte, que vive 6 cuadras al este y 7 cuadras al norte de la colmena de Buzz. No obstante, Uga VIII se ha mudado recientemente a la caseta del perro 2 cuadras al este y 3 cuadras al norte de la colmena de Buzz y ya tiene una orden de restricción contra Buzz. También hay un par de tigres (madre y cachorro) de Clemson que viven 1 cuadra al este y 2 cuadras al norte de Uga VIII, y son conocidos por colocar trampas para Buzz. Buzz quiere viajar de su colmena a la pluma de Thundar todos los días sin encontrarse con Uga VIII o El Tigre y El Cachorro de Tigre. No obstante, quiere evitar el aburrimiento causado por utilizar una ruta que ha utilizado en el pasado. ¿Cuál es el mayor número de días consecutivos en los que Buzz puede hacer el viaje para visitar Thundar sin reutilizar una ruta (puedes suponer que las rutas tomadas por Buzz solo van al este y al norte)?

29. Determinar el coeficiente on\(x^{15}y^{120}z^{25}\) in\((2x+3y^2+z)^{100}\).

30. Determinar el coeficiente on\(x^{12}y^{24}\) in\((x^3+2xy^2+y+3)^{18}\). (¡Ten cuidado, como\(x\) y\(y\) ahora aparecen en múltiples términos!)

31. Para cada palabra a continuación, determine el número de reordenamientos de la palabra en la que se deben usar todas las letras.

a) SOBRENUMEROSES

b) Oftalmootorrinolaringología

c) HONORIFICABILITUDINITATIBUS (la palabra más larga en el idioma inglés que consiste estrictamente en consonantes y vocales alternas)

32. ¿Cuántas formas hay de pintar un conjunto de 27 elementos tal que 7 están pintados de blanco, 6 están pintados de oro viejo, 2 están pintados de azul, 7 están pintados de amarillo, 5 están pintados de verde, y 0 de están pintados de rojo?

33. Hay muchos conjuntos útiles que son enumerados por los números catalanes. (El volumen dos de la Combinatoria Enumerativa de R.P. Stanley contiene un famoso (o quizás infame) ejercicio en 66 partes pidiendo a los lectores que encuentren bijecciones que demuestren que el número de diversas estructuras combinatorias es\(C(n)\), y su página web cuenta con una lista adicional de al menos 100 partes.) Dar argumentos biyectivos para mostrar que cada clase de objetos a continuación es enumerada por\(C(n)\). (Los tres fueron seleccionados de la lista en el libro de Stanley.)

a) El número de formas de paréntesis total de un producto de\(n+1\) factores como si la operación de “multiplicación” en cuestión no fuera necesariamente asociativa. Por ejemplo, hay una manera de paréntesis de un producto de dos factores\((a_1a_2)\), hay dos formas de paréntesis de un producto de tres factores\(((a_1(a_2a_3))\) y\(((a_1a_2)a_3))\), y hay cinco formas de paréntesis de un producto de cuatro factores:

\((a_1(a_2(a_3a_4))),(a_1((a_2a_3)a_4)),((a_1a_2)(a_3a_4)),((a_1(a_2a_3))a_4),(((a_1a_2)a_3)a_4)\).

b) Secuencias de\(n\) 1's y\(n −1\)'s en las que la suma de los primeros\(i\) términos no es negativa para todos\(i\).

c) Secuencias\(1 \leq a_1 \leq \cdot \cdot \cdot \leq a_n\) de números enteros con\(a_i \leq i\). Por ejemplo, para\(n=3\), las secuencias son

111 112 113 122 123

Pista

Para la parte 2.9.33.c, piense en dibujar trazados de celosía en papel con líneas de cuadrícula y (básicamente) el número de cajas debajo de una trayectoria de celosía en una columna en particular.