Universidad Nacional de Ingenierı́a
Facultad de Ciencias
Escuela Profesional de Matemática Ciclo 2022−I
PRÁCTICA DIRIGIDA 2 DE INTRODUCCIÓN A LA
MATEMÁTICA DISCRETA
1. ¿Cuántas formas existe para distribuir:
(a) 8 bolas indistinguibles en 4 cajas distinguibles.?
(b) 8 bolas indistinguibles en 5 cajas indistinguibles?
2. Determine la cantidad de maneras diferentes en que Jorge pueda escoger tres casilleros
negros de un tablero de ajedrez (casilleros blancos y negros), de tal manera que cada
casillero elegido se encuentre en diferente fila y columna.
3. De un conjunto de 10 puntos no colineales, ¿cuántas parejas de triángulos podemos formar
de manera que estos tengan un vértice en común?
4. Una urna contiene n/3 bolas blancas y 2n/3 bolas rojas. Considere el siguiente proceso:
una persona con los ojos vendados toma una bola de la urna, y luego chequea el color. Si
la bola fue blanca, retorna la bola a la urna y añade c bolas blancas más a la urna. Si la
bola fue roja, el retorna la bola y añade c bolas rojas. Si este proceso es repetido k veces,
¿cuál es la probabilidad de sacar una bola roja en la iteración k + 1.?
5. Use el principio de inclusión-exclusión para determinar cuántos enteros n existen de modo
que 1 ≤ n ≤ 211 y además:
(a) n no es divisible por 2, 5 y 7.
(b) n es divisible al menos por dos de ellos 2, 5 y 7.
6. Use el principio de inclusión-exclusión para probar que: Si N = p1 α1 ·p2 α2 · · · pn αn entonces
1 1 1
ϕ(N ) = N (1 − )(1 − ) · · · (1 − ).
p1 p2 pn
7. ¿Cuántos términos hay en el principio inclusión-exclusión para la unión de 10 conjuntos?
(no necesitas establecer la fórmula, sólo establecer el número de términos).
8. ¿Cuántos enteros pueden ser expresados como una suma de 2 o más diferentes miembros
del conjunto {0, 1, 2, 4, 8, 16, 31}?.
9. ¿Cuántas permutaciones de las 26 letras no contienen cualquiera de las siguientes expre-
siones: P U T N AM, EXAM, DEC, F IRST ?.
10. Considere la siguiente información acerca de tres conjuntos A, B y C, todos ellos sub-
conjuntos de un conjunto U . Si N (S) denota el número de elementos de S, suponga que
N (A) = 14, N (B) = 10, N (A ∪ B ∪ C) = 24 y N (A ∩ B) = 6. Considere las siguientes
proposiciones:
(a) C tiene como máximo 24 elementos.
(b) C tiene al menos 6 elementos.
(c) A ∪ B tiene exactamente 18 miembros.
11. El Sr. Suárez crı́a pollos. Cada uno de ellos puede ser clasificado como flaco o gordo,
marrón o rojo, gallina o gallo. Cuatro son gallinas marrones flacas, 17 son gallinas, 14 son
pollos flacos, 4 son gallinas flacas, 11 son pollos marrones flacos, 5 son gallinas marrones,
3 son gallos rojos gordos, 17 son pollos marrones o flacos. ¿Cuántos pollos tiene el señor
Suárez?.
12. Determine si las siguientes proposiciones son ciertas
(a) an ∼ n con a > 1.
(b) n! ∼ (a)n con a > 0.
n+1 n
(c) n! ∼ ( )
2
(d) ln(n!) ∼ n ln n.
13. Usando integración, pruebe que para todo n ≥ 1 se cumple:
n n
e( )n ≤ n! ≤ en( )n .
e e
14. Usa el principio del palomar para resolver los siguientes problemas:
(a) Si se seleccionan (n + 1) enteros que no excedan de 2n, debe haber un entero que
divida a uno de los otros enteros.
(b) Si se eligen 10 puntos en el interior de un triángulo equilátero de lado 1, debe haber
al menos dos puntos cuya distancia de separación menor que 31 .
(c) Demuestra que si se escogen 7 números del 1 al 12, dos de ellos sumarán 13.
(d) Hay 12 sillas en una fila, y 9 personas sentadas (de modo que son 9 sillas ocupada,
y 3 sillas están libres). Prueba que hay 3 sillas consecutivas ocupadas.
(e) Prueba que entre cada conjunto de 30 enteros, deben existir dos cuya diferencia o
suma es múltiplo de 51.
15. Para una permutación p : X → X, pk denota la permutación que aparece como la
composición de k - veces p, es decir, p1 = p y pk = p ◦ pk−1 . Se define una relación ≈
sobre el conjunto X como:
16. Determine el número de pares ordenados (A, B), donde A ⊆ B ⊆ {1, 2, . . . n}.
17. ¿Cuántas permutaciones de {1, 2, ..., n} tienen un solo ciclo?
18. Dada la tabla
x y z F(x,y,z)
1 1 1 0
1 1 0 1
1 0 1 0
1 0 0 1
0 1 1 0
0 1 0 1
0 0 1 0
0 0 0 1
2
a) Determine la forma normal disyuntiva (FND) y la forma normal conjuntiva (FNC).
b) Escribe la forma mas simple para F .
19. Simplifique las siguientes expresiones booleanas:
a) F (x, y, z) = (x0 + y)0 .(x + z).(x + z 0 )0 .
b) F (x, y, z, w) = (x0 + y.w)0 .(x + z.w).(x + z 0 .y)0 + (xyz)0 + (x + y + z)0 .
20. Descomponer la siguiente permutación σ en producto de ciclos.
1 2 3 4 5 6 7 8 9
( ) ∈ S9
3 7 8 9 4 5 2 1 6
(a) Dibuje usando grafos dirigidos.
(b) Calcule σ 2021 .
21. Calcule σασ −1 en los siguientes casos:
(a) σ = (135)(12), α = (1579).
(b) σ = (579)(12), α = (123)(34).
22. (a) Encuentre una permutación σ tal que σ tal que σ(12)(34)−1 = (56)(13).
(b) Muestre que no existe ninguna permutación σ tal que σ(123)σ −1 = (13)(578).
