A maior rede de estudos do Brasil

Grátis
179 pág.
Análise combinatória matemática

Pré-visualização | Página 24 de 30

por sus otros colegas. El
primer juez tiene 10 posibilidades de selección de su nomi-
nado, el segundo juez tendrá entonces sólo 9 posibilidades de
selección el tercer juez tendrá por tanto sólo 8 posibilidades
de selección, para un total de 10 × 9 × 8 = 720 formas dis-
tintas en las cuales no habrá un ganador absoluto. Como
en total hay 10 × 10 × 10 = 1.000 maneras distintas en que
los jueces pueden designar al primer nominado (sin restric-
ciones), entonces el número de casos en los cuales habrá un
ganador absoluto es 1.000− 720 = 280, para una proporción
de 100× 280/1.000 = 28% de los casos del torneo.
17. El conteo de collares y brazaletes pertenece al dif́ıcil
tema de las permutaciones circulares con repeticiones, tema
para el cual no hemos estudiado ninguna fórmula en la teoŕıa,
pues la misma —como veremos— se escapa a los objetivos de
la presente monograf́ıa. Aclaramos que cuando hablamos de
collares y brazaletes estamos considerando las permutaciones
circulares simples con repeticiones, tomando en consideración
las simetŕıas que se producen al “darle vuelta” al collar o
brazalete. Este ejemplo ilustrará las dificultades.
17a) Cuando se trata de 5 cuentas iguales y 2 de mayor di-
mensión, el problema puede ser resuelto fácilmente por enu-
meración de casos: solamente habrá tres 3 brazaletes circu-
124 Caṕıtulo 9. Las soluciones de los ejercicios impares
lares diferentes, los cuales son:
B B a a a a a , B a B a a a a , B a a B a a a.
Aqúı “a” representa una de las 5 cuentas pequeñas y “B”
representa a una de las 2 cuentas grandes. Es inmediato
corroborar que cualquier otro diseño es semejante a alguno de
los tres diseños básicos anteriores. Por ejemplo, el brazalete
“B a a a B a a” es semejante al último de la lista de arriba,
en virtud de la circularidad.
17b. Generalización: cuando tenemos n cuentas de un tipo
y m de otro tipo, el problema se complica enormemente. En
efecto, la solución viene dada por la fórmula
1
n+m
∑
d
φ(d) · ((n+m)/d)!
(n/d)! (m/d)!
,
donde d recorre los divisores del máximo común divisor de
n y m y φ(d) es la función de Euler1: el número de primos
relativos de d entre la lista 0, 1, 2, . . . , d−1. En el caso en que
n y m sean primos relativos (pero solo en ese caso) la fórmula
anterior simplifica, pues solamente tendrá un sumando, y
queda 1n+m
(n+m)!
n! m! . Por ejemplo, en el caso n = 3 y m = 3,
obtenemos que el número de brazaletes diferentes será
1
6
[
φ(1)
6!
3! 3!
+ φ(3)
(6/3)!
(3/3)! (3/3)!
]
=
1
6
(1 · 20 + 2 · 2) = 4.
Los 4 brazaletes son, en este caso:
a a a B B B, a a B a B B, a a B B a B, a B a B a B.
1La función φ de Euler está caracterizada por las siguientes
propiedades:
• Está definida para todo entero positivo.
• Si p es primo, entonces φ(p) = p − 1 y φ(pk) = pk − pk−1.
• φ es una función multiplicativa: φ(a · b) = φ(a) ·φ(b), si a y b son
primos relativos.
9.1. Ejercicios del caṕıtulo 1 125
19. En este problema los m libros encuadernados en ne-
gros son indistinguibles entre śı, interesando únicamente su
posición relativa con respecto a los n libros encuadernados
en rojo.
19a) Permutaciones en las cuales los primeros m lugares son
libros encuadernados en negro: n!. Cualquier posición inicial
de los m libros encuadernados en negro es equivalente.
19b) Permutaciones en las que los m libros negros quedan
juntos: podemos contarlas mediante el siguiente esquema:
n · · ·n︸ ︷︷ ︸
negros
� · · ·�︸ ︷︷ ︸
n rojos
= n! permutaciones
�︸︷︷︸
rojo
n · · ·n︸ ︷︷ ︸
negros
� · · ·�︸ ︷︷ ︸
n−1 rojos
= n! permutaciones
...
...
� · · ·�︸ ︷︷ ︸
n rojos
n · · ·n︸ ︷︷ ︸
negros
= n! permutaciones
para un total de (n+ 1)n! = (n+ 1)! permutaciones.
21. ¡Otro problema de brazaletes! La fórmula general para
la cantidad de brazaletes de n cuentas, donde n1 cuentas son
de tipo 1, n2 cuentas son de tipo 2, . . . , nr cuentas son de
tipo r, es sumamente compleja de obtener pues involucra a
la función φ de Euler. Esta fórmula es:
1
n
∑
d
φ(d)
(n/d)!
(n1/d)! (n2/d)! · · · (nr/d)!
,
donde d recorre a los divisores del máximo común divisor de
n1, n2, . . . , nr y φ es la función de Euler (ver el ejercicio 17).
En este caso tendremos n = 18, n1 = 5, n2 = 6, n3 = 7,
que son primos relativos entre śı, de manera que la fórmula
anterior simplifica a un único sumando: el número total de
brazaletes será igual a
1
18
· φ(1) · 18!
5! 6! 7!
= 816.816.
126 Caṕıtulo 9. Las soluciones de los ejercicios impares
23. Premios de la Olimṕıada: son 20 personas compitiendo
y los premios son 3 ejemplares del libro A, 2 ejemplares del
libro B y 1 ejemplar del libro C.
23a) Bajo el supuesto que a nadie le otorguen 2 premios de
golpe, tendremos el siguiente esquema de posibilidades de
entrega de los premios:
1er libro A: = 20 posibilidades
2do libro A: = 19 posibilidades
3er libro A: = 18 posibilidades
1er libro B: = 17 posibilidades
2do libro B: = 16 posibilidades
1er libro C: = 15 posibilidades
Total: = [20]6 = 27.907.200 posibilidades.
23b) Bajo el supuesto que a nadie se le otorguen 2 ejem-
plares de un mismo libro, tendremos el siguiente esquema de
posibilidades de entrega de los premios:
1er libro A: = 20 posibilidades
2do libro A: = 19 posibilidades
3er libro A: = 18 posibilidades
1er libro B: = 20 posibilidades
2do libro B: = 19 posibilidades
1er libro C: = 20 posibilidades
Total: = [20]3 · [20]2 · [20]1 = 51.984.000
25. Tendremos dos posibilidades de abordar el problema:
25a) Si permitimos ceros iniciales: en este caso el número
formado por las tres primeras cifras tiene 1.000 posibilidades
distintas de ser seleccionado (del 000 al 999), y para la se-
lección i-ésima el número formado por las tres últimas cifras
tendrá entonces 999− i posibilidades de ser seleccionado (del
000 al 999 − i). Luego, tendremos un total de posibilidades
9.2. Ejercicios del caṕıtulo 2 127
de selección igual a
999∑
i=0
(999− i) = 999× 1.000
2
= 499.500.
25b) Si no permitimos los ceros iniciales: en este caso el
número formado por las tres primeras cifras tiene solamente
900 posibilidades distintas de ser seleccionado (del 100 al
999), y para la selección i-ésima el número formado por las
tres últimas cifras tendrá entonces 999 − i posibilidades de
selección, para un total de posibilidades igual a
999∑
i=100
(999− i) = 404.550.
9.2 Ejercicios del caṕıtulo 2
27. Tablero de ajedrez.
27a) Número de selecciones de dos casillas del tablero, una
blanca y una negra: 32 × 32 = 1.024. Lo anterior si no
interesa el orden. Si interesa el orden, la respuesta es 2! ×
32× 32 = 2.048.
27b) Número de selecciones de dos casillas del tablero, sin
limitaciones: (642 ) = 2.016. Lo anterior si no interesa el or-
den. Si interesa el orden, la respuesta seŕıa 64× 63 = 4.032.
29. Palabras de género masculino (12), femenino (9) y neutro
(10). No interesa el orden dentro de las selecciones.
29a) Elección de una de cada género: 12 × 9 × 10 = 1.080
formas.
29a) Generalización: mfn formas.
31. Número de maneras de formar 6 palabras a partir de 26
letras diferentes.
128 Caṕıtulo 9. Las soluciones de los ejercicios impares
31a) Si en el conjunto de las 6 palabras, cada letra se utiliza
solo una vez. Comenzamos eligiendo la primera letra de cada
palabra, lo cual puede hacerse de [26]6 = 26× 25× 24× 23×
22× 21 formas diferentes. Nos quedan 20 letras disponibles.
Seleccionamos entre ellas las k letras que del todo no se em-
plearán, con 0 ≤ k ≤ 20. Para cada valor de k esto puede
hacerse de (20k ) formas distintas. Quedan 20 − k letras dis-
tintas, a distribuir en las 6 “cajas ordenadas” (palabras), lo
cual puede hacerse de [6]20−k = (25−k)!/5! formas distintas.
Luego, la solución será
[26]6 ·
20∑
k=0
(
20
k
)
· [6]20−k ≈ 0, 47× 1032.
31b) Generalización: cuando tenemos n (en vez de 26) letras
y se requiere formar m palabras (en vez de 6), la solución
será:
[n]m ·
n−m∑
k=0
(
n−m
k
)
· [m]n−m−k.
El autor ignora si esta última expresión admite una simplifi-
cación.
33. Al principio

Crie agora seu perfil grátis para visualizar sem restrições.