A maior rede de estudos do Brasil

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

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

restantes objetos se pueden en-
tonces seleccionar en forma no consecutiva de F (m −
2, k − 1) formas distintas.
28 Caṕıtulo 2. Arreglos, distribuciones, combinaciones . . .
(b) Aquellas selecciones en las cuales el primer objeto no
ocupa la primera posición. Habrá en total F (m− 1, k)
selecciones de este tipo.
Por lo tanto, tendremos la relación por recurrencia
F (m, k) = F (m− 2, k − 1) + F (m− 1, k),
con las condiciones iniciales F (m, 1) = m y F (k, k) = 0,
para k > 1. Utilizamos ahora el principio de inducción
matemática, para concluir que
F (m, k) =
(
m− 2− (k − 1) + 1
k − 1
)
+
(
m− 1− k + 1
k
)
=
(
m− k
k − 1
)
+
(
m− k
k
)
=
(
m− k + 1
k
)
.
Finalmente, presentamos el siguiente resultado análogo,
referente a selecciones de objetos no consecutivos.
Teorema 18 El número G(m, k) de selecciones de k obje-
tos no consecutivos, a partir de m objetos dispuestos en un
ćırculo, es igual a
G(m, k) =
m
m− k
(
m− k
k
)
, m ≥ 2k.
Demostración: Fijamos en el ćırculo la primera posición
y empleamos la función F del teorema precedente. El total
G(m, k) de selecciones puede separarse en dos grupos:
(a) Aquellas en las cuales el primer objeto ocupa la primera
posición. Los restantes objetos entonces se pueden se-
leccionar de F (m− 3, k − 1) maneras distintas.
(b) Aquellas en las cuales el primer objeto no ocupa la
primera posición. Habrá en total F (m − 1, k) selec-
ciones de este tipo.
2.10. Ejercicios 29
Por lo tanto, tendremos la siguiente relación por recurrencia:
G(m, k) = F (m− 3, k − 1) + F (m− 1, k).
Sustituyendo los valores de F de acuerdo al teorema prece-
dente, obtenemos el resultado, luego de realizar las simplifi-
caciones del caso.
2.10 Ejercicios
27. ¿De cuántas formas se puede indicar en el tablero de
ajedrez dos casillas, una blanca y una negra? ¿Y si no hay
limitaciones en lo que respecta al color de las casillas selec-
cionadas?
28. ¿De cuántas maneras se puede seleccionar en el tablero
de ajedrez una casilla blanca y una negra que no estén en
una misma horizontal ni vertical?
29. De 12 palabras de género masculino, 9 de femenino y
10 de neutro, hay que seleccionar una de cada género. ¿De
cuántos modos se puede efectuar esta selección? Generalice
el problema para cuando el número de palabras por género
son, respectivamente, m, f y n.
30. Hay 6 pares de guantes de distintas medidas. ¿De cuán-
tas maneras se puede seleccionar entre ellos un guante de
la mano izquierda y otro de la derecha, de forma que estos
guantes sean de distintas medidas? Generalice el problema
para cuando hay 2n pares de guantes de distintas medidas.
31. ¿De cuántas maneras se puede formar 6 palabras a partir
de 26 letras diferentes, si en el conjunto de estas 6 palabras
cada letra se utiliza exactamente una vez? Generalice el re-
sultado para cuando tenemos n letras diferentes y se requiere
formar m palabras, con las mismas condiciones.
30 Caṕıtulo 2. Arreglos, distribuciones, combinaciones . . .
32. De entre 3 ejemplares de un texto de álgebra, 7 de ge-
ometŕıa y 7 de trigonometŕıa, hay que seleccionar un ejemplar
de cada texto. ¿Cuántos modos existen de efectuarlo? Gen-
eralice el problema para cuando las cantidades de textos por
materia son n1, n2 y n3.
33. Un encuadernador debe encuadernar 12 libros diferentes
en rojo, verde y marrón. ¿De cuántos modos puede hacerlo,
si por lo menos un libro debe estar encuadernado en cada
color?
34. En una canasta hay 12 manzanas y 10 naranjas. Juan
toma de la canasta una manzana o una naranja, luego de lo
cual Maŕıa toma una manzana y una naranja. ¿En que caso
Maŕıa tendrá mayor libertad de elección: cuando Juan toma
una manzana, o cuando elige tomar una naranja?
35. ¿De cuántas maneras se puede seleccionar, de una baraja
completa de naipes, una carta de cada palo? Mismo asunto,
pero con la condición de que entre las cartas seleccionadas
no haya ningún par igual, es decir, dos reyes, dos diez, etc.
36. Cinco muchachas y tres muchachos juegan a la pelota.
¿De cuántas formas pueden dividirse en dos equipos de 4
personas cada uno, si en cada equipo debe haber por lo menos
un muchacho? Generalice el resultado, para cuando tenemos
n muchachas y m muchachos.
37. De una baraja normal de 52 cartas se han extráıdo 10
cartas. ¿En cuántos casos entre ellas habrá por lo menos
un as? ¿En cuántos casos habrá exactamente un as? ¿En
cuántos habrá no menos de 2 aces? ¿Y exactamente dos
aces?
38. Sea m un entero positivo. Calcule el número de solu-
ciones enteras y positivas de la ecuación
x1 + x2 + · · ·+ xn = m,
2.10. Ejercicios 31
esto es, soluciones para las cuales xi > 0, 1 ≤ i ≤ n.
39. Sea m un entero positivo. Calcule el número de solu-
ciones enteras de la ecuación
x1 + x2 + · · ·+ xn = m,
para las cuales xi ≥ −3, para cada i ∈ {1, 2, . . . , n}.
40. En el coupé de un vagón del ferrocarril hay dos divanes
opuestos, de 5 lugares cada uno. De 10 pasajeros, cuatro
desean sentarse de cara a la locomotora, y tres de espaldas a
ella; a los tres restantes les es indiferente cómo sentarse. ¿De
cuántos modos se puede efectuar esto?
41. La mamá tiene 2 manzanas y 3 peras. Cada d́ıa, du-
rante cinco d́ıas seguidos, da al hijo una fruta. ¿De cuántas
maneras puede efectuarse esto?
42. La mamá tiene n1 objetos tipo I, n2 objetos tipo II y
n3 objetos tipo III. Cada d́ıa, durante n1 + n2 + n3 d́ıas
seguidos, da al hijo un objeto. ¿De cuántas maneras puede
efectuarse esto?
43. En un club deportivo con 30 miembros, hay que formar
un equipo de 4 personas para participar en una carrera de
1000 m. ¿De cuántas maneras puede hacerse? ¿Y de cuántas
maneras se puede formar un equipo de 4 personas para par-
ticipar en la carrera de relevos 100 + 200 + 400 + 800?
44. ¿De cuántas maneras se puede colocar las figuras blancas
(2 torres, 2 alfiles, 2 caballos, el rey y la reina) en la primera
fila del tablero de ajedrez?
45. De un grupo formado por 7 hombres y 4 mujeres, hay
que seleccionar 6 personas de forma tal que entre ellas haya
al menos 2 mujeres. ¿De cuántas maneras puede efectuarse
32 Caṕıtulo 2. Arreglos, distribuciones, combinaciones . . .
la elección? Generalice el problema para cuando el grupo
consiste en H hombres y M mujeres, y hay que seleccionar
p personas (p ≤ H +M), de las cuales al menos h deben ser
hombres y m deben ser mujeres (h ≤ H, m ≤M , h+m ≤ p).
46. Un tren, en el que se encuentran n pasajeros, debe efec-
tuar m paradas. ¿De cuántas maneras pueden distribuirse
los pasajeros entre estas paradas? El mismo problema, si se
tiene en cuenta sólo la cantidad de pasajeros que se bajaron
en las paradas.
47. Un grupo de 7 mujeres y 10 hombres bailan en una fiesta.
Si para algún baile en particular participan todas las mujeres,
¿cuántas variantes existirán de la participación de los hom-
bres en este baile? ¿Cuántas variantes habrá, si se tiene en
cuenta solamente cuáles hombres quedaron sin bailar? Re-
solver las mismas cuestiones si se puede decir con seguridad
que dos hombres determinados serán invitados a bailar.
48. Una compañ́ıa está formada por 3 oficiales, 6 sargentos
y 60 soldados rasos. ¿De cuántos modos se puede seleccionar
entre ellos un destacamento formado por un oficial, dos sar-
gentos y 20 soldados rasos? Resolver el mismo problema,
pero en el destacamento debe figurar el jefe de la compañ́ıa
y el mayor de los sargentos.
49. En una fiesta escolar hay 12 niños y 15 niñas. ¿De
cuántas maneras se puede seleccionar de entre ellos 4 parejas
para un baile? Generalice el problema, para cuando hay n
niños, m niñas y se deben seleccionar de entre ellos k parejas
para el baile, con k ≤ min{n,m}.
50. Hay 3 gallinas, 4 patos y 2 gansos. ¿Cuántas agrupa-
ciones existen para la elección de varias aves, de forma tal
que entre las seleccionadas haya tanto gallinas como patos y
gansos? Generalice el problema, para cuando hay n1 gallinas,
n2 patos y n3 gansos.
2.10. Ejercicios 33
51. ¿De cuántos modos se puede dividir m + n + p objetos