Análise combinatória matemática

las siguientes 9 boletas garanti-
zan al menos 3 resultados correctos: (0,0,0,0), (0,1,1,2),
(0,2,2,1), (1,0,1,1), (1,1,2,0), (1,2,0,2), (2,0,2,2), (2,1,0,1),
(2,2,2,1). La solución no es única.
5. Para n = 5 es problema es muy complicado, aunque
aún nos queda el recurso de utilizar computadoras para
enumerar rápidamente los resultados, obteniéndose que
σ5 = 27. Por ejemplo, los siguientes 27 números, cuando
se representan en base 3, corresponden a 27 boletas que
garantizan al menos 4 resultados correctos: 0, 10, 23, 34,
41, 51, 59, 69, 73, 89, 93, 106, 111, 124, 128, 136, 146, 156,
166, 179, 180, 191, 198, 211, 222, 239, 242.
Sin embargo, para n = 6 el problema aún está abierto:
¡se desconoce el valor exacto de σ6! El problema aqúı es el
rápido crecimiento “combinatorio” de las configuraciones que
deben analizarse. Para resolver el problema por enumeración
se necesitaŕıa analizar un gran total de 23
n
casos, cantidad
que se escapa a toda posibilidad de análisis en el tiempo. Por
ejemplo, para n = 6 habŕıa que analizar 2729 casos: toda la
eternidad aún para la computadora más veloz del mundo.
118 Caṕıtulo 8. Otros tópicos de la teoŕıa de combinatoria
No se conoce una fórmula directa, ni por recurrencia, para
el cálculo de σn. Menos aún se conoce la función generadora
Fσ. Tan sólo se conocen algunas cotas superiores para σn, co-
tas que se han ido mejorando con el pasar de los años. Cada
vez que alguien encuentra una cota superior más pequeña
para algún valor de σn, el descubrimiento es objeto de una
publicación en alguna de las mejores revistas de la teoŕıa de
combinatoria del mundo. Para el caso más simple aún de-
sconocido, σ6, se encontró en 1992 que σ6 ≤ 73 y se conjetura
que σ6 = 72.
8.7 Ejercicios
124. Encuentre la función generadora para Ak, el número de
maneras de cambiar k colones en billetes de //C10000, //C5000,
//C2000, //C1000, //C500, //C100 y //C50.
125. Dado un grupo de n mujeres y sus respectivos esposos,
cúantas personas deben ser seleccionadas de este grupo de 2n
personas para garantizar que en el grupo de las seleccionadas
habrá un matrinomio?
126. Muestre que cualquier subconjunto de n + 1 enteros
diferentes entre 1 y 2n, con n ≥ 2, siempre contiene un par
de enteros que son primos relativos.
127. Muestre que en una fiesta de 20 personas, siempre hay
2 que tienen el mismo número de amigos (amistad dentro del
grupo de las 20 personas).
128. Muestre que en una fiesta con 6 o más personas, siem-
pre habrá un grupo de 3 amigos mutuos o un grupo de 3
extraños mutuos.
129. Muestre que cualquier secuencia de nm + 1 números
distintos siempre contiene una subsecuencia creciente de n+1
números o una subsecuencia decreciente de m+ 1 números.
Caṕıtulo 9
Las soluciones de los
ejercicios impares
Presentamos en este caṕıtulo las soluciones de los ejer-
cicios impares planteados a lo largo de toda la obra. Las
soluciones se presentan con gran cantidad de detalles, con
fines meramente didácticos.
Por lo general dispondremos de varios métodos para re-
solver los problemas de combinatoria. Recomendamos al lec-
tor que intente resolver cada ejercicio empleando sus propias
ideas y métodos y solamente luego de ello consulte las solu-
ciones aqúı desarrolladas.
9.1 Ejercicios del caṕıtulo 1
1. a. Hay 5 caminos que conducen de A a B y para cada
uno de ellos hay 3 caminos que conducen de B a C. Luego,
en total hay 15 = 5× 3 caminos diferentes que conducen de
A a C pasando por B.
A B C
1
2
3
4
5
1
2
3
b) Generalización: hay n × m caminos diferentes que con-
ducen de A a C pasando por B.
119
120 Caṕıtulo 9. Las soluciones de los ejercicios impares
3. a) Cantidad de nombres que los ingleses suelen dar a un
niño:
i) Si no se admiten repeticiones de nombre de ningún tipo:
[300]3 + [300]2 + [300]1 = 300× 299× 298 + 300× 299 + 300
= 26.820.600 nombres.
El primer sumando corresponde el número de maneras de
asignar 3 nombres diferentes, el segundo al número de man-
eras de asignar 2 nombres diferentes, etc.
ii) Si se permiten las repeticiones de nombres:
3003 + 3002 + 300 = 27.090.300 nombres.
3b) Generalización: i) Sin repeticiones de nombres:
n∑
i=1
[N ]i nombres.
ii) Con repeticiones de nombres:
N +N2 +N3 + · · ·+Nn = N(N
n − 1)
N − 1
nombres.
5. a) Hay 90.000 números diferentes de 5 d́ıgitos, si los ceros
iniciales no son permitidos. Estos se obtienen a partir de
la cantidad de números totales 100.000 (del 0 al 99.999) re-
stando los 10.000 (del 0 al 09999) que comienzan con 0.
5b) Serán pares la mitad de ellos, esto es, 45.000. La paridad
solamente depende del último d́ıgito.
5c) Aparece un 3 en alguna posición en 37.512 casos, de los
90.000. Estos pueden contarse según el siguiente esquema,
9.1. Ejercicios del caṕıtulo 1 121
en donde � indica una casilla a ser llenada por un d́ıgito:
1ra posición: 3 � � � �︸ ︷︷ ︸
10.000
= 10.000 casos
2da posición: �︸︷︷︸
8
3 � � �︸ ︷︷ ︸
1.000
= 8.000 casos
3ra posición: �︸︷︷︸
8
�︸︷︷︸
9
3 � �︸︷︷︸
100
= 7.200 casos
4ta posición: �︸︷︷︸
8
� �︸︷︷︸
81
3 �︸︷︷︸
10
= 6.480 casos
5ta posición: �︸︷︷︸
8
� � �︸ ︷︷ ︸
729
3 = 5.832 casos
5d) Paĺındromos: 900 en total. Pueden contarse mediante el
siguiente esquema:
a︸︷︷︸
9
b︸︷︷︸
10
c︸︷︷︸
10
b a = 900 casos.
7. Tendremos que en general m personas se pueden sentar
a una mesa circular de (m − 1)! formas distintas. Esto se
obtiene fijando cualquiera de las personas como “cabecera” y
calculando las permutaciones de las m−1 personas restantes,
las cuales son (m− 1)!.
7a) De 5! (5 − 1)! = 2.880 formas distintas. Más sencillo es
explicar el caso general que sigue.
7b) Generalización al caso de n hombres y n mujeres: primero
colocamos n sillas iniciales en la mesa circular y procedemos
a sentar a los n hombres, lo cual puede hacerse de (n − 1)!
formas distintas. Luego, agregamos sillas intercaladas entre
los hombres. Fijamos la posición de un hombre cualquiera en
la mesa y procedemos a contar el número de permutaciones
simples de las n mujeres: hay n! en total. Cada una de estas
permutaciones simples de las mujeres se pueden intercalar en
la disposición circular de los hombres previamente estable-
cida. Luego, habrá en total n! (n − 1)! formas distintas de
sentar a los hombres y las mujeres en forma intercalada.
122 Caṕıtulo 9. Las soluciones de los ejercicios impares
9. Números de matŕıcula de automóvil: 182.789.000 difer-
entes números, los cuales los podemos contar con el siguiente
esquema:
�︸︷︷︸
26
# # # #︸ ︷︷ ︸
10.000
= 260.000,
� �︸︷︷︸
262
# # # #︸ ︷︷ ︸
10.000
= 6.760.000,
� � �︸ ︷︷ ︸
263
# # # #︸ ︷︷ ︸
10.000
= 175.760.000.
En el diagrama anterior, � denota cualquier letra de las 26
posibles, mientras que # denota cualquier d́ıgito, de los 10
posibles.
11. Permutaciones de palabras, dejando las vocales en las
posiciones originales.
11a) “matematica”: Prescindiendo de las vocales (las cuales
tienen posición fija) tendremos 2“m”, 2“t”, 1“c”. Luego,
habrá
5!
2! 2! 1!
= 30 permutaciones.
11b) “parabola”: Eliminando las vocales, tendremos 1“p”,
1“r”, 1“b”, 1“l”. Luego, habrá
4!
1! 1! 1! 1!
= 24 permutaciones.
11c) “ingrediente”: Esta vez al eliminar las vocales nos
queda 2“n”, 1“g”, 1“r”, 1“d”, 1“t”. Luego, habrá
6!
2! 1! 1! 1! 1!
= 360 permutaciones.
11d) “parangaricutirimicuaro”: Eliminando las vocales,
esta vez tendremos 1“p”, 4“r”, 1“n”, 1“g”, 2“c”, 1“m”.
Luego, habrá
10!
1! 4! 1! 1! 2! 1!
= 75.600 permutaciones.
9.1. Ejercicios del caṕıtulo 1 123
13. Números distintos de 4 cifras divisibles por 4 con los
d́ıgitos 1, 2, 3, 4, 5. Usando solo esas cifras, tendremos que los
únicos números divisibles por 4 serán aquellos que terminen
en 12, 24, 32, 44 y 52. Luego, la cantidad total buscada es:
� �︸︷︷︸
5×5
� �︸︷︷︸
5
= 125 números.
15. Es más fácil calcular el porcentaje de los casos del torneo
en que NO se habrá determinado un ganador absoluto. Esto
ocurrirá cuando cada uno de los jueces nombre de primero a
un gimnasta distinto al nombrado