Problemas de Matemática Discreta

Profesorado de Matemática Discreta

Septiembre de 2006
Capı́tulo 1

Combinatoria: Muestras
ordenadas

1. (p99-pac11 ) En una plaza cuadrada de 2500 metros cuadrados, hay 626

personas manifestándose. ¿Se podrı́an repartir estas personas de forma que
cualquier persona se encontrara en 3 metros de cualquier otra?

Solución
Cada lado de la plaza mide 50 metros. Si dividimos cada lado del cuadrado en 25
partes de 2 metros cada una, podemos formar 25·25=625
√ cuadrados de 2 metros
de lado. La diagonal de estos cuadrados es igual a 8 metros, aproximadamente
2,8 metros, por lo tanto, menor que 3 metros.
Es decir, hemos dividido la plaza en 625 cuadrados; la distancia máxima en cada
uno de estos cuadrados es menor que 3 metros (por lo tanto, dos personas que
compartan el cuadrado se encontrarán en una distancia menor de 3 metros).
Podemos aplicar, ahora, el principio de las cajas: las 626 personas de la plaza se
reparten entre estos 625 cuadrados, de forma que, como mı́nimo, dos personas
tienen parte de su cuerpo dentro de un cuadrado. Por lo tanto, estas dos personas
se encuentran en una distancia menor de 3 metros.
En definitiva, no se pueden poner 626 personas en una plaza de estas caracterı́sti-
cas, de forma que todas las personas estén además de 3 metros de cualquier otra.

2. (p99-pac15 ) En un torneo de tenis, habitualmente, los enfrentamientos entre

jugadores son eliminatorios, es decir: cuando dos jugadores se enfrentan, quien
gana pasa a la siguiente ronda y quien pierde ya no continúa jugando. Esto
se repite hasta que se llega a la situación en que ya no quedan más que dos
jugadores, que juegan la final.
El estado de Malta quiere hacer un campeonato de tenis, que debe tener 5 rondas
eliminatorias antes de la final.

(a) ¿cuántos tenistas habrá que invitar?

1
Combinatoria: Muestras ordenadas 2

(b) ¿cuántos partidos se jugarán a lo largo de todo el torneo?

Solución

(a) habrá 6 rondas en total. Si partimos de la final y vamos hacia atrás, en

cada ronda hay el doble de jugadores, por lo tanto, en 6 rondas habrá 26 =
64 tenistas.
26 −1
(b) Se jugarán 1 + 21 + 22 + 23 + 24 + 25 = 2−1 = 63 partidos

3. (t99-pac12 ) Una función booleana consiste en una correspondencia en la que,

a partir de n inputs binarios, obtenemos un único output binario.
¿Cuántas funciones booleanas podemos construir?

Solución
Nos piden cuántas funciones entre A y B podemos hacer, siendo A el conjunto
de todas las secuencias de n bits y B el conjunto {0, 1}.
Entonces |A| = 2n , |B| = 2 y, por lo tanto, de funciones booleanas entre A y B
n
habrá tantas como 22 .

4. (t99-pac14 ) ¿De cuántas maneras se pueden disponer en fila las letras a, b,

c, d, x, x, x, x, x, de forma que ninguna pareja de ’x’ quede junta?

Solución
La única manera de hacerlo es disponer las ’x’ en los lugares 1, 3, 5, 7 y 9 de
la fila y repartir de todas las maneras posibles las restantes cuatro letras en los
lugares 2, 4, 6 y 8.
V4 = 4! = 24

5. (t99-pac15 ) Un estudiante ha estudiado 120 horas a lo largo de 14 dı́as (se

supone que cada dı́a ha estudiado un número entero de horas).
¿Cuál es la máxima cantidad de horas que podemos asegurar que ha estudiado,
en total, durante dos dı́as consecutivos?

Solución
Vemos que 120 > 8 · 14. Según el principio de las cajas, esto significa que en
alguna caja hay 9 horas (o sea, que algún dı́a ha estudiado 9 horas). De hecho
8 · 14 = 112 y, por lo tanto, hay 8 cajas con 9 horas o una caja con 10 horas y
7 cajas con 9 horas, etc.
Combinatoria: Muestras ordenadas 3

En el peor de los casos, respecto a considerar un par de dı́as consecutivos,

tendrı́amos una distribución como la siguiente:

9−8−9−8−9−8−9−8−9−8−9−8−9−8

Pero esta distribución da un total de 119. Por lo tanto en alguna caja debe
haber una hora de más. Esto significa que podemos asegurar que hubo un par
de dı́as consecutivos en los que estudió al menos 18 horas.

6. (p2000-pac11 ) En el conjunto de todos los números naturales mayores o iguales

que 1 y más pequeños o iguales que 1010 , ¿hay más números que contienen algún
9, o bien, hay más que no contienen ninguno?

Solución
Calculamos los números entre 1 y 1010 que no contienen ningún 9: son los
números de 10 cifras que se pueden formar utilizando, sólo, las cifras 0, 1, 2, 3, 4, 5, 6, 7
y 8 (los números de, por ejemplo, 3 cifras se pueden escribir como un número
de 10 cifras con las primeras 7 cifras iguales a 0 ).
Ası́, se pueden escribir 910 = 3486784401 números sin ningún 9. Por lo tanto,
se pueden escribir 1010 − 910 = 6513215559 números con algún 9. En definitiva,
hay más números con algún 9 que sin ningún 9, prácticamente el doble.

7. (p2000-final1 ) ¿Cuántos números impares entre 1000 y 9999 tienen todas las
cifras diferentes?

Solución
Sólo hace falta contar cuántos números se pueden poner en cada posición decimal
y multiplicarlos. En las unidades sólo pueden ponerse los números impares (5),
en los millares pueden ir los 8 números restantes (sin el 0 y el que se ha puesto
en las unidades), en las centenas pueden ir también 8 cifras (todas excepto las
de las unidades y los miles) y, finalmente, en las decenas pueden ir 7 cifras. Por
lo tanto, hay 5 × 8 × 8 × 7 = 2240 números impares entre 1000 y 9999.

8. (t2000-p1 ) La plaza de Torre de Palomas está embaldosada con baldosas

en forma de hexágonos regulares. El lado de cada una mide 50 cm y la plaza
es de tal forma que contiene exactamente 1600 baldosas enteras. Las palomas
son una de las distracciones de esta plaza y, para nutrirlos, la gente se los echa
pienso. Calcula el número de granos de pienso que hace falta echar en la plaza
para que se pueda asegurar que, como mı́nimo, hay dos granos a una distancia
menor de 50 cm. ¿Y si la distancia debe ser menor que 10 cm, cuántos granos
son necesarios?

Solución
Combinatoria: Muestras ordenadas 4

Un hexágono regular se puede dividir en 6 triángulos equiláteros; ası́, la plaza

se puede dividir imaginariamente en 6·1600 = 9600 triángulos equiláteros (ca-
jas). Si conseguimos asegurar que al menos dos granos están a la misma caja
podremos concluir que al menos dos granos estarán a distancia menor de 50
cm. Esto pasará cuando echamos 9601 granos.
En cuanto a la otra cuestión, cada uno de los triángulos anteriores se puede
dividir en 25 triángulos equiláteros siguiendo un proceso similar a un ejercicio de
la autoevaluación: se divide cada lado de un triángulo imaginario en 5 segmentos
iguales y se marcan los puntos de división; después se trazan rectas paralelas
a los lados del triángulo por estos puntos. De este modo se obtienen los 25
triángulos equiláteros pequeños contenidos en cada triángulo imaginario. Si hay
9600 triángulos imaginarios y cada uno contiene 25 triángulos equiláteros de 10
cm de lado, en total, se puede dividir la plaza en 9600·25 = 240000 triángulos
equiláteros de 10 cm de lado. Otra vez, por el principio de las cajas, si lanzamos
240001 granos a la plaza, como mı́nimo habrá 2 que se encuentran en uno de
estos triángulos pequeños y, por lo tanto, a distancia menor de 10 cm.

9. (t2000-p2 ) Un paı́s ha hecho un papel poco brillante en las últimas olimpiadas.

Un diario local propone, para apaciguar algo los ánimos, la creación de la
vicemedalla; la vicemedalla es la distinción que se otorga a quien obtiene el
cuarto lugar en cualquiera de las competiciones. Ası́, para los redactores de
este insigne diario, los cuatro premios importantes son: el primero (oro), el se-
gundo (plata), el tercero (bronce) y el cuarto (vicemedalla). De este modo, los
resultados de los deportistas de este paı́s mejoran sustancialmente, porque a su
representación hay muchos vicemedallistas (prácticamente tantos como medal-
listas).
En una prueba atlética participan 12 competidores, 3 de los cuales son compa-
triotas de los mencionados redactores. Suponemos que todos los participantes
acaban correctamente la carrera (es decir, en una de las 12 posiciones, sin aban-
donar o quedar descalificados). Contesta:

(a) ¿De cuántas formas diferentes pueden llegar estos 12 corredores?

(b) ¿De cuántas maneras se pueden repartir las tres medallas entre los 12
corredores?
(c) Y si se añade el generoso premio de la vicemedalla, ¿de cuántas formas
diferentes se pueden repartir los premios?
(d) ¿De cuántas formas diferentes pueden llegar los 3 compatriotas de los
redactores?
(e) ¿En cuántas de estas posibilidades, alguno de estos 3 competidores recibe
un premio oficial? ¿Y en cuantas reciben algún premio, si se incluye la
vicemedalla?

Solución
Combinatoria: Muestras ordenadas 5

(a) Se trata de permutar los 12 corredores; es decir,

P ()12 = 12! ' 4. 79 × 108
(b) Hay tres premios a repartir entre 12 corredores; si enumeramos del 1 al 12
estos corredores, entonces debemos hacer 3-muestras ordenadas sin repeti-
ción (evidentemente un participante no puede llevarse dos medallas) de
estos 12 números. Por lo tanto, el resultado es:
12!
V (12, 3) = (12−3)! = 1320

(c) En este caso el razonamiento es el mismo y el resultado, por lo tanto, es

12!
V (12, 4) = (12−4)! ' 1. 188 × 104

(d) La idea es la misma que al apartado 2: se deben hacer 3-muestras orde-

nadas de las 12 posiciones posibles. Por ejemplo, si los 3 participantes se
denominan, pongamos por caso, P1, P2 y P3,
la muestra (3,4,9) indica que P1 ha sido 3, P2 ha sido 4 y P3 ha sido
9.
la muestra (4,6,1) indica que P1 ha esta 4, P2 ha sido 6 y P3 ha sido
1. Es decir, volvemos a buscar el número de 3-muestras ordenadas de 12
elementos, por lo tanto,
12!
V (12, 3) = (12−3)! = 1320

(e) En el primer caso, como contarlas directamente es muy pesado (porque

debemos considerar las diferentes posiciones de cada uno de estos 3 com-
petidores), hacemos estos 2 pasos:

1) Buscamos aquellas posibilidades en las que no hay ningún medallista

entre los tres compañeros: debemos repartir estos 3 personajes entre
las 9 posiciones no premiadas, por lo tanto, las posibilidades son
9!
V (9, 3) = (9−3)! = 504
2) Restémoslas del total de posibilidades, 1320, que hemos encontrado
antes:
1320 − 504 = 816
Es decir, hay 816 posibilidades de que alguno de estos tres esforzados
competidores obtenga una medalla.

En el supuesto de que hubiera 4 premios, el razonamiento es el mismo:

8!
V (8, 3) = (8−3)! = 336
Es decir, hay 1320−336 = 984 posibilidades de que obtengan algún premio
entre los 3 si se premian los 4 primeros.

10. (t2000-pac12 ) ¿Cuántos números de 5 dı́gitos se pueden hacer con los

números 1, 2, 3, 4, 5, 6, 7, 8 que sean capicúas?
(Indicación: un número capicúa es el mismo leı́do de derecha a izquierda que de
izquierda a derecha)
Combinatoria: Muestras ordenadas 6

Solución
Para hacer un número capicúa de 5 dı́gitos, sólo debemos escoger tres posiciones
puesto que las otras dos quedarán fijadas por las dos primeras. Además, cada
dı́gito se puede repetir en más de una posición. Ası́, tenemos 8 posibilidades
para la x, 8 para la y y 8 para la z.
8 · 8 · 8 = 512

11. (t2001-pac12 ) Queremos codificar 38 sı́mbolos alfanuméricos (28 letras y 10

cifras) en palabras de longitud k de un alfabeto binario A = {0, 1}. ¿Cuál es la
mı́nima longitud k necesaria por poderlo hacer? ¿Y si el alfabeto fuera ternario?

Solución
Se debe cumplir que 2k ≥ 38, por lo tanto k ≥ 6. Ası́ la longitud mı́nima es 6.
En el caso ternario se debe cumplir 3k ≥ 38 y, por lo tanto, k ≥ 4.

12. (t2001-pac13 ) Suponemos que queremos repartir k objetos diferentes entre

n personas, k ≤ n. ¿De cuántas maneras lo podemos hacer si

(a) cada persona puede recibir como mucho un objeto?

(b) cada persona puede recibir más de un objeto?

Solución
n!
a) V (n, k) = (n−k)! ; b) nk

13. (t2001-pac41 )

(a) Demuestra que si elegimos 5 puntos cualesquiera en el interior de un

cuadrado de lado 2 unidades,
√ al menos dos de ellos se encuentran a una
distancia no superior a 2.
(b) ¿Cuántos puntos hemos de elegir, como mı́nimo, para poder √ asegurar que
2
al menos dos de ellos estarán a una distancia no superior a ?
3

Solución
Es un problema tı́pico del principio de las cajas.

(a) En un cuadrado de lado 2 unidades podemos dibujar cuatro cuadrados

en el interior uniendo los puntos medios de cada lado. Dados 5 puntos
cualesquiera dentro del cuadrado grande al menos dos de ellos estarán
dentro del mismo cuadrado. Pero la máxima distancia a la que están los
Combinatoria: Muestras ordenadas 7

puntos
√ dentro
√ del mismo cuadrado viene dada por la diagonal, que vale
1 + 1 = 2.
√
2 1
(b) es el valor de la diagonal de un cuadrado de lado (puesto que la
3 r3 
1 2  1 2
hipotenusa –que es la diagonal de este cuadrado– vale + =
√ 3 3
2
). En un cuadrado de lado 2 se pueden hacer 5 verticales y 5 horizon-
3
1
tales separadas entre ellas y esto nos da 36 cuadrados que cumplen lo
3
que queremos. Para asegurar que dos puntos dados están dentro de uno
de estos cuadrados nos deben dar un mı́nimo de 37 puntos.

14. (p2002-pac11 ) Calcula a medida del conjunto formado por todas las 4-listas
que se pueden hacer con los sı́mbolos {0, 1, . . . 9} tales que el 5 se encuentre
tanto en la 1a como en la 2a posición, o bien que el 7 se encuentre tanto en la
2a como en la 3a posición.
Repite problema suponiendo, ahora, que el 5 se encuentre tanto en la 1a como
en la 2a posición, o bien, que el 5 se encuentre tanto en la 2a como en la 3a
posiciones.

Solución
Las 4-listas en las que aparece el 5 en 1a y 2a posición son 102 y aquellas en las
que aparece el 7 en 2a y 3a posición son, también, 102 .
El resultado que nos piden es: 102 + 102 = 200.
La segunda parte del problema es parecido pero debemos restar la intersección
entre los dos conjuntos (el de 4-listas que tiene un 5 en las posiciones 1-2 y el
de 4-listas que tiene un 5 en las posiciones 2-3). Esta intersección está formada
por las 4-listas que tienen un 5 en las posiciones 1-2-3 y de estas listas ha 10.
El resultado que nos piden es 102 + 102 − 10 = 190.

15. (p2002-final5 ) Las placas de matrı́cula de los vehı́culos de un cierto paı́s

constan de 4 letras (cogidas de un abecedario de 20) seguidas de 3 cifras deci-
males.

(a) ¿Cuántas placas diferentes pueden hacerse?

(b) ¿Cuántas placas diferentes pueden hacerse en las que tanto la parte literal
como numérica sea capicúa?

Solución

(a) En cada lugar donde debemos colocar una letra tenemos 20 posibles man-
eras de hacerlo y los lugares donde va un número tenemos 10 posibilidades.
Combinatoria: Muestras ordenadas 8

En total 204 · 103 = 160,000,000.

(b) Sólo podemos colocar la letra que queramos en las dos primeras posiciones,
puesto que las otras dos letras vienen determinadas por las que ponemos
a las primeras posiciones. En cuando a las cifras, podemos colocar las que
queramos en las dos primeras posiciones, la última viene determinada por
la primera. En total: 202 · 102 = 40,000.

16. (p2002-final9 ) Calcula cuántas listas de longitud 4 se pueden hacer con

las nuevo cifras decimales no nulas si no podemos utilizar la misma cifra en las
posiciones 1 y 2; 2 y 3; 3 y 4; 1 y 3; 1 y 4. (Indicación: se deben cumplir las cinco
condiciones a la vez).

Solución
Las posibilidades que tenemos para las cuatro cifras son: que sean todas cuatro
diferentes; que haya tres de diferentes y la segunda cifra coincida con la cuarta.
En el primer caso lo podemos hacer de V (9, 4) maneras y en el segundo caso de
V (9, 3) maneras.
El resultado es: V (9, 4) + V (9, 3) = 9 · 8 · 7 · 6 + 9 · 8 · 7 = 3024 + 504 = 3528.

17. (t2002-pac12 )

Con las letras {m, r, s, t, x, a, o, e, u} se componen todas las palabras posi-

bles de nuevo letras de forma que cada vocal esté intercalada entre conso-
nantes y que no se repita ninguna letra. ¿Cuántas palabras encontraremos?
Con las letras {m, r, s, t, x, a, o, e, u} se componen todas las palabras posi-
bles de diez letras de forma que no haya dos letras iguales juntas. ¿Cuántas
palabras encontramos?

Solución

Un ejemplo del que nos piden serı́a la palabra sorametux.

Para componer estas palabras hemos de coger cualquier consonante (es-
to lo podemos hacer de 5 maneras), entonces hemos de añadir cualquier
vocal (esto lo podemos hacer de 4 maneras), a continuación añadir una
consonante de las que quedan (esto lo podemos hacer de 4 maneras), etc.
Aplicando la regla del producto el resultado será: 5·4·4·3·3·2·2·1·1 = 2880.
Utilizaremos la regla del producto como en el apartado anterior. Como
primera letra de las palabras que queremos componer podemos poner
cualquiera (esto lo podemos hacer de 9 maneras). La segunda letra puede
ser cualquiera de las otras ocho (sólo debe ser diferente de la que hemos
considerado en primer lugar). La tercera letra puede ser cualquiera de las
ocho letras diferentes de la que hemos considerado en segundo lugar, etc.
Combinatoria: Muestras ordenadas 9

El resultado será, pues, 9 · 8 · 8 · · · 8 = 9 · 89 = 1207959552.

18. (t2002-pac13 ) En el aeropuerto de la Seu d’Urgell hay 673 personas es-

perando por embarcar en uno de los cuatro vuelos con destino en Girona. Estas
personas, provenientes de siete pueblos de la comarca, han comprado el billete
de avión en una de las seis agencias que operan en cada pueblo.
Demuestra que hay, como mı́nimo, un grupo de tres personas del mismo sexo y
del mismo pueblo que han comprado el billete en la misma agencia y que vuelan
en el mismo avión.

Solución
Es una aplicación del principio de las cajas. Consideramos sólo el pueblo de
procedencia de las 673 personas. Podemos asegurar que hay un mı́nimo de 97
personas del mismo pueblo (pero no sabemos qué pueblo).
Restringiendo el problema a estas 97 personas y volviendo a aplicar el principio
de las cajas considerando, ahora, el avión en el que vuelan podemos concluir
que un mı́nimo de 25 personas del mismo pueblo volarán en el mismo avión.
Volviendo a restringir el problema a estas 25 personas del mismo pueblo y
que vuelan al mismo avión, pero considerando, ahora, la agencia en que han
comprado el billete, podemos decir que un mı́nimo de 5 personas del mismo
pueblo vuelan en el mismo avión y han comprado el billete a la misma agencia.
Finalmente, considerando el sexo, podemos asegurar que un mı́nimo de tres de
ellas serán del mismo sexo.

19. (p2003-pac12 ) ¿Cuál es el mı́nimo número de estudiantes que debe tener

un aula de Matemática Discreta para estar seguros que al menos 12 estudiantes
recibirán la misma nota? Suponemos que las calificaciones posibles son: D, C–,
C+, B, A.

Solución
Teniendo en cuenta que hay cinco calificaciones diferentes, si el número de estu-
diantes, n, cumple n > 5 · (12 − 1) = 55, entonces, por el principio de las cajas
generalizado, podemos asegurar que, como mı́nimo, habrá doce estudiantes que
tendrán una misma calificación. Por lo tanto, como mı́nimo necesitamos 56 es-
tudiantes en el aula.

20. (p2003-pac21 ) En una reunión celebrada a Bruselas con dos representantes

de Israel, dos representantes de Palestina y dos representantes de los Estados
Unidos y presidida por el secretario general de la ONU, el Sr. Kofi Anan, los
encargados de preparar la reunión decidieron que se harı́a en una mesa redonda,
pero no se acaban de decidir sobre como colocar a los 7 participantes.
Combinatoria: Muestras no ordenadas 10

(a) ¿De cuántas maneras se pueden colocar los 7 participantes a la mesa?

(b) Los organizadores pensaron que muy probablemente los representantes
palestinos querrı́an sentarse juntos, ¿de cuántas maneras se pueden colocar
los participantes en este caso?
(c) ¿De cuántas maneras se pueden colocar los participantes si los represen-
tantes palestinos además de querer sentarse juntos no querı́an sentarse
junto a un representante de Israel?

Solución
(a) 6! = 720; (b) 2 · 5! = 240; (c) 2 · 3! · 3! = 72

21. (t2004-pac11 )

(a) ¿Cuántos números naturales entre 1 y 999999 (ambos incluidos) son capicúa?
Un capicúa es un número que tiene la misma secuencia de cifras si lo lees
de derecha a izquierda que de izquierda a derecha. Por ejemplo, 87378 o
919.
(b) Suponiendo que la respuesta del apartado anterior es más grande que
1950, demuestra que, de todos los números capicúa entre 1 y 999999, hay al
menos un subconjunto de 37 cuyas cifras suman lo mismo ({8, 44, 323, 2222, 3113}
es un ejemplo de subconjunto de 5 capicúas cuyas cifras suman lo mismo).

Solución

(a) Hay 9 capicúas de una cifra, y 9 de dos cifras. Con respecto a los de tres
cifras, la primera y la tercera deben ser iguales y diferentes de 0, y la
segunda cifra puede ser cualquiera. En total, tenemos 9 × 10 capicúas de
tres cifras. Con respecto a los de cuatro cifras, podemos escoger las cifras
primera (que debe ser diferente de 0) y segunda, puesto que la tercera
y la cuarta quedarán determinadas. En total, tenemos 9 × 10 capicúas
de cuatro cifras. Análogamente, se calcula que hay 9 × 10 × 10 capicúas
de cinco cifras y 9 × 10 × 10 capicúas de seis cifras. En total, tenemos
9 + 9 + 90 + 90 + 900 + 900 = 1998 capicúas.
(b) Si sumamos todas las cifras de un capicúa, podemos obtener resultados
que van de 1 (la suma de la única cifra del capicúa 1) hasta 54 (la suma
de las cifras del capicúa 999999). Tenemos, pues, 54 cajas donde situamos
todos los capicúas dependiente del resultado que produzca la suma de sus
cifras. Entonces podemos aplicar el principio de las cajas generalizado,
puesto que 1950 > 54 · 36.
Capı́tulo 2

Combinatoria: Muestras no
ordenadas

22. (p99-pac13 ) Un entrenador de fútbol convoca por un partido 3 porteros, 7

defensores, 5 jugadores de medio campo y 6 delanteros. La estrategia de este
entrenador es la de jugar con 4 defensores, 3 medios y 3 delanteros, aparte
del portero. ¿Cuántos equipos diferentes puede confeccionar con esta plantilla,
siguiendo su sistema de juego?
Supón, ahora, que el entrenador siempre escoge 2 defensores, 2 medios y 1 de-
lantero fijos, de entre todos los que tiene a su disposición, ¿cuántos posibles
equipos puede hacer, ahora, con estas condiciones?

Solución
Se deben escoger uno entre los tres porteros, 4 entre los 7 defensores, 3 entre los
5 medios y 3 entre los 6 delanteros, por lo tanto, los posibles equipos son:
3· 74 · 53 · 63 = 21 000 equipos

Por otro lado, si siempre escogiera 2 defensores, 2 medios y 1 delantero, las

posibilidades de elección se reducen. El número de posibles equipos, en este
caso es
3· 52 · 31 · 52 = 900 equipos

Este problema también se puede resolver, si se es muy puntilloso, atendiendo al

hecho que un delantero, por ejemplo, puede ocupar varias posiciones (derecha,
izquierda, central, etc). Si queremos dar cuenta de esta diversidad de posiciones
en una misma lı́nea habremos de recurrir a las variaciones (y no, como anteri-
ormente, a las combinaciones).

23. (p99-pac14 ) Un internauta tiene las direcciones electrónicas de 8 amigos

almacenadas. Por Navidad quiere enviar un mensaje diferente para cada uno de
sus amigos. En el momento de enviarlo, decide hacerlo al azar ¿qué probabilidad
hay que algún de sus amigos reciba el mensaje correcto? Joan es uno de los sedes
amigos, ¿qué probabilidad tiene Joan de recibir correctamente su mensaje? Pere

11
Combinatoria: Muestras no ordenadas 12

es otro de los amigos del internauta, ¿qué probabilidad hay que Joan y Pere
reciban su mensaje correctamente? ¿Qué probabilidad hay que ni Joan ni Pere
reciban correctamente su mensaje?

Solución
Este problema es, de hecho, una versión actualizada del problema
de los desar-
reglos ahora con 8 direcciones y 8 mensajes. En este caso ap = p8 (8 − p)!. De
este modo,
D = 8! − a1 + a2 − a3 + a4 − a5 + a6 − a7 + a8 = 14 833
por lo tanto, la posibilidad que cabe de sus amigos reciba el mensaje correcto
es
D 2119
8! = 5760 = 0. 367 88
ası́, la probabilidad que uno de los suyos amigos la reciba es 1 − 0. 367 88 = 0.
632 12.
1
En Joan, uno de los sedes amigos tiene una probabilidad de 8 = 0. 125 que le
llegue correctamente su carta.
La probabilidad que, tanto Joan como Pere reciban correctamente sus cartas,
es
6!
8! = 1
56 = 1. 785 7 × 10−2 .
La probabilidad que ni la uno ni el otro la reciban correctamente: calculamos
las posibilidades de que, o bien, Joan la reciba correctamente, o bien, Pere la
reciba correctamente. Sean
J = {situaciones en las que Joan recibe correctamente su carta}
P = {situaciones en las que Pere recibe correctamente su carta}
Por el principio del cedazo,

|J ∪ P | = |J| + |P | − |J ∩ P | = 7! + 7! − 6!
Por lo tanto, las situaciones en que Joan y Pere no reciben correctamente sus
cartas es igual a 8! − 9360 = 30 960. Finalmente, la probabilidad que Joan y
Pere no reciban correctamente sus cartas es igual a
30960
= 0. 767 86
8!

24. (t99-final2 ) En una residencia de estudiantes se han constituido 4 grupos

para organizar unas jornadas culturales: el grupo de cine, el de teatro, el de
música y el de esparcimiento. Cada estudiante pertenece, como mı́nimo, a uno
de estos grupos. Hay dos estudiantes que participan en los cuatro grupos. Hay
25 estudiantes en cada uno de los grupos, 15 que simultanean su participación
en cada par de grupos y 10 en cada tres de los cuatro grupos.
¿Cuántos estudiantes hay en la residencia?

Solución
Combinatoria: Muestras no ordenadas 13

Digamos C, T, M, E los cuatro grupos:

|C ∪ T ∪ M ∪ E| = |C| + |T | + |M | + |E| − |C ∩ T | − |C ∩ M | · · · |M ∩ E| + |C ∩
T ∩ M | + · · · + |T ∩ M ∩ E| − |C ∩ T ∩ M ∩ E| =
25 + 25 + 25 + 25 − 15 − 15 · · · − 15 + 10 + · · · + 10 − 2 =
   
4 4
25 · 4 − 15 + 10 − 2 = 48
2 3

25. (t99-final3 ) ¿De cuántas maneras diferentes pueden colocarse 7 libros

diferentes en un estante de forma que tres libros determinados estén siempre
separados?

Solución
De entrada debemos colocar los tres libros (designémoslos con una X) de forma
que estén separados (los cuatro libros que pueden ir juntos designémoslos genéri-
camente con una Y ). O sea tendrı́amos una configuración como la siguiente:

XY XY X

Ahora tenemos de añadir los dos libros Y que nos quedan. Los pueden colocar
antes de la primera X, entre las dos primeras X, etc. Esto podemos hacerlo
de tantas maneras como combinaciones con repetición de 4 objetos (los cuatro
lugares en donde podemos colocar los dos libros
Y que nos quedan por colocar)
cogidos de 2 en 2. Esto da un total de 4+2−1
2 = 10.
Cada una de las anteriores maneras de colocar los libros admite permutar los
tres libros X de P (3) maneras diferentes y los cuatro libros Y de P (4) maneras
diferentes.
En definitiva lo que nos piden es:

10P (3)P (4) = 10 · 6 · 24 = 1440

26. (t99-final7 ) ¿Cuántos bytes pueden formarse utilizando exactamente 6

ceros?

Solución
Un byte son ocho bits y queremos que seis de ellos sean ceros. Cada una de estas
situaciones corresponden a seleccionar seis lugares de entre los ocho lugares
posiblesque
 podemos poner los ceros en un byte. En total, pues, podremos
8
formar = 28 bytes.
6

27. (t99-final9 ) Encuentra el número de permutaciones de los nueve dı́gitos

1, 2, 3, 4, 5, 6, 7, 8, 9 en las cuales
Combinatoria: Muestras no ordenadas 14

(a) los bloques 12, 34 y 567 no aparecen

(b) los bloques 12, 23 y 415 no aparecen

Solución

(a) Permutaciones en las que los bloques 12, 34 y 567 no aparecen.

De permutaciones de 9 dı́gitos hay P (9), pero le debemos descontar aque-
llas en las que figura el bloque 12.
Podemos considerar que el bloque 12 tiene entidad propia y, entonces,
junto con los otras dı́gitos 3, 4, 5, 6, 7, 8, 9 hacer todas las posibles per-
mutaciones. En total habrá P (8).
Del mismo modo, de permutaciones en las que figura el bloque 34 hay
P (8) y de permutaciones en las que figura el bloque 567 hay P (7).
Al restar del total P (9) las permutaciones en las que aparece el bloque
12 y aquellas en las que aparece el bloque 34, hay permutaciones que las
hemos restado dos veces. Son aquellas en las que aparece el bloque 12 y,
también, 34. Análogamente con los otros bloques.
Por lo tanto el que nos piden es:

P (9) − P (8) − P (8) − P (7) + P (7) + P (6) + P (6) − P (5) = 283560

(b) Permutaciones en las que los bloques 12, 23 y 415 no aparecen.

El problema es parecido al anterior. La diferencia es que en las permuta-
ciones en las que aparece el bloque 12 estamos seguros que el bloque 415
no aparece, etc.
Lo que nos piden es:

P (9) − P (8) − P (8) − P (7) + P (7) + P (6) = 282960

28. (p2000-pac13 ) En la última promoción del ejército coinciden al mismo cuartel

5 catalanes y 7 gallegos. Estos soldados se deben poner en fila. Los catalanes
están peleados entre ellos y, para evitar problemas, no puede haber dos de juntos.
¿De cuántas formas se puede hacer esta fila?

Solución
Entre dos catalanes siempre hay de haber un gallego, por lo tanto, la posición de
los catalanes y los gallegos son cgcgcgcgcgcgcgc, donde c indica la posibilidad
que haya un catalán, mientras que g indica que hay un gallego.
Los gallegos se pueden distribuir de P (7) formas. Los catalanes pueden dis-
tribuirse de P (5) 85 , por lo tanto, la fila se puede formar de

 
8
P (7)P (5)
5
Combinatoria: Muestras no ordenadas 15

formas diferentes.

29. (p2000-pac16 ) Tras el escrutinio de las quinielas del el pasado domingo

(quiniela de 15 resultados)

(a) ¿Cuántas quinielas diferentes pueden tener exactamente 14 aciertos?

(b) ¿Cuántas quinielas diferentes pueden tener exactamente 13 aciertos?
(c) ¿Qué cantidad de aciertos deberı́a ser la más habitual, si suponemos que
las quinielas se han llenado al azar? ¿Por qué?

Solución

(a) Se deben de acertar 14 de los 15 resultados y el otro se debe fallar. Por lo

tanto, sólo hay una posibilidad para las casillas acertadas y 2 posibilidades
por la casilla errada. Ahora bien, el desacierto puede estar en cualquiera
de los 15 partidos. Por lo tanto, las posibles quinielas con exactamente 14
aciertos es 2 × 15 = 30 quinielas.
(b) Se han de acertar 13 de los 15 resultados y el otro se debe fallar. Por lo
tanto, hay una posibilidad para cada casilla acertada y 2 posibilidades por
las 2 casillas erradas. Es decir, hay 22 quinielas que equivocan 2 partidos
determinados. Las formas de escoger estos 2 partidos de los 15 es igual
a 15


2 . Por lo tanto, las quinielas diferentes que aciertan exactamente 13
aciertos son 22 15


2 = 420.
(c) En general, el número de quinielas que se equivocan en k resultados es
igual a
2k 15!
 
k 15
2 =
k k!(15 − k)!

Los resultados para los diferentes valores de k son:

k=1 30 k=2 420

k=3 3640 k=4 21840
k=5 96096 k = 6 320320
k = 7 823680 k = 8 1647360
k = 9 2562560 k = 10 3075072
k = 11 2795520 k = 12 1863680
k = 13 860160 k = 14 245760
k = 15 32768

Por lo tanto, el número más habitual de errores se da para k = 10, es

decir, que el número más habitual de aciertos deberı́a ser 5.
Combinatoria: Muestras no ordenadas 16

30. (p2000-final10 ) 4 americanos, 3 rusos y 5 chinos aprenden a bailar sardanas.

¿De cuántas maneras diferentes pueden hacer el cı́rculo para bailar una sardana
todos juntos, si los de un mismo paı́s no pueden estar todos juntos?
(Observación: para bailar una sardana se ponen los participantes en cı́rculo
cogidos de la mano. Normalmente, siempre se intercalan un hombre y una mujer,
pero en este caso debes suponer que se pueden mezclar hombres y mujeres de
cualquier manera.)

Solución
Denominamos R el conjunto de cı́rculos en que los rusos se encuentran juntos,
A, la de los americanos juntos, y X, la de los chinos juntos.
El número de cı́rculos que cumplen que no están los de un mismo paı́s todos
juntos es igual a:

11! − |R| − |A| − |X| + |R ∩ A| + |R ∩ X| + |A ∩ X| − |R ∩ A ∩ X| =

11! − 9!3! − 8!4! − 7!5! + 6!4!3! + 5!3!5! + 4!5!4! − 2!4!3!5! = 36391680

31. (p2001-pac12 ) En los lenguajes de programación se utilizan identificadores

para hacer referencia a varios objetos: constantes, variables, funciones,...
Normalmente un identificador está formato por una serie de caracteres, letras
del alfabeto (’a’,..,’z’,’A’,..,’Z’) y dı́gitos numéricos (’0’,..,’9’) em-
pezando siempre por una letra. Por ejemplo, a1, Jet, NUM, n36, AddNode
son identificadores válidos, pero 1a, 3jda no se considerarı́an válidos porque
empiezan por un dı́gito o contienen caracteres que no son letras ni dı́gitos.

(a) ¿Cuántos identificadores de 8 caracteres podemos formar? ¿Y si todos los

caracteres deben ser diferentes?
(b) Si consideramos identificadores con un máximo de 6 caracteres, ¿cuántos
identificadores podemos formar con todos los caracteres diferentes?
(c) Si se consideran equivalentes las letras mayúsculas y minúsculas, ¿cuántos
identificadores con un máximo de 6 caracteres diferentes podremos formar?
(d) ¿Cuántos de los identificadores del apartado anterior tendrán, al menos,
una vocal?

Solución
Suponemos que tenemos 26 letras minúsculas, 26 mayúsculas y 10 dı́gitos.

(a) El número total de identificadores de 8 caracteres serán:

52 × V R(62, 7) = 52 × 627 = 183123959522816
Si todos el caracteres deben ser diferentes, entonces la solución será:
52 × V (61, 7) = 52 × 61 × 60 × 59 × 58 × 57 × 56 × 55 = 600956640
Combinatoria: Muestras no ordenadas 17

(b) En este caso, los identificadores pueden tener longitud de 1 a 6. La solución

será:
X5
52(1+ V (61, y)) = 52(1+V (61, 1)+V (61, 2)+V (61, 3)+V (61, 4)+V (61, 5)) = 37785374744
y=1

(c) Este caso es como el anterior pero ahora sólo hace falta considerar 26
letras y 10 dı́gitos:

X5
26(1+ V (35, y)) = 26(1+V (35, 1)+V (35, 2)+V (35, 3)+V (35, 4)+V (35, 5)) = 1046577376
y=1

(d) Calculamos, primero, cuántos identificadores no tienen ninguna vocal:

X5
21(1+ V (30, y)) = 21(1+V (30, 1)+V (30, 2)+V (30, 3)+V (30, 4)+V (30, 5)) = 373457721
y=1

Restando de la cantidad del apartado anterior obtendremos el resultado

deseado:
1046577376 − 373457721 = 673119655

32. (p2001-pac21 ) Una persona que tiene 8 amigos, ha prometido salir cada dı́a
del año con un amigo diferente o con un grupo diferente de amigos.
¿Puede llevar a cabo su propósito?

Solución
Puede salir cada dı́a con un grupo de i amigos (i puede valer desde 1 hasta 8).
Las maneras
  de hacerlo serán las combinaciones de 8 elementos cogidos de i en
8
i, o sea .
i
Al variar i desde 1 hasta 8 nos dará como soució
8  
X 8
= 28 − 1 = 255
y=1
i

La respuesta al problema, será pues, negativa.

33. (p2001-pac23 ) En un tablero de ajedrez de 8 × 8 casillas, ¿de cuántas formas

diferentes se pueden colocar 8 torres iguales de forma que ninguna esté en la
diagonal principal ni se puedan matar entre ellas? (dos torres están en posición
de matarse si están a la misma fila o en la misma columna).

Solución
Combinatoria: Muestras no ordenadas 18

Es un problema de desarreglos. Pongamos 1 en la primera casilla de la diagonal

principal, 2 en la segunda casilla de la diagonal principal, etc. tal y como indica
la figura:

1
2
3
4
5
6
7
8

Entonces las ocho torres (que podemos numerar del 1 al 8) han de situarse, re-
spectivamente, la torre 1 en la fila 1, la torre 2 en la fila 2, etc. sin que coincida
la torre y con la columna y y sin que dos torres estén en la misma columna.
Cada colocación equivale a escribir las columnas en las que situaremos, respec-
tivamente, la torre 1, la torre 2, etc., o sea una permutación de los elementos
del conjunto {1, 2, · · · , 8} en la que ninguna y se encuentra en el lugar y.
El resultado es, pues, el número de desarreglos de 8 elementos, D = 8! − a1 +
a2 − a3 + a4 − a5 + a6 − a7 + a8 = 20160 − 6720 + 1680 − 336 + 56 − 8 + 1 = 14833

34. (p2001-pac24 ) Siete personas no relacionadas entre ellas llegan a la recepción

de un edificio que tiene cuatro pisos más, entran al ascensor y cada una elige
uno de los cuatro pisos. ¿Cuántas de las posibles selecciones de las siete personas
tienen como resultado que el ascensor se pare en cada piso por dejar pasajeros?
Indicación: Consideramos que dos selecciones son iguales sólo si baja la misma cantidad de
personas en cada piso, independientemente de cuáles son estas personas.

Solución
Podemos suponer que hacemos las diferentes combinaciones con repetición CR(4, 7)
de 4 elementos (los cuatro pisos) cogidos de 7 en 7 (cada persona escoge un piso
de los cuatro). Pero en este cálculo no tenemos en cuenta que queremos que cada
piso esté representado (al menos una vez) en estas combinaciones que cogemos.
O sea que si empezamos por seleccionar cada uno  de los  cuatro pisos, entonces
4+3−1
el problema se reducirá a calcular CR(4, 3) = = 20.
3
También podı́amos haber considerado el cálculo de las soluciones enteras y pos-
itivas de la ecuación a + b + c + d = 7, ası́ como también se podı́a enfocar a
través del cálculo con funciones generadoras.

35. (p2001-pac41 ) Queremos colocar 10 personas (5 parejas) alrededor de una

mesa circular. Dos disposiciones se consideran equivalentes si una es idéntica a
la otra por rotación. Por ejemplo, si las personas son A, B, C, D, E, F; entonces
las disposiciones ABCDEF y CDEFAB se considerarı́an equivalentes.
Combinatoria: Muestras no ordenadas 19

¿De cuántas formas diferentes podemos sentar estas personas alrededor de la

mesa?
Si, además, queremos que dos personas del mismo sexo no estén juntas, ¿de
cuántas formas lo podremos hacer?
De cuántas maneras si queremos que, además, nadie se siente al lado de su
pareja?
Si suponemos que cada persona tiene un lugar asignado a la mesa (por ejemplo,
con una tarjeta con su nombre), de cuántas formas los podremos sentar de tal
manera que ninguna de ellas ocupe una posición que coincida con su tarjeta?

Solución
Siendo la mesa circular, no hay ninguna posición predominante. Ası́, podemos
fijar una de las posiciones. Por ejemplo, podemos fijar la que ocupa la persona
A. Entonces, tenemos 9 personas por poner alrededor de la mesa de todas las
maneras posibles. Esto hace un total de 9! = 362880 disposiciones diferentes.
Si no pueden estar juntas las personas del mismo sexo, entonces debemos tener
en cuenta las diferentes posiciones de la mesa. Si fijamos el lugar que ocupa A,
entonces la posición de su derecha puede ser ocupada de 5 maneras. Las dos
posiciones siguientes, pueden ser ocupadas de 4 maneras, las dos siguientes de 3
maneras, las dos siguientes de 2 maneras. Finalmente, las dos últimas posiciones
(que corresponden a personas de sexo diferente) pueden ser ocupadas de una
única manera. Ası́, hay
5 × 4 × 4 × 3 × 3 × 2 × 2 × 1 × 1 = 2280
maneras de sentar las personas sin que dos del mismo sexo estén juntas.
El tercer apartado es un problema de desarreglos. La solución serı́a el número
de desarreglos de 10 elementos:
10! − a1 + a2 − a3 + a4 − a5 + a6 − a7 + a8 − a9 + a10 = 1334961

36. (p2001-final5 ) ¿De cuántas formas podemos distribuir 7 manzanas y 6

naranjas entre 4 personas, A, B, C, D?
¿Y si queremos que las 4 personas tengan, al menos, una manzana?
¿Y si queremos que la persona A no tenga ninguna manzana, y entre una y dos
naranjas?

Solución
En el primer caso, tenemos
  
4+7−1 4+6−1
= 120 × 84 = 10080
7 6
Ahora, si cada persona debe tener, al menos, una manzana, sólo tendremos tres
manzanas para repartir y el resultado será:
  
4+3−1 4+6−1
= 20 × 84 = 1680
3 6
Combinatoria: Muestras no ordenadas 20

Finalmente, podemos contar el número de distribuciones en las cuales la persona

A tiene una naranja:
  
3+7−1 3+5−1
= 756
7 5
y las distribuciones en las cuales tiene dos naranjas:
  
3+7−1 3+4−1
= 540
7 4
Aplicando el principio de adición, tendremos las 756+540 = 1296 distribuciones
pedidas.

37. (p2001-final8 ) Por un canal de comunicación se vuelan transmitir 12 sı́mbo-

los todos diferentes. Para sincronizar el transmisor y el receptor, entre cada
pareja de sı́mbolos hace falta enviar un mı́nimo de 3 caracteres en blanco. Si en
total se han enviado 45 caracteres en blanco, ¿de cuántas maneras diferentes se
pueden transmitir los 12 sı́mbolos?

Solución
Hay 12! maneras de enviar los 12 sı́mbolos. Entre los 12 sı́mbolos hay 11 posi-
ciones ocupadas por caracteres en blanco. Como que ha de haber un mı́nimo de
3, quedarán 45 − 33 = 12 caracteres en blanco por repartir en las 11 posiciones.
Este reparto se puede hacer de 11+12−1


12 = 646646 maneras.
Ası́, el número total de mensajes diferentes que se pueden enviar es
 
11 + 12 − 1
12! × ' 3,097 × 1014
12

38. (t2000-p3 ) Un número musical de un film americano de los años 40 se

desarrolla en una amplia escalera de 12 peldaños. En principio, cada peldaño
está ocupado por una chica. Este espectacular número consiste en que las chicas
hagan una serie de pasos sobre esta escalera. En un paso la chica puede saltar
1 o 2 escalones, hacia arriba o hacia abajo.

(a) En un momento del número, la chica que se encuentra en lo alto de la

escalera, hace una serie de pasos siempre hacia abajo, que la hacen llegar
abajo de todo de la escalera, fuera de la escalera. ¿De cuántas formas
diferentes puede hacer el descenso esta chica?
(b) En otro momento del número, una chica hace 10 pasos. ¿De cuántas for-
mas diferentes puede hacerlos de forma que se produzcan, exactamente,
5 variaciones entre dos pasos (una variación entre dos pasos se produce
cuando se hace un paso de un escalón y, inmediatamente después, una
paso de 2 escalones o al revés, sin considerar si son hacia arriba o hacia
abajo)?.
Combinatoria: Muestras no ordenadas 21

(c) El coreógrafo de este número, aficionado a la Matemática Discreta en su

escaso tiempo de ocio, quiere que al final de la obra no haya más de una
chica por escalón, y que exactamente la mitad de las chicas se encuentren
en un escalón diferente al que estaban al principio. ¿De cuántas formas
puede conseguir esta distribución?
(d) El productor del film, tras ver la actuación le parece que falta algo. De-
cide que tiene que haber más chicas y que se deben numerar los doce
escalones de abajo arriba. Pero conociendo la afición del coreógrafo por
las Matemáticas, le comunica el número de este modo: ”al final del número,
debe haber 17 chicas sumando todas las que hay a los escalones con
números pares, 16 chicas sumando todas las que hay a los escalones con
números múltiples de 3, 3 chicas sumando todas las que hay a los escalones
con números múltiples de 5, 8 chicas sumando todas las que hay a los
escalones con números múltiplos de 6, 1 chica al escalón numerado con el
10 y 2 chicas sumando todas las que hay a los escalones no mencionados”.
¿Cuántas chicas quiere el productor que aparezcan?

Solución

(a) La chica debe bajar 12 peldaños de 1 o 2 escalones. Por lo tanto, puede

hacer de 6 a 12 pasos.
Si hace 6 pasos, todos son de 2 escalones; por lo tanto, tiene 1 única
posibilidad.
Si hace 7 pasos,

ha hecho 5 pasos de 2 escalones y 2, de 1 escalón; por lo
tanto, tiene 72 = 21 posibilidades
Si hace 8 pasos,

ha hecho 4 pasos de 2 escalones y 4, de 1 escalón; por lo
tanto, tiene 84 = 70 posibilidades
En definitiva, las posibilidades de bajar las escaleras son:
P6 6+k


k=0 2k = 233
(b) El total son 10 pasos: hay 9 posibles variaciones, de las cuales sólo quere-
mos 5; por lo tanto, si la chica empieza de una manera determinada (por
ejemplo, un paso de 1 escalón), puede hacer 95 = 126 bajadas con 5

variaciones de paso. Ahora bien, tiene dos posibilidades para empezar (un
paso de 1 escalón y un paso de 2 escalones). En definitiva, puede hacer 10
pasos que incluyen 5 variaciones de 2 95 = 252 maneras diferentes.

(c) La manera de
escoger 6 de las 12 chicas de forma que estén en el escalón

inicial es 12
6 = 924.
El resto de las chicas han de estarPdesordenadas.

Por lo tanto, las posibil-
6
idades de hacerlo son: D6 = 6! + k=1 (−1)k k6 (6 − k)! = 265
En definitiva, hay 924 × 265 = 2. 449 × 105 formas de hacer esta distribu-
ción.
(d) Denominamos Ni ={chicas que se encuentran en una escalera múltiplo de
i}
|N2 | = 17
Combinatoria: Muestras no ordenadas 22

|N3 | = 16

|N5 | = 3
|N6 | = 8
|N10 | = 1

Por lo tanto:
|N2 ∪ N3 ∪ N5 | = 17 + 16 + 3 − 8 − 1 = 27
Faltan dos chicas que se encuentran en otros escalones; por lo tanto, hay
29 chicas.

39. (t2000-final1 ) Tres amigos suben, en la planta baja, a un ascensor de un

edificio de 5 plantas. ¿De cuántas maneras diferentes pueden ir saliendo del
ascensor si en ningún piso baja más de uno de ellos?

Solución
5


3 · 3! = 60.

40. (t2000-final8 ) Una palabra-código consiste en una secuencia de los dı́gitos

1, 2, 3, 4, 5, en la que se permiten repeticiones.

¿Cuántas palabras-código de longitud 10 se pueden construir que no acaben

en 3 o 5?
¿Cuántas palabras-código de longitud n (n ≥ 3) se pueden construir que
tengan dos o tres dı́gitos diferentes?

Solución

Tenemos C(5, 1) maneras para los primeros nuevo dı́gitos y C(3, 1) para
el último. En total 3 · 59 = 5,859,375.
Hay C(5, 2) · (2n − 2) palabras código con dos dı́gitos diferentes y C(5, 3) ·
(3n − 3 · 2n + 3) palabras código con tres dı́gitos diferentes. El total será de
10 · (3n − 2 · 2n + 1).

41. (t2000-final14 ) ¿De cuántas maneras 24 bolas diferentes se pueden colocar

en 3 cajas diferentes con tal que haya el doble de bolas en una caja que en las
otras dos juntas? ¿Y si no ponemos la condición?
Combinatoria: Muestras no ordenadas 23

Solución
Una caja debe tener 16 bolas y las otras dos cajas 8 en total. Hay C(3, 1)
maneras de escoger la primera caja, C(24, 16) maneras de llenarla y C(2, 1)8
maneras de llenar las dos cajas restantes.
El resultado es, pues, C(3, 1) · C(24, 16) · C(2, 1)8 .
Si no tenemos en cuenta la condición el problema se transforma en el cálculo de
las variaciones con repetición de 3 objetos cogidos de 24 en 24, o sea, 324 .

42. (t2000-pac11 ) Un grupo de tres chicas y cinco chicos se espera a que pasen
dos taxis a la salida del Up and Down para poder volver a casa. Subirán cuatro
personas en cada taxi, ¿de cuántas maneras diferentes lo pueden hacer si quieren
que siempre haya al menos una chica en cada taxi?

Solución
3 5



1 3 = 30

43. (t2000-pac14 ) Suponemos que disponemos de 20 pelotas azules idénticas,

18 de rojas idénticas y 10 de amarillas idénticas. Calcula el número de maneras
de seleccionar 16 pelotas (no importa el orden en que hacemos esta selección).

Solución
Este problema lo entenderéis mejor si consideráis que tenéis tres cajas y debéis
escoger 16 pelotas entre las tres cajas. Como las pelotas son indistinguibles y
no importa el orden de la selección, se trata de escoger muestras no ordenadas
con repetición. El problema añadido está en que no podemos escoger 16 pelotas
amarillas puesto que sólo tenemos 10. Si tuviéramos un número
suficiente, la
solución serı́a: escoger n = 16 objetos entre m = 3: 3+16−1 16 , pero debemos
restar los casos en los que escogemos bolas amarillas que no tenemos, es decir,
las muestras que tengan más de 10 bolas amarillas:

1 muestra con 16 bolas amarillas

2 muestras con 15 bolas amarillas
3 muestras con 14 bolas amarillas
4 muestras con 13 bolas amarillas
5 muestras con 12 bolas amarillas
6 muestras con 11 bolas amarillas

en total, hace falta restar 21 muestras.

Observa que esto es equivalente al razonamiento siguiente: como tiene que haber,
al menos, 11 bolas amarillas para eliminar las muestras que sobran, podemos
contar los número de maneras de escoger 5 objetos (las posiciones que nos
quedan) entre 3: 3+5−1


= 21
16+3−1

5+3−1

5
16 − 5 = 153 − 21 = 132
Combinatoria: Muestras no ordenadas 24

44. (t2001-final1 ) En una estanterı́a hay 12 libros alineados en una fila. ¿De
cuántas maneras podemos escoger 5 de forma que nunca cogemos dos que sean
contiguos en el estante (no nos importa el orden de la extracción).

Solución
Suponemos que ya hemos acabado de coger los 5 libros. En el estante nos quedan
7 libros y entre estos libros los 5 agujeros en donde habı́a previamente los libros
que hemos cogido. Denominemos x, y, z, r, s, t, respectivamente, a las cantidades
de libros que nos han quedado en el estante, a la izquierda del todo, desde el
primer libro extraı́do hasta el segundo, del segundo al tercero, etc.
Se debe cumplir que x + y + z + r + s + t = 12 − 5 = 7, las variables deben ser
números enteros no negativos y, además, y, z, r, s deben ser enteros positivos.
De otro modo, el problema consiste en contar la cantidad de soluciones enteras
no negativas de la ecuación x + y + z + r + s + t = 7 − 4 = 3.
 
8
El resultado ya sabemos que es: CR(6, 3) = = 56.
3

45. (t2001-final9 ) Dadas las 5 vocales y 4 consonantes diferentes, ¿cuántas

palabras de 2 vocales cualesquiera y 2 consonantes diferentes se pueden hacer
de forma que las consonantes no vayan juntas?

Solución
Si no pueden haber dos consonantes seguidas, el patrón que seguirán las palabras
que buscamos es: CV CV o CV V C o V CV C o V CCV o CCV V o V V CC. En
total, tantos como permutaciones en repetición de 2 elementosde forma que el
4
primero se repite 2 veces y el segundo se repite 2 veces, o sea, = 6.
2, 2
De estos casos debemos suprimir aquellos en que hay dos consonantes juntas,
o sea, permutaciones con repetición de 2 elementos de forma
 que el primero se
3
repite 2 veces y el segundo se repite 1 vez. En total = 3.
2, 1
Nos han quedado 3 posibles patrones. En cada uno de ellos las vocales se las
podemos poner de P R(5, 2) = 52 maneras y las consonantes de V (4, 2) = 4 · 3
maneras.
La solución es, pues, 3 · 52 · 4 · 3 = 900.

46. (p2002-pac13 ) En la UOC se reciben solicitudes para matricularse de un

master que se atienden según las calificaciones de las siguientes asignaturas:
matemáticas, informática, inglés y deportes. Cada asignatura tiene una pun-
tuación entera de entre 4 y 10.

Atendiendo a las calificaciones, ¿cuántos expedientes académicos difer-

entes podemos recibir?
Combinatoria: Muestras no ordenadas 25

¿De los expedientes académicos que tienen la máxima nota en deportes,

en cuántos la nota mediana es 7?

Solución
La cantidad de diferentes expedientes académicos es la cantidad de maneras
diferentes de escoger 4 valores enteros entre 4 y 10 de todas las maneras posibles,
tantas como V R(7, 4) = 74 = 2401.
De los expedientes académicos que tienen 10 en deportes, la nota mediana será 7
en aquellos en que la suma de las calificaciones sea 28 y, la cantidad de estos
coincide con la cantidad de soluciones de la ecuación:
x1 + x2 + x3 + 10 = 28
cada xi tiene un valor entero entre 4 y 10.
Restando 4 a cada variable, también podemos considerar las soluciones enteras,
no negativas, de la ecuación:
y1 + y 2 + y3 = 6
Y, de estas, ya sabemos que hay 3+6−1


6 = 28.

47. (t2002-pac11 ) En una finca de caza de Extremadura hay una grupo de

casetas de guarda. Desde cada una de estas casetas se puede ir directamente a
las otras por un camino diferente. Hay en total 36 caminos.
¿Cuántas casetas hay?

Solución
Si suponemos n casetas, la cantidad de caminos que debemos tener coincide con
las 2-muestras no ordenadas de n elementos, que ya sabemos que son 36.
 
n n(n − 1)
O sea: = = 36.
2 2
Haciendo operaciones obtenemos n = 9.

48. (t2002-pac14 ) En una de las carreras que ofrece la UOC, a partir de segun-
do encontramos 9 asignaturas optativas en cada uno de 4 ámbitos diferentes.
No tendremos en cuenta el orden en la elección ni la asignatura concreta que
escogemos sino tan solo el ámbito al cual pertenece.

Si hemos de elegir 7 optativas, ¿de cuántas maneras lo podemos hacer?

Y si en esta elección de las 7 optativas queremos asegurar que haya una
optativa de cada ámbito, ¿de cuántas maneras lo podemos hacer?

Solución
Combinatoria: Muestras no ordenadas 26

   
4+7−1 10
En la primera cuestión podemos calcular CR(4, 7) = = =
7 7
120.
En la segunda pregunta suprimiremos 4 optativas del total (una de cada ámbito)
y, entonces calcularemos las maneras
 de 
elegir3 
asignaturas sin ninguna condi-
4+3−1 6
ción. Esto nos da CR(4, 3) = = = 20.
3 3

49. (t2002-pac15 ) Debemos repartir un presupuesto de 80 millones de euros entre

los cuatro departamentos de una multinacional del sector de las comunicaciones.
Queremos dar a cada departamento una cantidad exacta de millones.

¿De cuántas maneras podemos hacerlo en el supuesto de que queremos

que todos los departamentos obtengan algo?
¿De cuántas maneras podemos hacerlo si queremos que algún departa-
mento no obtenga absolutamente nada?

¿De cuántas maneras podemos hacerlo si queremos que el Departamen-

to de Servicios Profesionales y el Departamento de Desarrollo obtengan
exactamente lo mismo?

Solución

Se trata de contar la cantidad de soluciones enteras positivas de la ecuación:

x + y + z + t = 80
   
80 − 1 79
El resultado es = = 79,079.
4−1 3
Por otro lado, la cantidadde soluciones  dela  ecuación anterior que son
4 + 80 − 1 83
enteras y no negativas es: = = 91,881.
80 3
La respuesta a la segunda cuestión es, pues, la diferencia entre esta segunda
cantidad y la anterior: 91,881 − 79,079 = 12,802.
En este caso se trata de contar la cantidad de soluciones enteras y no
negativas de la misma ecuación x + y + z + t = 80 pero, ahora, suponiendo
que x = y.
Empezamos por suponer que x = y = 0. La ecuación
 se ha  transformado en
2 + 80 − 1 81
z + t = 80 y ya sabemos que tiene = = 81 soluciones.
80 1
Suponemos, ahora, x = y = 1. Ahora la ecuación se ha transformado
en
 1 + 1 + z + t = 80 o bien, z + t = 78 que ya sabemos que tiene
2 + 78 − 1
= 79 soluciones.
78
Combinatoria: Muestras no ordenadas 27

Haciendo
 x = y = 2 encontramos la ecuación z + t = 76 que tiene
2 + 76 − 1
= 77 soluciones.
76
Seguiremos haciendo x = y = 3, x = y = 4, . . ., x = y = 40.
La cantidad total de soluciones de la ecuación será:
81 + 79 + 77 + · · · + 1 = 412 = 1681.

50. (t2002-final5 ) Un estudiante debe responder 7 preguntas de un cuestionario

de 12. ¿De cuántas maneras puede hacer la selección si no hay restricciones? ¿Y
si debe responder a 3 preguntas como mı́nimo de las 5 primeras?

Solución
Cuando no hay restricciones, es 12


7 . Con las restricciones del segundo caso, el
alumno puede escoger de responder 3, 4 o 5 preguntas de las 5 primeras. Hay 53

maneras de responder 3 de las 5 primeras preguntas, hay 5 maneras de responder

4 de las 5 primeras preguntas, y solo hay 1 manera de
responder las

5 primeras
preguntas. Por lo tanto, el número que nos piden es 53 · 74 + 5 · 73 + 72 = 546.

51. (p2003-pac11 ) El consejo de seguridad de Naciones Unidas está formato

por 15 miembros. Cinco son miembros permanentes (Francia, Alemania, Rusia,
China y Estados Unidos) y los otros 10 miembros se van cambiando cada año.
Por aprobar una resolución tiene que haber, como mı́nimo, nuevo votos a favor
y, además, los cinco paı́ses permanentes no deben de votar en contra (de esto se
llama derecho a veto).
¿De cuántas maneras diferentes se puede aprobar una resolución?

Solución
Aplicaremos el principio de adición y el de la multiplicación.
En primer lugar observamos que para aprobar una resolución puede haber pasa-
do que todos los paı́ses permanentes hayan votado a favor. En este caso, nece-
sitamos
  cuatro votos más entre los 10 paı́ses restantes. Lo podremos hacer de
10
maneras.
4
La segunda posibilidad es que de los paı́ses permanentes, cuatro hayan votado
a favor y un de ellos se haya abstenido. Entonces necesitamos
  cinco votos más
10
entre los otros diez paı́ses. Lo podemos hacer de 5 · maneras.
5
Una tercera posibilidad es que, de los paı́ses permanentes, tres hayan votado a
favor y dos de ellos se hayan abstenido. Entonces  necesitamos
   seis votos más
5 10
entre los otros diez paı́ses. Lo podemos hacer de · maneras.
2 6
Etcétera.
Combinatoria: Muestras no ordenadas 28

5   
X 5 10
Finalmente el que nos piden es: = 210 + 1260 + 2100 + 1200 +
y=0
y 4+y
225 + 10 = 5005

52. (p2003-pac13 ) El ayuntamiento de una ciudad quiere distribuir una subven-

ción de 53 millones de euros entre seis instituciones culturales de la ciudad. Si
suponemos que hemos de asignar un número exacto de millones a cada insti-
tución, ¿de cuántas maneras lo podemos hacer? ¿Y si, como mı́nimo, queremos
asignar cinco millones a cada una de las instituciones?

Solución
Este problema es equivalente a calcular el número de soluciones enteras no
negativas de la ecuación x1 + x2 + x3 + x4 + x5 + x6 = 53 que sabemos que es
   
6 + 53 − 1 58
CR(6, 53) = = = 4582116.
53 5

En cambio, si queremos asignar como mı́nimo cinco millones a cada una de las
instituciones, sólo hace falta que nos planteemos de cuántas maneras podemos
distribuir el resto de 53 − 5 · 6 = 23 millones. Del mismo modo que antes,
debemos calcular el número de soluciones enteras no negativas de la ecuación
x1 + x2 + x3 + x4 + x5 + x6 = 23 que es
   
6 + 23 − 1 28
CR(6, 23) = = = 98280.
23 5

53. (p2003-pac14 ) Un cartero llega a un edificio con ocho cartas dirigidas a ocho
destinatarios diferentes, para depositar en los buzones correspondientes. Aquel
dı́a tiene mucha prisa y no mira donde las coloca. ¿De cuántas maneras puede
pasar que:

(a) como mı́nimo Maria reciba la carta dirigida a ella?

(b) sólo Maria reciba la carta dirigida a ella?
(c) como mı́nimo dos de los vecinos reciban las cartas dirigidas a ellos?

Solución

(a) Si como mı́nimo la Maria recibe la carta correctamente, debemos calcular

el número de maneras diferentes de distribuir las siete cartas restantes.
Esto puede pasar de 7! = 5040 maneras diferentes.
(b) Si sólo la Maria recibe la carta dirigida a ella, ninguna de las otras car-
tas han sido repartidas correctamente, por lo tanto debemos calcular el
número de desarreglos de siete elementos, D7 . Esto es:
Combinatoria: Muestras no ordenadas 29

             
7 7 7 7 7 7 7
D7 = 7! − 6! + 5! − 4! + 3! − 2! + 1! − 0! =
1 2 3 4 5 6 7
= 7! − 7! + 2520 − 840 + 210 − 42 + 7 − 1 = 1854.
(c) Los casos en los que como mı́nimo dos de los vecinos han recibido las cartas
dirigidas a ellos se pueden contar a partir del total de permutaciones,
restando aquellos casos en los que ninguna carta o sólo una se ha recibido
correctamente. Ası́ tenemos,
 
8
8! − D8 − D7 = 40320 − 14833 − 8 · 1854 = 10655.
1

54. (t2004-pac12 ) Considera 4 alumnos de primer curso, 5 de segundo, 6 de

tercero 3 de cuarto y 2 de quinto. Son candidatos a recibir 4 premios de la UOC
(al alumno que más utiliza el Foro, al que presenta las mejores Pecs, al más
dialogante con los profesores y al que se matricula de más asignaturas). Ningún
candidato puede recibir más de un premio.

(a) ¿De cuántas maneras se pueden distribuir los premios si no puede haber
más de un premio por curso?
(b) ¿Y si no tienes en cuenta el tipo de premio y cada candidato puede recibir
más de uno?

Solución

(a) Hay un curso que se queda sin premio. Si el primer curso se queda sin
premio, tenemos 4 premios a repartir entre 4 cursos, y esto lo podemos
hacer de 4! maneras diferentes. Ahora, el premio correspondiente a segun-
do curso lo podemos haber entregado a cualquiera de sus 5 candidatos;
el correspondiente a tercero, a cualquiera de sus 6 candidatos; el corre-
spondiente a cuarto, a 3 candidatos; y el quinto, a 2. En total, tenemos
4! × 5 × 6 × 3 × 2 casos. Podemos razonar exactamente igual si se queda sin
premio el segundo curso (4!×4×6×3×2 casos), el tercero (4!×4×5×3×2
casos), el cuarto (4! × 4 × 5 × 6 × 2 casos) y el quinto (4! × 4 × 5 × 6 × 3
casos). La suma de todos estos casos es 25056.
(b) Cada distribución de los 4 premios a los 20 candidatos, con repetición
permitida, es una combinación con repetición. Por lo tanto, la respuesta
es CR(20, 4) = 20+4−1


4 = 8855.

55. (t2004-pac13 ) En un estante hay 6 libros azules, 5 de rojos y 4 de negros. Si

se supone que todos los libros son diferentes, ¿de cuántas maneras los podemos
ordenar si todos los libros de un mismo color han de estar juntos?

Solución
Números multinomiales y funciones generadoras 30

Primero debemos decidir el orden de los colores (B,V,N), y esto lo podemos

hacer de 3! maneras diferentes. Los libros azules se pueden ordenar de 6! maneras
diferentes, los rojos de 5! maneras y los negros de 4! maneras. En total, tenemos
3! 6! 5! 4! = 12441600 maneras de ordenar los libros.

56. (t2004-pac14 )

(a) Debemos repartir un lote de 10 libros diferentes entre 3 estudiantes, y

cada estudiante debe recibir al menos 3. ¿De cuántas maneras lo podemos
hacer?
(b) Un expediente académico contiene las notas de Matemáticas Fı́sica, Quı́mi-
ca e Informática (notas enteras entre 0 y 10). ¿De todos los expedientes
académicos posibles, cuántos tendrán una nota mediana de 2?

Solución

(a) Uno de los estudiantes recibirá 4 libros, y los otras dos, 3. Hay 3 elec-
ciones para el estudiante que recibe 4. Una vez decidido quien recibe 4,
podemos darle los 4 libros de 10


4 maneras diferentes. Al siguiente estudi-
ante le podemos dar sus 3 libros de 63 maneras diferentes, y los 3 libros

que
quedan se los queda el último estudiante. En total, la respuesta es

3 10 6


4 3 = 12600.
(b) Si la nota mediana debe ser 2, la suma de las 4 notas debe ser 8. La solución
es, pues, el número de soluciones enteras

no negativas de la ecuación x +
y + z + t = 8, que es CR(4, 8) = 4+8−1
8 = 165.
Capı́tulo 3

Números multinomiales y
funciones generadoras

57. (t99-pac16 ) Hay 18 estudiantes en una clase. Encuentra el número de

maneras de partir la clase en:

4 grupos de igual medida y un quinto grupo más pequeño.

2 grupos de cinco estudiantes, 1 grupo de cuatro y 2 grupos de dos.
1 grupo de siete estudiantes, 1 grupo de seis y 1 grupo de cinco.

Solución
18!
= 402026625
4! (4! )4 1! 2!
18!
= 1157836680
2! (5! )2 1! 4! 2! (2! )2
18!
= 14702688
7! 6! 5!

58. (p2000-pac15 ) Se asignan doce estudiantes para trabajar en 5 proyectos

diferentes. Cada uno de los estudiantes debe trabajar solo en un proyecto, y
para cada proyecto hay de haber entre 2 y 4 estudiantes. ¿De cuántas formas se
puede hacer esta asignación?

Solución
Suponemos que ai es el número de estudiantes asignados al proyecto número i,
de esta forma:

P1 P2 P3 P4 P5
a1 a2 a3 a4 a5

31
Números multinomiales y funciones generadoras 32

Las condiciones del problema imponen que la suma de los ai sea igual a 12, y
cada ai debe encontrarse entre 2 y 4. Es decir,

5
X
ai = 12 i 2 ≤ ay ≤ 4 ∀i, i = 1, · · · , 5
i=1

Si todos los ai valen 2, la suma es 10 y, por lo tanto, faltan 2 para llegar al 12

exigido. Las únicas posibilidades para estos valores son: 22224 y 22233.

(a) En el primer caso, el 22224 se puede conseguir, fácilmente, de 5 man-

5


eras diferentes; si se quiere de 1,4 = 5 maneras diferentes. Además, las
posibilidades de poner 12 objetos (alumnos) en estas 5 cajas (proyectos)
12


guardando esta distribución son 2,2,2,2,4 .
5 5!


(b) En el segundo caso, el 22233 se puede conseguir de 2,3 = 2!3! = 10 formas
diferentes. Además, las posibilidades de poner 12 objetos (alumnos) en
12


estas 5 cajas (proyectos) guardando esta distribución son 2,2,2,3,3 .

En definitiva, el número de asignaciones de alumnos posibles a los 5 proyectos

son:
   
12 12
5 + 10 = 22869000
2, 2, 2, 2, 4 2, 2, 2, 3, 3

59. (p2001-pac25 ) Una caravana publicitaria consta de 6 coches y 6 furgone-

tas, siendo todos ellos del mismo color (o sea, dos coches son indistinguibles
y dos furgonetas también, pero sabemos distinguir coches de furgonetas) ¿De
cuántas maneras diferentes se puede organizar la fila de la caravana con tal que
la furgoneta de Oriol y la de Josep no circulen juntas?

Solución
Organizar una caravana equivale a escribir 12 letras utilizando seis veces la c
y seis veces la f . La condición que dos f concretas no estén juntas no debe
tener en cuenta puesto que las f son indistinguibles y, por lo tanto, en cualquier
configuración aceptable del problema siempre podemos cambiar los conductores
de forma que se cumpla la condición.
Las diferentes
  maneras de escribir una tira de 12 letras utilizando seis c y seis
12 12!
f son = = 924.
6, 6 6!6!

60. (p2001-final1 ) Cuál es el número total de palabras diferentes que se pueden

formar con todas las letras de la palabra TALLAHASSEE?
¿Cuántas de estas no tienen dos A juntas?

Solución
Números multinomiales y funciones generadoras 33

Hay 3, 2, 2,112, 1, 1 maneras de construir palabras diferentes con las letras de la

palabra TALLAHASSEE:
 
11 11!
= = 831600
3, 2, 2, 2, 1, 1 3!2!2!2!1!1!

Si no tenemos en cuenta las A, tendremos

 
8 8!
= = 5040
2, 2, 2, 1, 1 2!2!2!1!1!
maneras de formar palabras de 8 letras sin las A. Para que las A no estén jun-
tas deben tener una de las otras letras intercaladas. Ası́, las A pueden estar
en cualquiera

de las 9 posiciones determinadas por las otras letras. En total,
tenemos 93 = 84 formas de seleccionar tres posiciones.
Por la regla del producto, tendremos 5040 × 84 = 423360 maneras de formar
palabras sin dos A juntas.

61. (t2000-final2 )

(a) ¿En qué casos (o sea, para qué valores
de n > 1)
podemos asegurar que la
suma de los números combinatorios n2 + n−1 2 es un cuadrado?
(b) ¿Cuál es el coeficiente numérico de x21 x2 x24 x5 en el desarrollo de (x1 + x2 +
x3 + x4 + x5 )6 ?

Solución

n n(n − 1) (n − 1)(n − 2)
+ n−1 = (n − 1)2 . O sea, la respuesta



(a) 2 2 = +
2 2
al problema es: siempre.
 
6 6!
(b) = = 180.
2, 1, 2, 1 2!2!

62. (t2000-pac13 ) ¿De cuántas maneras se pueden ordenar en fila todas las
piezas blancas del ajedrez, si no son distinguibles entre sı́ las del mismo rango?
(Por ejemplo los ocho peones).

Solución
El tablero de ajedrez contiene 8 peones, 2 torres, 2 caballos, 2 alfiles, 1 reina y
1 rey. En total 16 piezas.
Si las piezas fueran todas distinguibles, entonces la solución serı́a simplemente
16!. Pero, como que son indistinguibles hace falta dividir por las permutaciones
de cada uno de los subconjuntos.
16


8,2,2,2,1,1
Números multinomiales y funciones generadoras 34

63. (p2002-pac21 ) Queremos construir números de 10 cifras usando las cifras

1, 2, 3, 4, 5, 6, 7, 8, 9. ¿Cuántos números cumplen todas estas condiciones: tienen,
exactamente, la cifra 5 tres veces, la cifra 7, dos veces y la cifra 1, una vez?

Solución
Primero escogemos las 6 posiciones en  las que
 colocar las cifras 5,5,5,7,7,1.
10
Esto lo podemos hacer de C(10, 6) = maneras. En estas posiciones,
6 
6, 6!
podemos colocar las cifras anteriores de = maneras difer-
3, 2, 1 3!, 2!, 1!
entes. Para las cuatro posiciones restantes hay P R(6, 4) = 64 4-muestras
ordenadas
  utilizando las 6 cifras 2,3,4,6,8,9. Por lo tanto, hay exactamente
10, 6!
, 64 = 12600 · 64 = 16329600 números que reúnen las condi-
6 3!, 2!, 1!
ciones del enunciado.

64. (t2002-pac21 ) ¿De cuántas maneras podemos ordenar, en una estanterı́a,

14 CD’s diferentes de música? ¿Y si hay 3 copias iguales de un CD de Mozart,
4 copias de un de Bach y 7 copias de un de Vivaldi?

Solución
Si todos los CD’s son diferentes, la solución viene dada por el número de 14-
muestras ordenadas sin repetición (permutaciones sin repetición), o sea, hay
P (14) = 14! = 87178291200 maneras diferentes de ordenarlos. En cambio, si
algunos de los CD’s son iguales entre ellos, las maneras de ordenarlos venden
14!
dadas por el número de permutaciones con repetición P R(3, 4, 7)14 = =
3!4!7!
120120.

65. (t2002-pac41 ) Efectuamos el siguiente experimento: lanzamos simultánea-

mente 7 dados, y anotamos los puntos mostrados por cada dado después del
lanzamiento.

(a) Si todos los dados son idénticos, calcula el número de posibles resultados
del experimento. ¿En cuántos de estos resultados el producto de todos los
puntos es un número impar?
(b) Si cada dado está pintado de un color diferente, calcula el número de
posibles resultados del experimento. ¿En cuántos de estos resultados el
producto de todos los puntos es 45? ¿En cuántos la suma de todos los
puntos es 17?

Solución

(a) CR(6, 7) = 6+7−1

6−1 = 792. Si el producto de todos los puntos debe ser
impar, cada una de las 7 puntuaciones debe ser un número impar. Por lo
Números multinomiales y funciones generadoras 35

tanto, de cada uno de los 7 dados
solo admitimos 3 resultados: 1, 3 o 5.

Tenemos, pues, CR(3, 7) = 3+7−1
3−1 = 36.

(b) V R(6, 7) = 67 . Como que 45 = 3 · 3 · 5, la única posibilidad para que el

producto de los 7 dados dé 45 es obtener dos treses, un cinco y cuatro
unos. Como los 7 dados son distinguibles, hace falta contar cuántas mues-
tras ordenadas se pueden formar con los elementos {1, 1, 1, 1, 3, 3, 5}. Es
7!
decir, P R7 (4, 2, 1) = 4!2!1! = 105. Finalmente, para contar cuántos resul-
tados dan una suma de 17, debemos contar el número de soluciones de
la ecuación x1 + x2 + . . . + x7 = 17 con 1 ≤ xy ≤ 6. Es decir, debemos
encontrar el término de x17 de la función generadora (x + x2 + . . . + x6 )7 .
Como que (x + x2 + . . . + x6 )7 = x7 (1 + x + . . . + x5 )7 , debemos encontrar
el término de x10 de (1 + x + . . . + x5 )7 . Tenemos
7
1 − x6

5 7
(1 + x + . . . + x ) = .
1−x

Decimos α(x) = (1 − x)−7 y β(x) = (1 − x6 )7 . Los únicos coeficientes de

β(x) diferentes de cero son los de grado 0, 6, 12, . . . Solo nos interesan los
de grado 0 y 6, β0 y β6 . Por lo tanto, de α(x) nos interesarán los de grado
10 y 4, α10 y α4 . Tenemos
   
7 + 10 − 1 7+4−1
α10 = = 8008, α4 = = 210,
10 4
 
7
β0 = 1, β6 = − = −7.
1
Obtenemos finalmente α10 β0 + α4 β6 = 6538.

66. (t2002-final1 ) Permutando de todas las maneras posibles las cifras 1111223
formamos números que ordenamos de menor a mayor. ¿Cuántos números for-
mamos? ¿Qué número ocupa la posición 90 en esta ordenación?

Solución
7!
Se pueden formar 4!2! = 105 números. Para estimar que encontraremos en la
posición 90, calculamos cuántos de estos números tienen el 3 en la primera
6!
posición: es el número de permutaciones de las cifras 111122, o sea 4!2! = 15.
Por lo tanto, el número en posición 90 es exactamente el más grande de los que
no empiezan por 3, o sea 2321111.

67. (p2001-pac22 ) Se sacan los 10, 11 y 12 de una baraja de cartas. Las cartas
que quedan todas valen lo que marca en la carta excepto el as (o sea el 1) que
vale 10 puntos.
Se coge una carta de la baraja, se mira cuántos puntos vale y se vuelve a la
baraja. Esto se hace cuatro veces y tendremos en cuenta el orden en el que
vamos extrayendo las cartas.
Números multinomiales y funciones generadoras 36

¿De cuántas maneras podemos sumar 32 puntos?

Solución
Podemos plantear el problema a través de la función generadora:

f (x) = (x2 + x3 + x4 + x5 + x6 + x7 + x8 + x9 + x10 )4 = x8 (1 + x + x2 + · · · + x8 )4

El resultado que nos interesa es el cálculo del coeficiente de grado 32 de f (x)

o, lo que es el mismo, el coeficiente de grado 24 del polinomio g(x) = (1 + x +
x2 + · · · + x8 )4 .
4
1 − x9

g(x) = (1 + x + x2 + · · · + x8 )4 =
1−x
Debemos calcular, pues, el coeficiente de x24 a (1 − x9 )4 (1 − x)−4 .
| {z } | {z }
α β
O
 sea,
 α0 β24 +α
 9 β15+α18 β6 = CR(4, 24)−C(4, 1)CR(4, 15)+C(4, 2)CR(4, 6) =
27 18 9
−4 +6 = 2925 − 4 · 816 + 6 · 84 = 165
24 15 6

68. (p2001-pac42 ) Encuentra el número de soluciones de la ecuación

a + b + c + d + e = 1000

siendo a, b, c, d, e enteros no negativos y, además, a, c y e son pares y b y d son

impares.

Solución
Podamos construir la función generadora asociada al problema:
1 x2
g(x) = (1 + x2 + x4 + x6 + . . .)3 (x + x3 + x5 + . . .)2 = =
(1 − x2 )3 (1 − x2 )2
x2
(1 − x2 )5
y calcular el coeficiente de grado 1000.
1
Lo que es lo mismo, debemos calcular el coeficiente de grado 998 de
  (1 − x2 )5

1 5 + 499 − 1 503
o el coeficiente de grado 499 de 5
que vale = =
(1 − y) 499 499
5271062750

69. (p2001-final2 ) En la asignatura de Matemática Discreta de la U OC se

ha decidido que el examen de cada alumno serı́a corregido por su consultor y,
también, por otros tres consultores. Con esto cada alumno dispondrá de cuatro
notas valoradas de 0 a 10 sólo con valores naturales.
Por aprobar la asignatura se debe sacar un mı́nimo de 20 puntos, pero los
alumnos que tienen 19 puntos pasan a un proceso de revisión de examen.
Números multinomiales y funciones generadoras 37

Encuentra de cuántas maneras puede ser puntuado un alumno por los cuatro
consultores para pasar al proceso de revisión de examen.

Solución
4
1 − x11

10 4
La función generadora del problema es g(x) = (1+x+. . .+x ) = =
1−x
(1 − x11 )4 (1 − x)−4 y debemos calcular el coeficiente de grado 19.
| {z } | {z }
α β
 
22
Debemos calcular, pues, α0 β19 +α11 β8 = CR(4, 19)−C(4, 1)CR(4, 8) = −
  19
11
4 = 1540 − 660 = 880
8

70. (p2001-final6 ) Tiramos 100 dados y queremos saber de cuántas maneras la

suma de sus puntos puede dar 112.

Solución
La función generadora del problema es g(x) = (x + x2 + x3 + x4 + x5 + x6 )100
y nos interesa obtener el coeficiente de grado 112.
100
1 − x6

g(x) = x100 (1 + x + x2 + x3 + x4 + x5 )100 = x100 , o sea que nos
1−x
interesa encontrar el coeficiente de grado 12 a (1 − x6 )100 (1 − x)−100
| {z } | {z }
α β
Debemos calcular: α0 β
12 + α6 β6 + α12 β  12) − 100CR(100, 6) +
0 = CR(100,
111 105 100
C(100, 2)CR(100, 0) = − 100 +
12 6 2

71. (p2001-final9 ) Antes de la implantación del euro, Joan, Josep y Pere deciden
gastarse todas las monedas de peseta que habı́an ido guardando. Comprarán un
gran pastel de 2000 pesetas y se preguntan de cuántas maneras diferentes podrán
pagarlo con tal que nadie ponga más de 1000 pesetas.

Solución
La solución al problema consiste en encontrar la cantidad de soluciones enteras
no-negativas de la ecuación: a + b + c = 2000, con tal que las tres variables
a, b, c ≤ 1000.
Debemos calcular, pues, el coeficiente de grado 2000 de la función generadora
3
1 − x1001

2 3
g(x) = (1 + x + x + x + . . . + x1000 3
) = = (1 − x1001 )3 (1 − x)−3 .
1−x | {z } | {z }
α β
El coeficiente pedido es, pues, α0 β2000 +α1001 β999 = CR(3, 2000)−C(3, 1)CR(3, 999) =
Números multinomiales y funciones generadoras 38

   
2002 1001
−3 = 501501
2000 999

72. (t2000-p4 ) Un grupo de amigos amantes del vino mantiene una pequeña
bodega, dividida en tres secciones: una de vino tinto, otra de vino blanco y,
finalmente, una de vino rosado. Cada sección de esta bodega es una matriz
rectangular de celdas de forma que en cada celda se puede poner una única
botella. La sección de vinos tintos está formato por una matriz de 15 celdas
horizontales por 11 celdas verticales, como esta:

La sección de vino blanco está formada por una matriz 8 por 7, y la de vino
rosado está formada por una matriz 6 por 5.

(a) Supón que este grupo de amigos ha comprado 6 botellas de cada marca
de vino que quiere tener, para poderlos catar en diferentes momentos de
su evolución, hasta que llena al máximo todas las secciones. ¿De cuántas
formas diferentes se puede poner todas las botellas?
(b) Supón que este grupo de amigos compra botellas de una única marca de
vino tinto, botellas de una única marca de vino de blanco y botellas de
una única marca de vino rosado. En total compra 100 botellas de vino:
como mı́nimo, 25 son de vino tinto, no más de 10 son de vino rosado,
y entre 10 y 40 son de vino blanco. ¿De cuántas formas diferentes puede
hacer esta adquisición?
(c) Supón, ahora, que este grupo de amigos quisiera comprar botellas de 5
marcas de vino fijadas para cada sección, hasta llenar al máximo todas
tres secciones. ¿De cuántas formas diferentes puede hacerse la adquisición
de las botellas de estas 5 marcas de vino, si se deben tener 6 botellas como
mı́nimo de cada marca?

Solución

(a) caben 165 botellas de vino tinto, 56 botellas de vino blanco y 30 botellas
de vino rosado. Si se compran 6 botellas de cada marca, en la sección de
vino tinto sobrarán 3 celdas, en la de vino blanco, 1 y en la de vino rosado
cabeza (ahora bien, es indiferente considerar que se llenan las celdas vacı́as
con un vino de una otra marca)
Números multinomiales y funciones generadoras 39

Para encontrar el número de posibilidades de poner estas botellas hace

falta calcular este producto:
165 56 30 165! 56! 30!




6,6,6..,6,3 · 6,6,6..,6,1 6,6,6,6,6 = (6!)27 3! (6!)9 2! (6!)5

(b) Hace falta calcular el coeficiente g100 de esta función generadora:

g(x) = (x25 + x26 + ... + x100 )(x + x2 + ... + x10 )(x10 + ... + x40 ) =
x36 (1 + ... + x75 )(1 + ... + x9 )(1 + ... + x30 ) =
76
1−x10 1−x31 −3
x36 1−x 36 76 10
1−x 1−x 1−x = x (1 − x )(1 − x )(1 − x )(1 − x)
31

pondremos, sólo, los términos que son importantes, para calcular g100
g(x) = (x36 − x46 − x67 + x77 + ...)(1 − x)−3 =
P∞
(x36 − x46 − x67 + x77 + ...) r=0 r+2

r
r x
Por lo tanto, el coeficiente que buscamos es:
64+2
− 54+2 − 33+2 + 23+2





64 54 33 23 = 310 formas diferentes.
(c) En el caso del vino tinto, la función generadora es:
 5
1−x160
g(x) = (x6 + x7 + ... + x165 )5 = x30 (1 + x + .... + x159 ) = x30 1−x =
P∞
= x30 (1 − x160 )5 .(1 − x)−5 = x30 (1 − x160 )5 . r=0 r+4

r
r x
El coeficiente 165 de este polinomio es
g165 = 135+4


135 = 1. 489 × 107
Para calcular el número las formas de adquirir vino blanco y vino rosado, la
función generadora es semejante, pero debemos calcular otros coeficientes,
respectivamente:
g56 = 26+4


26 = 2. 741 × 104
g30 = 40 = 1

El último coeficiente es evidente, porque si se deben escoger como mı́nimo

6 botellas de cada una de las 5 marcas de vino rosado, hasta obtener 30
botellas, sólo se puede hacer de una manera.
En definitiva, las formas de adquirir todas las botellas son:
135+4

26+4

135 · 26 ' 4. 081 × 1011

73. (t2000-final3 ) Nos han regalado cajas de 7 tipos diferentes de velas y en

cada caja hay 20 velas iguales.
Para montar el pastel de aniversario utilizaremos 300 velas, pero usaremos ca-
jas enteras y nunca una parte de las velas de la caja y, de cada tipo de vela,
usaremos, como mı́nimo, una caja y, como máximo, cinco cajas. ¿De cuántas
maneras lo podemos hacer?

Solución
Podemos modelar el problema como el número de soluciones enteras de la
ecuación: e1 + e2 + e3 + e4 + e5 + e6 + e7 = 15, con 1 ≤ e1 ≤ 5.
Números multinomiales y funciones generadoras 40

Lo que nos interesa es el coeficiente de x15 a la función generadora ordinaria

g(x) = (x + x2 + x3 + x4 + x5 )7 = x7 (1 − x5 )7 (1 − x)−7 . Haciendo los cálculos
adecuados el resultado es 2415.

74. (t2000-final9 ) Encuentra el coeficiente de x9 a (x2 + x3 + x4 + x5 )5 y,

también, el coeficiente de x20 .

Solución
(x2 + x3 + x4 + x5 )5 = x10 · (1 + x + x2 + x3 )5 y, por lo tanto, el coeficiente de
grado menor es x10 . En particular, el coeficiente de x9 es cero.
El coeficiente de x20 es el mismo que el de x10 a (1+x+x2 +x3 )5 = (1 − x4 )5 (1 − x)−5 .
| {z } | {z }
α β
10
El coeficiente de x en αβ se reduce a considerar los productos α0 β10 , α4 β6 y
α8 β2 .
Finalmente, el coeficiente pedido es: 50 · 14 5



10
5

6

10 − 1 · 6 + 2 · 2 = 101

75. (t2000-final15 ) Utiliza las funciones generadoras para encontrar el número

de maneras de seleccionar 10 pelotas de una caja con pelotas rojas, blancas y
azules, pero cogiendo un número par de azules,

Solución
Estamos buscando el número de soluciones enteras, no-negativas, de la ecuación
v + b + bl = 10, donde bl es par.
Esto es, el coeficiente de x10 de la función generadora (1 + x + x2 . . .)2 (1 + x2 +
x4 + . . .) = (1 − x)−2 (1 − x2 )−1 . Haciendo los cálculos adecuados da 36.

76. (t2001-pac42 ) ¿De cuántas maneras se pueden repartir doce libros iguales y
dieciséis agendas iguales entre cuatro personas de forma que la primera reciba
al menos un libro y tres agendas y cada una de las otras reciba al menos dos
libros pero como mucho cinco agendas?

Solución
Queremos repartir 12 libros entre 4 personas de forma que la primera reciba al
menos uno y cada una de las otras reciba al menos dos. Esto vendrá dado por
el coeficiente de x12 en la función generadora:

f (x) = (x + x2 + x3 + · · · + x6 )(x2 + x3 + ······ + x7 )3

se trata pues de calcular el coeficiente de x5 en g(x) = (1 + x + ······ + x5 )4 .

Sabemos que g(x) = (1 − x6 )4 (1 − x)−4 , por lo tanto g5 = CR(4, 5) = 56.
El número de maneras diferentes de repartir 16 agendas entre las cuatro per-
Números multinomiales y funciones generadoras 41

sonas, con las restricciones del enunciado, viene dado por el coeficiente de x16
de la función generadora

f (x) = (x3 + x4 + · · · + x16 )(1 + x + · · · + x5 )3

o, equivalentemente, el coeficiente de x13 de

g(x) = (1 + x + · · · + x13 )(1 + x + · · · + x5 )3

Podemos escribir,

(1 − x)14 (1 − x6 )3
g(x) =
1 − x (1 − x)3
por lo tanto, g13 = C(3, 0)CR(4, 13) − C(3, 1)CR(4, 7) + C(3, 2)CR(4, 1) = 212.
El número total de maneras de repartir los libros y las agendas es 56 · 212 =
11872.

77. (t2001-final5 ) Se distribuyen k bolas idénticas dentro de n cajas numeradas.

¿De cuántas maneras se puede hacer la distribución si:

(a) en cada caja debemos colocar al menos una bola y, como mucho, dos?
(b) la única restricción es que en cada caja haya, como mucho, dos bolas? En
este segundo apartado haz el problema considerando n = 8 y k = 5.

Solución
Enfocaremos el problema a través de la técnica de las funciones generadoras. El
exponente de la variable x querrá decir las bolas que colocamos.

(a) En el primer caso construimos la función generadora g(x) = (x + x2 )n y

la respuesta viene dada por el coeficiente de xk .
n


g(x) = (x + x2 )n = xn (1 + x)n . El coeficiente de xk es k−n .

(b) En el segundo caso la función generadora será g(x) = (1 + x + x2 )n .

n
1 − x3

2 n
g(x) = (1 + x + x ) = = (1 − x3 )n (1 − x)−n
1−x | {z } | {z }
α(x) β(x)

nos9
piden viene dado por α0 β5 + α3 β2 = CR(8, 5) −

El coeficiente que
8CR(8, 2) = 12 5 − 8 2 = 504

78. (t2001-final10 ) Determina el coeficiente de x19 en la expresión:

(x2 + x3 + · · · + x9 )3
Números multinomiales y funciones generadoras 42

Solución
3
1 − x8

6 2 7 3 6
g(x) = x (1 + x + x + . . . + x ) = x o sea que nos interesa el
1−x
8 3 −3
coeficiente de x13 a (1 − x ) (1 − x) .
| {z } | {z }
α β
Debemos calcular    
15 7
α0 β13 + α8 β5 = CR(3, 13) − C(3, 1)CR(3, 5) = −3 = 42.
13 5

79. (p2002-pac22 ) Plantea una función generadora en la que el coeficiente de x30

sea el número de soluciones enteras positivas de la ecuación 2x1 + 5x2 + x3 = 30
siendo 0 < x1 ≤ x2 ≤ x3 .

Solución
Como que x1 ≤ x2 ≤ x3 , podemos escribir x1 ≤ x1 + a ≤ x1 + a + b, a, b ≥ 0,
tomando x2 = x1 + a y x3 = x2 + b = x1 + a + b. Sustituyendo x2 y x3 en la
ecuación inicial, ésta es equivalente a 2x1 + 5(x1 + a) + x1 + a + b = 30 que
podemos escribir como 8x1 + 6a + b = 30, x1 > 0 y a, b ≥ 0. El coeficiente del
término x30 de la función generadora siguiente nos da el número de soluciones
enteras positivas de la ecuación planteada.

f (x) = (x8 + x16 + x24 )(1 + x6 + x12 + x18 + x24 )(1 + x + · · · + x22 )

80. (p2002-pac23 ) Calcula el coeficiente de x20 de la función generadora

g(x) = (x3 + x4 + x5 + · · · + x12 )3 (1 + x + x2 + x3 ).

Solución
Podemos escribir g(x) = (x3 )3 (1 + x + · · · + x9 )3 (1 + x + x2 + x3 ), por lo tanto el
coeficiente de x20 es igual al coeficiente de x11 de la función generadora (1 + x +
 10
3
1−x4
· · · + x9 )3 (1 + x + x2 + x3 ). Esta última se puede escribir como 1−x 1−x 1−x =
1
(1 − x10 )3 (1 − x4 ) . El coeficiente de x11 de la función generadora es
| {z } | {z } (1 − x)4
α β | {z }
γ
pues α0 β0 γ11 + α0 β4 γ7 + α10 β0 γ1 = CR(4, 11) − CR(4, 7) − C(3, 1)CR(4, 1) =
364 − 120 − 12 = 232.

81. (p2002-pac42 ) Un repartidor de propaganda tiene 20 revistas idénticas para

repartir en el último edificio de la zona que consta de 9 pisos (3 por planta).
¿De cuántas maneras puede repartir todas las revistas que le quedan en los 9
buzones si en cada uno de los 3 pisos de la primera planta coloca como mı́nimo
Números multinomiales y funciones generadoras 43

4 y como máximo 8, en cada uno de la segunda planta coloca como mı́nimo 1

y finalmente en la última planta coloca como máximo 3 en cada uno de los tres
buzones?

Solución
La solución al problema planteado consiste en encontrar el coeficiente del térmi-
no x20 de la función generadora:

g(x) = (x4 + x5 + · · · + x8 )3 (x + x2 + · · · )3 (1 + x + x2 + x3 )3

Podemos escribir g(x) = x15 (1 + x + · · · + x4 )3 (1 + x + · · · )3 (1 + x + x2 + x3 )3 ,

por lo tanto el coeficiente del término x20 de g(x) es el mismo que el coeficiente
del término x5 a la función generadora

f (x) = (1 + x + x2 + x3 + x4 )3 (1 + x + x2 + · · · )3 (1 + x + x2 + x3 )3
5
3
3 1−x4
3  1 9
Como f (x) = 1−x
1−x
1
· 1−x · 1−x = (1 − x5 )3 (1 − x4 )3 .
| {z } | {z } 1 − x
α β
| {z }
γ
Ası́, debemos calcular α0 β0 γ5 + α0 β4 γ1 + α5 β0 γ0 =
C(3, 0)C(3, 0)CR(9, 5) −
C(3, 0)C(3, 1)CR(9, 1)−C(3, 1)C(3, 0)CR(9, 0) = 13 5 −3·9−3 = 1287−27−3 =
1257.

82. (p2002-final10 ) Una fábrica dispone de 3 lı́neas robotizadas para montar or-
denadores. Una lı́nea monta placas base, la otra monitores y la tercera la unidad
central. Si dispone de 12 robots industriales idénticos, ¿de cuántas maneras los
podemos asignar a las diferentes lı́neas de forma que cada lı́nea tenga un mı́nimo
de 3 robots pero no más de 9? Utiliza el método de las funciones generadoras
por resolver el problema.

Solución
La solución al problema planteado consiste en encontrar el coeficiente del térmi-
no x12 de la función generadora:

g(x) = (x3 + x4 + · · · + x9 )3

Podemos escribir g(x) = x9 (1 + x + · · · + x6 )3 , por lo tanto el coeficiente del

término x12 de g(x) es el mismo que el coeficiente del término x3 a la función
generadora

f (x) = (1 + x + · · · + x6 )3
7
3
 1 3
7 3
Como f (x) = 1−x
1−x = (1 − x ) .
| {z } 1 − x
α
| {z }
β
5


debemos calcular α0 β3 = 1 · 3 = 10.
Números multinomiales y funciones generadoras 44

83. (t2002-pac22 ) Plantea una función generadora y determina cuál es el término

cuyo coeficiente corresponde al número de maneras de distribuir 100 objetos
iguales en 4 cajas.

Debes tener en cuenta que las cajas son distinguibles y cada una debe
contener un objeto como mı́nimo.
Debes tener en cuenta que las cajas son indistinguibles y cada una debe
contener un objeto como mı́nimo.

Solución
En el primer caso el número de distribuciones posibles corresponde al número
de soluciones enteras y positivas de la ecuación x1 + x2 + x3 + x4 = 100.
El coeficiente del término x100 de la función generadora siguiente nos da el
número de distribuciones que pide el enunciado:

f (x) = (x + x2 + x3 + x4 + · · · )4 .

En el segundo caso, como que los objetos y las cajas son indistinguibles, el
número de distribuciones posibles corresponde al número de soluciones enteras
de la ecuación x1 + x2 + x3 + x4 = 100 tales que x1 ≤ x2 ≤ x3 ≤ x4 . Si, como
mı́nimo, hay un objeto a cada caja, entonces 0 < x1 ≤ x2 ≤ x3 ≤ x4 .
Tomamos x2 = x1 + a, x3 = x2 + b = x1 + a + b y finalmente x4 = x3 + c =
x1 + a + b + c, con x1 > 0 y a, b, c ≥ 0. Sustituyendo x2 , x3 y x4 en la ecuación
anterior, esta es equivalente a x1 (x1 + a) + (x1 + a + b) + (x1 + a + b + c) = 100
que podemos escribir como 4x1 + 3a + 2b + c = 100, x1 > 0 y a, b, c ≥ 0. El
coeficiente del término x100 de la función generadora siguiente nos da el número
de distribuciones que pide el enunciado:

f (x) = (x4 +x8 +x12 +· · · )(1+x3 +x6 +x9 +· · · )(1+x2 +x4 +x6 +· · · )(1+x+x2 +· · · )

84. (t2002-pac23 ) En la fábrica de coches de una conocida marca se acaban

de fabricar 34 coches idénticos. ¿De cuántas maneras podemos distribuir todos
estos coches en los 3 almacenes que dispone la fábrica si la capacidad máxima
tanto del primero como del segundo es 25 y del tercero es 20?

Solución
Podemos plantear la solución como el coeficiente de término x34 de la función
generadora (1 + x + x2 + · · · + x25 )2 (1 + x + x2 + x3 + · · · + x20 ). Ésta se puede
 26
2 1
1−x21
escribir como 1−x
1−x 1−x = | (1 − x26 )2 (1 − x21 ) . El coeficiente de
{z } | {z } (1 − x)3
α β | {z }
γ
x34 de la función generadora es pues α0 β0 γ34 +α0 β21 γ13 +α26 β0 γ8 = CR(3, 34)−
CR(3, 13) − C(2, 1)CR(3, 8) = 630 − 105 − 2 · 45 = 435.
Números multinomiales y funciones generadoras 45

85. (t2002-final6 ) Utilizando funciones generadoras determina el número de

soluciones positivas y enteras de la ecuación x1 + x2 + x3 + x4 + x5 + x6 = 20,
tales que x1 ≤ 5.

Solución
El coeficiente del término x20 de la función generadora g(x) = (x+x2 +x3 +x4 +
x5 )(x+x2 +x3 +· · · )5 nos da el número de soluciones positivas y enteras tales que
x1 ≤ 5. Podemos escribir g(x) = x6 (1+x+x2 +x3 +x4 )(1+x+x2 +· · · )5 , por lo
tanto el coeficiente de x20 es igual al coeficiente de x14 de la función generadora
(1 + x + x2 + x3 + x4 )(1 + x + x2 + · · · )5 . Esta última se puede escribir como
 5 1
1−x5
1−x 1−x
1
= (1 − x5 ) . El coeficiente de x14 de la función generadora
| {z } (1 − x)6
α | {z }
β
es pues α0 β14 + α5 β9 = CR(6, 14) − CR(6, 9) = 11628 − 2002 = 9626.

86. (p2003-pac22 ) Los sondeos electorales del pueblo de Pinos del Vallés dan
las siguientes bandas de regidores para cada partido:

Partido Regidores (mı́n-màx)

P 3-5
C 4-6
S 3-5
E 2-4

Si suponemos que los sondeos se cumplen y que en total tenemos 17 regidores,

¿de cuántas maneras diferentes puede organizarse el consistorio?

Solución
La solución consiste en calcular el coeficiente de x17 de la función generadora:

f (x) = (x3 + x4 + x5 )(x4 + x5 + x6 )(x3 + x4 + x5 )(x2 + x3 + x4 ) = x12 (1 + x + x2 )4

Tras simplificar, la solución también la podemos ver como el coeficiente de x5

del polinomio

(1 − x3 )4
(1 + x + x2 )4 = = (1 − x3 )4 (1 − x)−4 .
(1 − x)4 | {z } | {z }
α(x) β(x)

 
4
El coeficiente que nos piden viene dado por α0 β5 + α3 β2 = CR(4, 5) −
      0
4 8 5
CR(4, 6) = −9 = 16
1 5 2

87. (p2003-pac24 ) Encuentra la manera de asignar:

Números multinomiales y funciones generadoras 46

(a) 9 estudiantes en 11 habitaciones de una residencia (numeradas consecuti-

vamente de la 100 a la 110 ) de forma que en cada habitación haya, como
máximo, un estudiante.
(b) 9 teléfonos de colores (dos de rojos, tres de blancos y cuatro de verdes) en
estas 11 habitaciones de forma que cada habitación tenga, como máximo,
un teléfono.
(c) los 9 estudiantes y los 9 teléfonos en las 11 habitaciones de forma que cada
estudiante tenga teléfono (no puede haber más de un estudiante ni más
de un teléfono por habitación).

Solución
11!
(a) V (01, 9) = .
2!
71!
(b) P R(11; 2, 3, 4, 2) = .
6!3!4!2!
(c) V (11, 9) · P R((9; 2, 3, 4).

88. (p2003-pac41 ) Plantea una función generadora y di cuál es el coeficiente que

nos interesa calcular para resolver el problema siguiente.
En un sorteo de pisos de promoción pública destinados a jóvenes que viven
en Montepijo, se valora el nivel de ingresos, la antigüedad como residente del
pueblo y el trabajo actual del candidato. Los puntos que se conceden para cada
apartado son enteros, positivos y el primer apartado siempre se puntúa menos
(o igual) que el segundo, que a la vez se puntúa menos (o igual) que el tercero.
Finalmente, se concede un piso a un joven si haciendo la suma de dos veces los
puntos del primer apartado, más cinco veces el del segundo más los del tercer
apartado da exactamente 27.
¿A cuántas tipologı́as diferentes se concede el piso?
Nota: Una tipologı́a es igual que otra si y sólo si coinciden las puntuaciones de los tres aparta-
dos.

Solución
Nuestro problema es plantear una función generadora g(x), en la que el coefi-
ciente a27 de x27 sea el número de soluciones enteras, positivas, de la ecuación
2a + 5b + c = 27, tal que 0 < a ≤ b ≤ c.
Para asegurar las restricciones de las variables a, b, c, consideramos a = α, b =
β + a, c = γ + b = γ + β + a, siendo α > 0 y β, γ ≥ 0. Entonces el problema
se transforma en calcular el número de soluciones enteras de la ecuación 2α +
5(β + α) + (γ + β + α) = 27 o, simplificando 8α + 6β + γ = 27 que, a la vez es el
mismo que x + y + z = 27 con la condición x = 8α > 0, y = 6β ≥ 0, z = γ ≥ 0.
A la hora de construir los polinomios asociados a cada x, y, z fijaos que los
valores que puede tener x son enteros, positivos y, además, múltiplos de ocho:
Ecuaciones recurrentes y complejidad computacional 47

ası́, su función generadora será (x8 +x16 +x24 ); los valores que puede tener y son
enteros, no negativos y, además, múltiplos de seis: ası́, su función generadora
será (1 + x6 + x12 + x18 + x24 ) y los valores que puede tener z son enteros y no
negativos: ası́, su función generadora será (1 + x + x2 + · · · + x27 ).
La respuesta al problema es expresada por el coeficiente de x27 de la función
generadora

g(x) = (x8 + x16 + x24 )(1 + x6 + x12 + x18 + x24 )(1 + x + x2 + · · · + x27 ).

89. (t2004-pac22 ) Un expediente académico contiene las notas de Matemáticas,

Fı́sica, Quı́mica e Informática (notas enteras entre 0 y 10). Utilizando funciones
generadoras, resuelve los siguientes apartados:

(a) Considerando todos los expedientes, ¿cuántos tendrán una nota mediana
de 2?
(b) Ahora consideramos sólo los expedientes con nota de Matemáticas superior
o igual que cinco. ¿Cuántos tendrán una nota mediana de 7?

Solución

(a) Si la nota mediana debe ser 2, la suma de las 4 notas debe ser 8. Por lo
tanto, la solución es el número de soluciones enteras no negativas de la
ecuación x + y + z + t = 8, o equivalentemente el coeficiente de x8 de la
función generadora f (x) = (1 + x + x2 + · · · + x10 )4 . Podemos escribir
11 4
f (x) = (1−x )
(1−x)4 . Calculamos f8 = α0 β8 , siendo α(x) = (1 − x ) y
11 4

1 4+8−1


β(x) = (1−x) 4 , por lo tanto f8 = CR(4, 8) = 8 = 165.

(b) En este caso, la suma de las notas debe ser 28. Por lo tanto, la solución
es el número de soluciones enteras de la ecuación x + y + z + t = 28,
donde 5 ≤ x y x, y, z, t ≤ 10, o equivalentemente el coeficiente de x28 de
la función generadora

g(x) = (x5 + x6 + · · · + x10 )(1 + x + x2 + · · · + x10 )3 .

6 11 3
Podemos escribir g(x) = x5 (1−x 1−x
) (1−x ) 5 6 11 3
(1−x)3 = x (1 − x )(1 − x ) (1−x)4 ,
1

por lo tanto se trata de calcular el coeficiente de x23 , de f (x) = (1−x6 )(1−

1 1
x11 )3 (1−x) 6
4 . Sea α(x) = (1 − x ), β(x) = (1 − x
11 3
) y γ(x) = (1−x) 4 . Ası́,

f23 = α0 β0 γ23 + α0 β11 γ12 + α0 β22 γ1 + α6 β0 γ17 + α6 β11 γ6 = CR(4, 23) −

C(3, 1)CR(4, 12)+C(3, 2)CR(4, 1)+(−1)·CR(4, 17)+(−1)(−C(3, 1))CR(4, 6) =
2600 − 3 · 455 + 3 · 4 − 1140 + 3 · 84 = 359.
Capı́tulo 4

Ecuaciones recurrentes y
complejidad computacional

90. (t2001-final2 ) Resuelve la ecuación recurrente:

xn − 4xn−1 + 5xn−2 − 2xn−3 = 0; x0 = 0, x1 = x2 = −1

Solución
La ecuación caracterı́stica es

t3 − 4t2 + 5t − 2 = 0 ⇔ (t − 2)(t − 1)2 = 0

por lo tanto las raı́ces son t = 2 y t = 1 con multiplicidad 2. Ası́, la solución

general es
xn = α2n + β + γn.
Teniendo en cuenta las condiciones iniciales, formamos el sistema

0 =α+β
−1 = 2α + β + γ
−1 = 4α + β + 2γ

que tiene como solución α = 1, β = −1 y γ = −2. Ası́, la solución que verifica

las condiciones iniciales es

xn = 2n − 1 − 2n.

91. (p2002-pac24 ) Sea xn el número de palabras de longitud n en el alfabeto

{0, 1, 2} de forma que no contienen la secuencia 01 ni la 02. Formula una ecuación
recurrente para obtener xn y utilizala para obtener el valor de los 5 primeros
términos. Considera x0 = 1. Usando una ecuación recurrente, determina una
expresión que permita evaluar xn en función de n. Considera x0 = 1.

48
Ecuaciones recurrentes y complejidad computacional 49

Solución
El total xn se puede descomponer con las palabras que empiezan por 1, xn−1 ,
más las que empiezan por 2, xn−1 , más las que empiezan por 0 que únicamente
es la palabra todo ceros. Ası́

xn = 2xn−1 + 1 ∀n ≥ 1

con x0 = 1. Por lo tanto, x1 = 3, x2 = 7, x3 = 15, x4 = 31, x5 = 63, . . .

92. (p2002-pac25 ) Resuelve la ecuación recurrente siguiente:

xn = 3xn−2 − 2xn−3 + 2n ; x0 = 0, x1 = −1, x2 = 1

Solución
La ecuación caracterı́stica de la ecuación recurrente homogénea es

t3 − 3t + 2 = 0 ⇔ (t − 1)2 (t + 2) = 0

por lo tanto las raı́ces son t = 1 con multiplicidad 2 y t = −2. Ası́, la solución
general es xn = α(−2)n + β + γn + Rn , siendo Rn una solución particular de
la ecuación recurrente inicial no homogénea. Ensayamos una solución por Rn
tomando Rn = c 2n y sustituyendo en la ecuación recurrente a resolver tenemos

c 2n − 3 c 2n−2 + 2 c 2n−3 − 2n =0
2n−3 (c 23 − 3 c 2 + 2 c − 23 ) =0
8c − 6c + 2c − 8 =0
c =2

La solución general será pues xn = α(−2)n + β + γn + 2n+1 . Teniendo en cuenta

las condiciones iniciales, formamos el sistema

x0 = 0 =α+β+2
x1 = −1 = −2α + β + γ + 4
x2 = 1 = 4α + β + 2γ + 8
−19 −8
que tiene como solución α = 91 , β = 9 yγ= 3 . Ası́, la solución que verifica
las condiciones iniciales es
1 19 8
xn = (−2)n − − n + 2n+1
9 9 3

93. (p2002-final2 ) Sabiendo que la sucesión

(xn ) = 2, −5, 8, −11, 14, −17, 20, . . . (n = 0, 1, . . .)

se puede expresar mediante una ecuación recurrente lineal homogénea de orden

2, determina la expresión recurrente y resuélvela para calcular x100 .
Ecuaciones recurrentes y complejidad computacional 50

Solución
Una ecuación recurrente lineal homogénea de orden 2 es de la forma

xn + axn−1 + bxn−2 = 0 ∀n ≥ 2.

Se trata de encontrar los coeficientes constantes a y b. Para ello sustituimos n

por dos valores diferentes mayores o igual a 2, de forma que podamos formar
un sistema con dos ecuaciones y dos incógnitas

n=2 x2 + ax1 + bx0 = 0

n=3 x3 + ax2 + bx1 = 0

Sustituyendo por los términos de la sucesión, obtenemos el sistema

8 − 5a + 2b =0
−11 + 8a − 5b =0

que tiene como solución a = 2 y b = 1. Por lo tanto, la ecuación recurrente es

xn + 2xn−1 + xn−2 = 0 ∀n ≥ 2

con x0 = 2 y x1 = −5.
La ecuación caracterı́stica es t2 + 2t + 1 = 0 ⇔ (t + 1)2 = 0. Dado que
tiene una raı́z t = −1 con multiplicidad 2, podemos formar las dos soluciones
independientes xn = (−1)n y xn = n (−1)n−1 . Ası́, la solución general es xn =
α(−1)n + βn(−1)n−1 . Teniendo en cuenta las condiciones iniciales, formamos el
sistema
x0 = 2= α
x1 = −5 = −α + β
que tiene como solución α = 2 y β = −3. La solución que verifica las condiciones
iniciales es
xn = (2 + 3n)(−1)n .
Por lo tanto, x100 = 302.

94. (p2002-final6 ) Resuelve la ecuación recurrente siguiente:

xn + 6xn−1 + 12xn−2 + 8xn−3 = 0; x0 = 2, x1 = −3, x2 = 4

Solución
La ecuación caracterı́stica es

t3 + 6t2 + 12t + 8 = 0 ⇔ (t + 2)3 = 0

por lo tanto tiene una única raı́z t = −2 con multiplicidad 3. Ası́, la solución
general es
xn = α(−2)n + βn(−2)n−1 + γn(n − 1)(−2)n−2 .
Ecuaciones recurrentes y complejidad computacional 51

Teniendo en cuenta las condiciones iniciales, formamos el sistema

x0 = 2 =α
x1 = −3 = −2α + β
x2 = 4 = 4α − 4β + 2γ

que tiene como solución α = 2, β = 1 y γ = 0. Por lo tanto, la solución que

verifica las condiciones iniciales es xn = 2(−2)n + n(−2)n−1 o equivalentemente

xn = (−2)n−1 (n − 4).

95. (t2002-pac24 ) Dada la ecuación recurrente siguiente:

xn − xn−1 − 5xn−2 − 3xn−3 = 2n + 3.

(a) Determina la solución general de la ecuación recurrente homogénea asoci-

ada, o sea, xn − xn−1 − 5xn−2 − 3xn−3 = 0.
(b) Determina una solución particular de la ecuación no homogénea inicial.
(c) Determina la solución general de la ecuación no homogénea a partir de los
apartados anteriores.
(d) ¿Cuál es la solución de la ecuación recurrente no homogénea que cumple
las siguientes condiciones iniciales, x0 = 0, x1 = −1/4, x2 = −41/2 ?

Solución

(a) La ecuación caracterı́stica es t3 − t2 − 5t − 3 = 0 ⇔ (t + 1)2 (t − 3) = 0.

Dado que tiene una raı́z, t = −1, de multiplicidad 2 y otra, t = 3, de
multiplicidad 1, podemos formar las tres soluciones xn = (−1)n , xn =
n (−1)n−1 y xn = 3n . Ası́, la solución general es xn = α (−1)n +βn (−1)n−1 +
γ3n , siendo α, β y γ constantes cualesquiera.
(b) Ensayamos una solución particular tomando Rn = an + b.
Sustituyendo en la ecuación recurrente a resolver, tenemos

(an + b) − (a(n − 1) + b) − 5(a(n − 2) + b) − 3(a(n − 3) + b) = 2n + 3

que desarrollando queda

(a − a − 5a − 3a)n + (b − b + a + 10a − 5b + 9a − 3b) = 2n + 3

igualando los coeficientes en los dos miembros se forma el sistema

−8a = 2
20a − 8b = 3
−1
que tiene por solución a = 4 y b = −1. Por lo tanto, la solución particular
n
es Rn = − − 1
4
Ecuaciones recurrentes y complejidad computacional 52

(c) La solución general de la ecuación recurrente no homogénea es

n
xn = α (−1)n + βn (−1)n−1 + γ3n − −1
4
α, β y γ son constantes cualesquiera.
(d) Sustituyendo las condiciones iniciales en la solución general del apartado
(c), formamos el sistema

x0 = 0 =α+γ−1
x1 = −1/4 = −α + β + 3γ − 1/4 − 1
x2 = −41/2 = α − 2β + 9γ − 2/4 − 1

que tiene como solución α = 2, β = 6 y γ = −1. Ası́, la solución que

verifica las condiciones iniciales es
n
xn = 2 (−1)n + 6n (−1)n−1 − 3n − −1
4

96. (t2002-pac25 ) Calcula la complejidad de cada uno de los fragmentos del

algoritmo siguiente y utilı́zala para hallar la complejidad total del algoritmo.
Asimismo escribe un algoritmo alternativo que dé el mismo resultado con menos
complejidad y calcúlala.

1 suma ← 0
2 para y ← 1 hasta n
3 suma ← suma + 2y
4 fin para

Solución
La inicialización de la variable suma tiene una complejidad O(1). La segunda
instrucción tiene una complejidad de O(n) y como que el interior del bucle
cuesta 3, la complejidad de todo el bucle es O(3n) = O(n). Aplicando las reglas
de la complejidad nos resulta O(n) para todo el algoritmo.
y=n n
X X n(n + 1)
Este algoritmo calcula 2y = 2 y=2 = n2 + n y, esto, es puede
y=1 y=1
2
calcular directamente con 3 operaciones, o sea complejidad O(1) según el algo-
ritmo:
1 suma ← n2 + n

97. (t2002-pac42 ) Resuelve la ecuación recurrente xn −2xn−1 = 3xn−2 +n2 −n−1

con las condiciones iniciales x1 = 2, x2 = 5.

Solución
Ecuaciones recurrentes y complejidad computacional 53

El ecuación caracterı́stica de la ecuación homogénea asociada śe t2 − 2t − 3 = 0,

que tiene como raı́ces 3 y −1. Por lo tanto, la solución de la ecuación recurrente
es α3n + β(−1)n + Rn , siendo Rn una solución particular que buscaremos acto
seguido. Ensayemos una solución del tipo an2 +bn+c. Sustituyendo a la ecuación
recurrente y comparando términos del mismo grado, obtenemos que a = −1/4,
b = −3/4, c = −3/8. Por lo tanto, la solución general de la ecuación recurrente
2
nos queda α3n + β(−1)n − n4 − 3n 3
4 − 8 . Imponiendo las condiciones iniciales,
nos queda un sistema formado por las dos ecuaciones 3α − β − 11/8 = 2 y
9α + β − 23/8 = 5, que tienen por solución α = 15/16 y β = −9/16. Ası́, pues,
la solución de la ecuación recurrente es
15 n 9 n2 3n 3
3 − (−1)n − − − .
16 16 4 4 8

98. (t2002-final2 ) Resuelve la ecuación recurrente siguiente:

xn = 2xn−1 + 9xn−2 − 18xn−3 + 16 (n ≥ 3) x0 = 0, x1 = 3 y x2 = −11

Solución
La ecuación caracterı́stica de la ecuación recurrente homogénea es

t3 − 2t2 − 9t + 18 = 0 ⇔ (t − 2)(t − 3)(t + 3) = 0

por lo tanto las raı́ces son t = 2, t = 3 y t = −3. Ası́, la solución general es

xn = α2n +β3n +γ(−3)n +Rn , siendo Rn una solución particular de la ecuación
recurrente inicial no homogénea. Probamos una solución por Rn tomando Rn =
c y sustituyendo en la ecuación recurrente a resolver tenemos c = 2c + 9c − 18c +
16, por lo tanto c = 2. La solución general será pues xn = α2n +β3n +γ(−3)n +2.
Teniendo en cuenta las condiciones iniciales, formamos el sistema

x0 = 0 =α+β+γ+2
x1 = 3 = 2α + 3β − 3γ + 2
x2 = −11 = 4α + 9β + 9γ + 2

que tiene como solución α = γ = −1 y β = 0. Ası́, la solución que verifica las

condiciones iniciales es

xn = (−1)2n + (−1)(−3)n + 2.

99. (p2003-pac23 ) Nos dan la sucesión xn = −5, 5, 15, 65 . . . (n = 0, 1, . . .)

y nos aseguran que se puede expresar mediante una ecuación recurrente lineal
homogénea de orden 2. Determináis la expresión recurrente y resuélvela (da el
término general)

Solución
Ecuaciones recurrentes y complejidad computacional 54

La ecuación que nos piden es xn = Axn−1 +Bxn−2 . Con los datos del enunciado
podemos plantear el sistema de ecuaciones:

15 = 5A − 5B
65 = 15A + 5B

Las soluciones de este sistema son A = 4, B = 1 y, a partir de ellas, podremos

escribir la ecuación recurrente asociada al problema:
xn = 4xn−1 + xn−2 ∀n ≥ 2
con condiciones iniciales x1 = 5, x2 = 15.
La ecuación caracterı́stica de la ecuación recurrente es t2 − 4t − 1 = 0. Las raı́ces
son √
t = 2 ± 5.
Ası́, la solución general es
 √ n  √ n
xn = α 2 + 5 + β 2 − 5

Si tomamos las condiciones iniciales x1 = 5, x2 = 15 obtenemos

√ √
5 = α(2 + √5) + β(3 − 5) √
15 = α(2 + 5)2 + β(2 − 5)2
√ √
−5 + 3 6 −3 − 3 5
de donde resulta α = , β = . Por lo tanto, el término
2 2
general viene dado por
√ √
−5 + 3 8  √ n −5 − 3 5  √ n
xn = f (n) = 2+ 5 + 2− 5
2 2

100. (p2003-pac42 ) Sea S el conjunto de todas las palabras ternarias de longitud

n en las que no aparecen dos ceros consecutivos.

(a) Encuentra una relación de recurrencia por el cardinal de S, ası́ como las
condiciones iniciales.
(b) Da una expresión por el cardinal de S en función de n. Puedes asumir que
si n = 0, entonces S estarı́a formato por la palabra vacı́a.

Solución

(a) Sea xn el cardinal de S cuando la longitud de las palabras es n. Observamos

que añadiendo un uno o un dos a las palabras de longitud n−1 que cumplen
el enunciado obtendremos palabras de longitud n que siguen cumpliendo
el enunciado. Tras lo cual nos faltará sumar las palabras que acaban en
0, y que son las palabras de longitud n − 2 a las cuales se añade un 10, o
bien, un 20, y que por lo tanto, también cumplirán el enunciado.
O sea, el total de palabras es xn = 2xn−1 +2xn−2 . Las condiciones iniciales
serian x1 = 3, x2 = 8.
Ecuaciones recurrentes y complejidad computacional 55

(b) La ecuación caracterı́stica de la ecuación recurrente es t2 − 2t − 2 = 0. Las

raı́ces son √
t = 1 ± 3.
Ası́, la solución general es
 √ n  √ n
xn = α 1 + 3 + β 1 − 3

Si tomamos las condiciones iniciales x0 = 1, x1 = 3 obtenemos

1=α+β √ √
3 = α(1 + 3) + β(1 − 3)
√ √
3+2 3 3−2 3
de donde resulta α = , β = . Por lo tanto, el término
6 6
general viene dado por
√ √
3+2 3 √ n 3 − 2 3  √ n
xn = 1+ 3 + 1− 3 .
6 6

101. (t2004-pac23 ) Resuelve la ecuación recurrente siguiente:

xn = 2xn−1 + 9xn−2 − 18xn−3 + 16 (n ≥ 3) x0 = 0, x1 = 3 y x2 = −11

Solución
La ecuación caracterı́stica de la ecuación recurrente homogénea es

t3 − 2t2 − 9t + 18 = 0 ⇔ (t − 2)(t − 3)(t + 3) = 0

por lo tanto las raı́ces son t = 2, t = 3 y t = −3. Ası́, la solución general

es xn = α2n + β3n + γ(−3)n + Rn , siendo Rn una solución particular de la
ecuación recurrente inicial no homogénea. Ensayamos una solución para Rn
tomando Rn = c y sustituyendo en la ecuación recurrente a resolver tenemos
c = 2c + 9c − 18c + 16, por lo tanto c = 2. La solución general será pues
xn = α2n + β3n + γ(−3)n + 2. Teniendo en cuenta las condiciones iniciales,
formamos el sistema
x0 = 0 =α+β+γ+2
x1 = 3 = 2α + 3β − 3γ + 2
x2 = −11 = 4α + 9β + 9γ + 2

que tiene como solución α = γ = −1 y β = 0. Ası́, la solución que verifica las

condiciones iniciales es

xn = (−1)2n + (−1)(−3)n + 2.

102. (t2004-pac24 )
Fundamentos de grafos 56

(a) Plantea una función generadora y di qué coeficiente darı́a el número de

maneras de colocar treinta objetos idénticos en cuatro bolsos idénticos,
con la única restricción que en cada bolso deba haber como mı́nimo un
objeto.
(b) Una bandera consta de n franjas horizontales que pueden pintarse de 4
colores diferentes. Escribe una ecuación recurrente para el valor an de
banderas diferentes que se pueden diseñar si no pueden haber franjas ady-
acentes con el mismo color y tampoco las franjas superior e inferior pueden
tener el mismo color.

Solución

(a) Debemos calcular el número de soluciones enteras de x1 +x2 +x3 +x4 = 30,
donde 0 < x1 ≤ x2 ≤ x3 ≤ x4 . Sea a, b, c ≥ 0 tales que x2 = x1 + a, x3 =
x2 + b, x4 = x3 + c. Ası́, la solución es equivalente al número de soluciones
enteras de x1 +x1 +a+x1 +a+b+x1 +a+b+c = 4x1 +3a+2b+c = 30, x1 > 0
y 0 ≤ a, b, c. El resultado que buscamos vendrı́a dado por el coeficiente del
término x30 de la función generadora siguiente:

(x4 +x8 +· · · )(1+x3 +x6 +x9 +· · · )(1+x2 +x4 +x6 +· · · )(1+x+x2 +x3 +· · · ).

(b) Sea an el número de banderas de n franjas con las restricciones del enun-
ciado. Si sabemos como pintar las banderas con n − 1 franjas, para pintar
la franja que falta debemos considerar dos casos: si el color de la franja
n − 1 y la primera son diferentes disponemos de dos colores más y si es-
tos son iguales disponemos de tres colores, pero sólo hace falta considerar
banderas con n − 2 franjas ya pintadas. En el primer caso hay 2an−1 ban-
deras diferentes y en el segundo 3an−2 , por lo tanto obtenemos la ecuación
recurrente an = 2an−1 + 3an−2 , ∀n ≥ 4.
Capı́tulo 5

Fundamentos de grafos

103. (p99-pac21 ) Prueba que cualquier grafo con un mı́nimo de 2 vértices,

siempre contiene 2 vértices con el mismo grado.

Solución
Es evidente en el supuesto de que n = 2; demostrémoslo por induccció (se supone
cierto por grafos de orden n − 1 y se demuestra por grafos de orden n).
Considerémoslo cierto por un grafo de orden n − 1 y demostrémoslo por un
grafo de orden n. Los vértices de un grafo de orden n pueden tener grados: 0,
1, 2, 3, ..., n − 2 y n − 1. Es decir, un total de n posibilitados. Queremos ver
que se repiten dos de estos grados, es decir, que no se pueden lograr todas estas
posibilidades (que son n, el mismo número que el orden del grafo). Si este grafo
no tiene vértice de grado 0, entonces, a la fuerza, se repiten algunos de los otros
grados posibles y, por lo tanto, ya estarı́a demostrado el resultado. Suponemos,
en cambio, que hay un vértice de grado 0. Este vértice no está conectado con
ningún otro vértice del grafo. Podemos, pues, eliminar este vértice y considerar
el resto del grafo. Este otro grafo tiene n-1 vértices y las mismas aristas que
el primero grafo (el de orden n). Ahora bien, por hipótesis (todos los grafo se
orden n − 1 tienen 2 vértices con el mismo grado) este grafo de orden n − 1 tiene
dos vértices con el mismo grado. Por lo tanto, el grafo inicial (que es igual a
este último grafo de orden n − 1 más un vértice de grado 0) también tiene dos
vértices con el mismo grado.
Este resultado también se puede demostrar de manera todavı́a más sencilla. Los
vértices de un grafo de orden n pueden tener, como hemos dicho, n posibles
grados. Ahora bien, los grados 0 y n − 1 son mutuamente incompatibles (no
puede ser que un vértice tenga grado 0 y otro vértice tenga grado n-1, porque
este último no podrı́a estar conectado al vértice de grado 0). Por lo tanto, de
hecho, sólo hay n-1 posibilidades para los n vértices de un grafo de orden n.
Aplicando el principio de las cajas, dos vértices deben tener el mismo grado. En
este caso, no hace falta aplicar la inducción.

104. (t99-pac21 ) En una reunión con más de 2 personas, cada una tiene amistad

57
Fundamentos de grafos 58

exactamente con dos. Demuestra que se pueden distribuir los asistentes a la

reunión en mesas redondas (no hace falta que sea una única mesa) de forma que
cada persona siente junto a sus amigos.

Solución
De hecho, se debe demostrar que todo grafo 2-regular es isomorfo a un ciclo, o
bien, a una reunión de ciclos (si no es conexo). Lo demostraremos por inducción:
suponemos que el grafo tiene 3 vértices: el único grafo con 3 vértices 2-regular
es C3 . Suponemos que es cierto por un grafo con n vértices: demostrémoslo
por un grafo con n + 1 vértices. Sea v un vértice de este grafo G: este vértice
tiene 2 vértices adyacentes, v1 y v2 . Consideramos el grafo G0 que tiene el mismo
conjunto de vértices que G, excepto el vértice v, y la arista v1 v2 , además de todas
las otras aristas del grafo G que unen vértices de G0 . Este grafo es 2-regular y
tiene n vértices, por lo tanto, por hipótesis de inducción, el grafo G0 es puede
poner como reunión de ciclos conexos. En un de estos conexos encontraremos
v1 y v2 y la arista que los une. Hacemos la manipulación contraria a la anterior:
añadimos el vértice v y sus aristas, y eliminamos la arista v1 v2 . Claro está que
esta componente conexa continúa siendo un ciclo y, por lo tanto, G es reunión
de ciclos.

105. (t99-pac24 ) Demuestra que en una reunión con un número par de asis-
tentes, hay dos con un número par de conocidos comunes.

Solución
Modelizaremos esta situación con un grafo con n vértices, que son los compo-
nentes de esta reunión. Hay una arista entre dos vértices si estas dos personas
son conocidas. Para demostrar el enunciado, supondremos que todos los pares
de vértices tienen un número impar de vértices adyacentes comunes. Sea v un
vértice y consideramos el subgrafo inducido por los vértices adyacentes de v. Los
grados de estos vértices son todos impares, debido a la suposición que hemos
hecho (el vértice v y cualquiera de los adyacentes tienen un número impar de
vértices adyacentes comunes). Por lo tanto, el número de vértices adyacentes
a v es par (de lo contrario, la suma de grados del grafo inducido serı́a impar).
En definitiva, el grado de todos los vértices del grafo es par. Buscamos ahora
todos los caminos de longitud 2 que empiezan en v no triviales. En total hay un
número par, porque todos los vértices tienen grado par. Ahora bien, el número
de vértices diferentes de v es impar y el número de vértices adyacentes a v y
a cualquiera de los otros vértices también es impar. Por lo tanto, el número de
estos caminos que llegan a v es impar (impar × impar = impar). Por un lado
el número total de caminos de longitud 2 que empiezan a v es par y, por otro
lado, el número de los que llegan es impar; esto es contradictorio. Por lo tanto,
la suposición inicial es incorrecta. En definitiva, como mı́nimo hay 2 vértices
que tienen un número de vértices adyacentes comunes par.

106. (t99-final6 ) En una zona remota de montaña hay 3 valles aislados, uno
Fundamentos de grafos 59

de ellos tiene pocos pueblos, otro tiene el doble de pueblos y el último tiene el
triple de pueblos que el primero. Dos pueblos de un mismo valle están unidos
por un único camino, que no pasa por ningún otro pueblo. Sólo hay un camino
que una un valle con otro valle (de hecho, une dos pueblos de estos dos valles).

Si, en total, hay 103 caminos, ¿cuántos pueblos tiene cada valle?
Generaliza los resultados en el siguiente sentido: Un grafo G tiene n
vértices y, exactamente, k componentes conexas (k ≤ n), ¿cuál es el máxi-
mo de aristas posible en G?

Solución
Empezaremos respondiendo al segundo apartado.
Si las componentes
Pk conexas tienen, cada una de ellas, ni vértices i = 1, 2 . . . k,
de forma que
i=1 ni = n, el máximo número de vértices de cada componente
conexa es n2i . Por eso es por lo que el máximo número de aristas de un grafo
de este tipo es:
k  
X ni
i=1
2

Por otro lado, es fácil comprobar que, si b ≤ a

       
a b a+1 b−1
+ ≤ +
2 2 2 2

si desarrollamos los dos términos

   
a b 1 1
+ = (a(a − 1) + b(b − 1)) = (a2 − a + b2 − b)
2 2 2 2
   
a+1 b−1 1
+ = (a2 + a + b2 − 3b + 2)
2 2 2
si sustituimos a los dos miembros de la desigualdad que volamos probar:

a2 − a + b2 − b ≤ a2 + a + b2 − 3b + 2

que es equivalente a b − 1 ≤ a, cosa que es cierta.

Es decir, la forma de maximizar

k  
X ni
i=1
2

consiste en aumentar una de las ni hasta el máximo posible (suponemos que sea
n1 ). La única forma de hacerlo es reducir al máximo las otras. Es decir, ni = 1
por i = 2 . . . k. En definitiva, n1 = n − k + 1, y el número máximo de aristas de
este grafo es:
Fundamentos de grafos 60

 
n−k+1
2
Acabaremos respondiendo a la primera parte:
Si p1 , p2 y p3 son los pueblos de cada valle, p2 = 2p1 y p3 = 3p1 .
Por lo tanto, el número total de caminos es
     
p1 2p1 3p1
+ + + 3 = 103
2 2 2

resolviendo esta ecuación de 2n grado p1 = 4, p2 = 8 y p3 = 12.

107. (t99-final10 ) G es un árbol en el que, a parte de las hojas, hay 4 vértices

de grado 2, 1 de grado 3, 2 de grado 4 y 1 de grado 5. Calcula el número total
de vértices de este grafo.

Solución
Es sabido que la suma de grados de los vértices de un grafo es el doble de las
aristas. Además, un árbol tiene un vértice más que el número de aristas. Por lo
tanto, la suma de grados es igual al doble del número de vértices menos 1, es
decir,
X
g(v) = 2(v − 1)

si n es el número de vértices de grado 1, la suma de grados es 24 + n, por lo

tanto,

24 + n = 2(7 + n)

Ası́ n = 10 y el número total de vértices es 18.

108. (p2000-pac23 ) Di si los grafos de la siguiente figura son isomorfos. Razona

la respuesta.

Solución
No son isomorfos, puesto que aunque tengan la misma cantidad de vértices, estos
no conservan las adyacencias. Fijaos que la secuencia de grados en el primero
grafo es: 2, 2, 3, 3, 4, 4 y en el segundo 2, 2, 2, 4, 4, 4.
Fundamentos de grafos 61

109. (p2000-pac24 ) ¿Cuál de las cuatro afirmaciones siguientes son ciertas?

Razona la respuesta.

En todo grafo hay un número impar de vértices de grado par.

En todo grafo hay un número par de vértices de grado impar.
En todo grafo, la suma de los grados de los vértices es un número par.
En todo grafo de n vértices que tenga un mı́nimo de n aristas podemos
asegurar que hay un ciclo.

Solución
El primer apartado es falso. Por ejemplo podéis pensar en un cuadrado. Todos
los vértices son de grado par y hay cuatro.
El segundo apartado es cierto. Este resultado se deduce de la fórmula de grados.
El tercer apartado es cierto. El resultado se deduce de la fórmula de grados.
Efectivamente, la suma de los grados de cada vértice es el doble del número de
aristas (o sea, un número par).
El cuarto apartado es cierto. Tal y como está escrito el enunciado podemos coger
alguna componente conexa en la que el número de aristas sea más grande o igual
que el número de vértices. En esta componente conexa habrá un ciclo.

110. (p2001-pac44 ) Demuestra que un grafo conexo con n vértices y n aristas

(n ≥ 3) contiene un único ciclo.

Solución
Cualquier grafo debe cumplir una, y sólo una, de estas opciones:

No contiene ningún ciclo.

Contiene un único ciclo.
Contiene más de un ciclo.

Vemos que no son posibles ni la primera ni la tercera opciones:

No contiene ningún ciclo.

No es posible porque no es un árbol: tiene tantas aristas como vértices.
Contiene más de un ciclo.
Suponemos que C1 y C2 son dos ciclos diferentes. Suponemos que a1 es
una arista de C1 pero no de C2 . Si eliminamos esta arista nos queda un
grafo conexo con n vértices y n − 1 aristas. Por lo tanto, nos encontramos
ante de un árbol. Pero esto no es posible, porque contiene un ciclo, C2 .
Por lo tanto, no es posible que este grafo contenga más de un ciclo.
Fundamentos de grafos 62

111. (p2001-final4 ) Una revista cientı́fica publica 8 problemas para que los lec-
tores intenten resolverlos. La revista recibe exactamente 2 respuestas correctas
para cada uno de los problemas que provienen de autores diferentes. Todas las
respuestas correctas han sido enviadas por 8 personas, a razón de 2 soluciones
por persona. ¿Es posible publicar una única solución por cada problema (y, por
lo tanto, el nombre de un único acertante), de forma que las 8 personas sean
mencionadas exactamente una vez? Razona tu respuesta.

Solución
Si pensamos esta situación como un grafo bipartido de 16 vértices (P-preguntas,
R-personas que responden), cada vértice P está unido a 2 únicos vértices R
(quienes responden bien a la pregunta P), mientras que cada vértice R está unido
a 2 únicos vértices P (las preguntas que responde correctamente la persona R).
Entonces, esta situación se puede modelar con un grafo que todos los vértices de
grado 2. Una de las posibilidades es este grafo sea un ciclo y, además, bipartido,
como por ejemplo:

Si empezamos por la publicación de una pregunta, podemos poner la respuesta

(y el nombre correspondiente) de la persona que se encuentra a la derecha en el
grafo. De este modo conseguiremos publicar los 8 problemas y los ocho autores,
citando cada uno de los autores en una única publicación.
Hay otras posibilidades: el grafo seria una unión de ciclos como por ejemplo:
- dos ciclos de 8 vértices cada uno.
- cuatro ciclos 4 vértices cada uno.
etc.

112. (p2001-final7 ) Prueba que si G es un grafo cualquiera con más de 4 vértices,

entonces G, o bien el grafo complementario Gc contiene un ciclo.
¿Es cierto con grafos de menos de 5 vértices? Razona la respuesta

Solución
Empezamos con la segunda pregunta: es evidente que los grafos de 1 y 2 vértices
no tienen ciclos y, por lo tanto, la pregunta no es pertinente. Por grafos de 3
Fundamentos de grafos 63

vértices, tenemos el grafo T3 , de forma que no contiene ningún ciclo, ni tampoco

su complementario. Por grafos de 4 vértices, tenemos el grafo T4 , de forma que
no contiene ningún ciclo, ni tampoco su complementario (que también es T4 ).
Si el grafo G contiene n vértices (n ≥ 4), entonces, el número de aristas de este
grafo ha de estar entre 0 y n(n−1)2 . Para comprobar que uno de los dos tiene un
ciclo, sólo debemos ver que uno de los dos tiene, como mı́nimo n aristas.
Claro está que, o bien G, o bien, Gc , tienen, como mı́nimo, la mitad de aristas
del grafo completo, es decir, n(n−1)4 aristas. Por lo tanto, harı́a falta ver que

n(n − 1)
≥n
4
Esto es fácilmente demostrable:

n(n − 1)
≥ n ⇔ n2 − n ≥ 4n ⇔ n2 − 5n ≥ 0 ⇔ n(n − 5) ≥ 0
4
Pero esto es cierto, porque n ≥ 5.

113. (t2000-p5 ) Un cubo de queso está dividido en 27 cubos pequeños iguales

(cómo si se tratara de un cubo de Rubik). Los quesos de los que están he-
chos estos cubos pequeños son de dos tipos diferentes: uno de roquefort y el
otro parmesano. Estos pequeños cubos están colocados de forma que dos cubos
pequeños del mismo tipo de queso no pueden tener nunca una cara común. Un
ratón empieza en una de las esquinas y se come cada uno de estos pequeños
cubos, un tras el otro. Siempre pasa de un cubo pequeño a otro que tiene una
cara en común con el anterior.

(a) Si se modeliza los posibles trayectos del ratón sobre el queso mediante
un grafo, ¿cuál es la secuencia de grados de este grafo (apúntalos de más
pequeños a más grandes)? ¿Cuál es la medida de este grafo?
(b) ¿El ratón puede acabar su recurrido al cubo pequeño que ocupa el centro
del cubo grande? Razona la respuesta.

Solución

(a) Los vértices de este grafo son los cubos pequeños, es decir, 27 vértices;
las aristas de este indican que los vértices que unen comparten una cara.
Cada uno de los cubos pequeños que se encuentran en los vértices del cubo
grande tiene 3 caras en contacto con otros cubos; por lo tanto, el grado
del vértice asociado es 3. El grafo tiene 8 vértices de grado 3.
Hay 12 cubos pequeños que comparten 4 caras con otros cubos. Por lo
tanto, el grafo tiene 12 vértices de grado 4.
Hay 6 cubos pequeños (que se encuentran en el centro de cada cara) que
comparten 5 caras con otros cubos. Por lo tanto, el grafo tiene 6 vértices
de grado 5.
Finalmente, el cubo pequeño que ocupa el centro del cubo tiene todas las
Fundamentos de grafos 64

caras compartidas; por lo tanto, el grafo tiene 1 vértice de grado 6.

En definitiva, la secuencia de grados es:

333333334444444444445555556

La medida del grafo, por el lema de los grados, es la suma de grados

dividido por 2: 54 aristas.

(b) Tal y como está definido el grafo, es bipartido: los vértices que representan
cubos pequeños del mismo tipo de queso no son nunca adyacentes. Por lo
tanto, los vértices del grafo se pueden dividir en dos grupos: uno, de 13
vértices (cubos pequeños de un tipo de queso) y el otro, de 14 vértices (cu-
bos pequeños del otro tipo de queso). Si se empieza a un vértice cualquiera,
tras 26 movimientos por el grafo (26 vértices nuevos + vértice inicial =
27 vértices), nos encontraremos en un vértice de la misma partición que
el inicial (es decir, en un cubo de queso del mismo tipo). Ahora bien, el
pequeño cubo central es, evidentemente, de un queso diferente al del cubo
inicial, que se encuentra en una esquina. Por eso es por lo que el ratón no
puede acabar su recurrido en el centro del cubo.

114. (t2001-pac31 ) Sea G un grafo conexo con n vértices. Demuestra que si el

grado de cada vértice es el mismo en G que en Gc (Gc es el grafo complementario
de G) entonces G es regular y n es impar.

Solución
Sea ni el grado del vértice vi ∈ G. Entonces el vértice vi ∈ G tendrá grado
n − ni − 1 = ni . De aquı́, 2ni = n − 1 y ni = n−1
2 ∀y. Por lo tanto G es regular.
Además, para que n−12 sea un entero hace falta que n sea impar.

115. (p2002-pac32 ) Denotamos por Km,n el grafo bipartido completo de orden

m + n.
(a) ¿Para qué valores de n y m el grafo Km,n es regular?
c
(b) Describe el grafo Km,n (el grafo complementario de Km,n ) como combi-
nación de los grafos Km y Kn
(c) Si Gs representa un grafo bipartido de orden s, ¿cuál será el número
máximo de aristas que puede tener Gs en función de s?

Solución
(a) Si los vértices de Km,n están divididos en dos conjuntos V1 , V2 , entonces
todos los vértices de V1 tienen grado n y todos los de V2 tienen grado m.
Ası́, Km,n será regular cuando n = m.
Fundamentos de grafos 65

c
(b) A Km,n todos los vértices de V1 serán adyacentes entre sı́. También to-
dos los de V2 serán adyacentes entre sı́. Además, ningún vértice de V1
c
será adyacente a ningún vértice de V2 . Ası́, Km,n = Km ∪ Kn
(c) Si Gs = (V1 ∪ V2 , A) y decimos x = |V1 | entonces, s − x = |V2 | y |A| =
x(s − x). Consideramos la función f (x) = x(s − x), entonces queremos
calcular x de manera f (x) sea máximo. f (x) tendrá un máximo cuando
f 0 (x) = s − 2x = 0 y f 00 (x) = −2 < 0. De aquı́, x = s/2 y el número
2
máximo de aristas será 2s (s − 2s ) = s4 .

116. (p2002-final7 ) En una competición de ajedrez hay n participantes. Re-

sponde, usando la teorı́a de grafos, las cuestiones siguientes (los apartados son
independientes):

(a) Supón que cada competidor ha jugado, como mı́nimo (aun cuando puede
haber jugado más veces), una partida con alguno de los otros competi-
dores. Demuestra que siempre se pueden encontrar dos competidores que
hayan jugado el mismo número de partidas.
(b) Supón que ya se han jugado n + 1 partids en total. Demuestra que existe
un participante que ya ha jugado como mı́nimo 3 partidas.

Solución

(a) Consideramos el grafo de vértices, los participantes, y de aristas, las par-

tidas jugadas. Este grafo tiene n vértices de grado más grande o igual que
1. El grado de cada vértice puede ir de 1 hasta n − 1. Por lo tanto, hay de
haber dos vértices con el mismo número de aristas.
(b) Si se han jugado n + 1 partidas significa que |A| = n + 1. Sabemos que la
suma de grados del grafo se igual al doble de las aristas. Si nadie hubiera
jugado 3 partidas, el máximo de partidas jugados serı́an 2 por persona. En
este caso, la suma de todos los grados seria 2n, por lo tanto, sólo habrı́a n
aristas. Ası́, hay algún vértice que debe tener grado más grande de 2, es
decir, hay un jugador, como mı́nimo, que ya ha jugado 3 partidas.

117. (p2002-final11 ) ¿Cuántos grafos con estas secuencias de grados existen?

Razona tu respuesta.

(a) 7, 5, 4, 3, 2, 2, 3
(b) 7, 6, 5, 4, 4, 3, 2, 1
(c) 4, 2, 3, 3, 4, 1, 2

Solución
Fundamentos de grafos 66

(a) Ninguno, porque hay un vértice de grado 7, y el grafo tiene sólo 7 vértices.
(b) Un de único, porque el vértice de grado 7 ha de estar unido a todos los
otros, el de grado 6 a todos excepto el de grado 1 (que está unido al vértice
de grado 7), el de grado 5 a todos excepto a los de grado 1 y 2, y los de
grado 4 a todos excepto los de grado 1, 2 y 3. Por lo tanto, esta distribución
de aristas sólo se puede dar de una manera, y el grafo es este:

(c) Ninguno, porque los vértices de grado impar son impares, 3, 3 y 1 .

118. (t2002-pac32 ) Dado un número entero positivo r ∈ Z+ , consideramos

el conjunto Xr = {1, 2, · · · , 2r − 1} y el conjunto Vr formado por todos los
subconjuntos de Xr de cardinal r − 1. Definimos el grafo impar (Odd graph) Or
como el grafo que tiene por conjunto de vértices el conjunto Vr y dos vértices
de este grafo, u, v ∈ Vr , son adyacentes si los subconjuntos u y v son disjuntos.

(a) ¿Cuántos subconjuntos de cardinal r − 1 tiene Xr ?

(b) Representa gráficamente los grafos O2 y O3 . Identifica estos dos grafos.
(c) Calcula el orden y la medida del grafo Or .
(d) ¿Para qué valores de r el grafo Or es regular?

Solución
Or esta formado a partir de los subconjuntos de cardinal r − 1 de un conjunto
de cardinal 2r − 1.

(a) C(2r − 1, r − 1) = 2r−1

r−1

(b) O2 = K3 y O3 es el grafo de Petersen .

(c) El orden n = 2r−1


r−1 . Por calcular la medida, calculamos primero el grado
de cada vértice. Dado un subconjunto v ⊂ X de cardinal r − 1, existen
2r − 1 − (r −
1) = r elementos a X diferentes de los elementos de v. Ası́,
r
existirán r−1 = r subconjuntos de cardinal r − 1 disjuntos de v. Por lo
tanto, g(v) = r.
Fundamentos de grafos 67

P P
Aplicando el lema de los grados 2m = v∈Or g(v) = v∈Or r = nr y
m nr
2 .

(d) Como que cada vértice tiene grado r podemos concluir que Or es regular
para todo r.

119. (t2002-pac33 ) Denotamos por B = (bij ) la matriz de adyacencias de un

grafo G de orden n.
1
P
(a) Demuestra que 2 i,j bi,j es la medida del grafo G.

(b) Demuestra que los coeficientes de la diagonal de la matriz B 2 = B · B

coinciden con los grados de los correspondientes vértices de G.

Solución
Usaremos el hecho (ejercicio 6-91) que la suma de la fila (o de la columna)
i-ésima
P de la matriz
P B coincide con el grado gi del vértice i-ésimo, es decir,
b
k ik = gi (ó k ki = gi ).
b

(a) Aplicando el lema de los grados,

1X 1 XX 1X 1
bi,j = bi,j = gj = 2m = m
2 i,j 2 j i 2 j 2

(2)
(b) Los elementos bij de la matriz B 2 se obtienen como la suma

(2)
X
bij = bik · bkj
k

Los de la diagonal serán de la forma

(2)
X
bii = bik · bki
k

(2) P
Pero como
P que BP es una matriz simétrica, bik = bki y bii = k bik ·
2
bki = b = b ik puesto que b ik = 0 ó b ik = 1. Por lo tanto,
(2) P k ik k
bii = k bik = gi .

120. (t2004-pac31 ) Un grupo de 2n aficionado al ajedrez decide hacer una

competición. La competición tendrá dos sedes: la de Madrid que acogerá x
competidores y la de Barcelona que acogerá y competidores. En cada una de las
sedes, cada participante se enfrentará una vez a cada uno de los competidores
de su sede. ¿Cuántos competidores debe haber en cada sede para que se efectúe
el menor número de partidas posible?
Fundamentos de grafos 68

Solución
Este problema se puede modelar con el grafo G = Kx ∪ Ky. La medida de
G es m = x(x−1)+y(y−1)
2 y el orden 2n = x + y. De este modo resulta que
m = (x − n)2 + n2 − n. Ası́, pues, el mı́nimo valor de m se obtiene para x = n.
Entonces, el menor número de partidas se celebrará cuando x y y sean iguales.

121. (t2004-pac33 ) Dado un grafo G(V, A) de orden n y medida m, definimos

el grafo lı́nea de G, L(G), como el grafo que tiene por conjunto de vértices el
conjunto de aristas de G y dos vértices de L(G) son adyacentes si las correspon-
dientes aristas de G son adyacentes (tienen un vértice en común). Por ejemplo, si
G(V, A) con V = {a, b, c, d} y A = {{a, b}, {a, d}, {b, d}, {c, d}}; entonces L(G)
será el grafo con vértices V 0 = {v1 = {a, b}, v2 = {a, d}, v3 = {b, d}, v4 = {c, d}}
y aristas A0 = {{v1 , v2 }, {v1 , v3 }, {v2 , v3 }, {v3 , v4 }}.

(a) Calcula y dibuja los grafos lı́nea de los grafos siguientes: K4 , C5 , K3,3 , T5 .
(b) ¿Es cierto que si G es regular, entonces L(G) también es regular?
(c) Demuestra que si G es k-regular entonces la medida de L(G) es (k − 1)m.

Solución

(a) El gráfico siguiente muestra el grafo lı́nea:

(b) Si G es regular y cada vértice tiene grado k entonces cada arista de G es

adyacente a k − 1 + k − 1 aristas de G. Por lo tanto, cada vértice de L(G)
será adyacente a 2k − 2 vértices de L(G).
(c) Si G es k-regular entonces L(G) será 2k − 2-regular. Aplicando el lema de
los gradosa L(G):
m m
1X 1X
medida de LG) = gy = (2k − 2) = (k − 1)m
2 y=1 2 y=1

122. (t2004-pac34 ) Considera estas dos listas:

Fundamentos de grafos 69

Lista 1
1 : 2, 3
2 : 1, 3, 7, 8
3 : 1, 2, 5, 7
4 : 8, 10
5 : 3, 6, 7, 8, 9,10
6 : 5, 8, 9, 10
7 : 2, 3, 5, 9
8 : 2, 4, 5, 6, 9
9 : 5, 6, 7, 8, 10
10 : 4, 5, 7, 9

Lista 2
1 : 8
2 : 3, 4, 5, 6,,7, 8
3 : 2, 4, 5, 6, 7, 8
4 : 2, 3
5 : 2, 3, 6
6 : 2, 3, 5
7 : 2, 3, 4, 5
8 : 1, 2, 3, 4, 5, 6, 7

(a) Utilizando sólo el algoritmo de Havel -Hakimi di cuál de ellas no son listas
de adyacencias correctas.
(b) ¿Es suficiente el algoritmo de Havel -Hakimi para determinar si una lista
de adyacencias es correcta? Justifica la respuesta.

Solución

(a) La 1a lista tiene esta secuencia de grados

6, 5, 5, 4, 4, 4, 4, 4, 2, 2

Aplicamos el algoritmo de Havel-Hakimi a la 1 lista:

6,5,5,4,4,4,4,4,2,2
4,4,4,3,3,3,3,2,2
3,3,3,3,2,2,2,2
2,2,2,2,2,2,2
2,2,2,2,1,1
2,1,1,1,1
1,1,0,0
0,0,0,0

por lo tanto, la secuencia es gráfica; ahora bien, no podemos todavı́a ase-

gurar que la lista sea correcta.
Fundamentos de grafos 70

La 2 lista tiene esta secuencia de grados:

7, 6, 6, 4, 3, 3, 2, 1
Aplicamos el algoritmo de Havel-Hakimi a esta secuencia:

7, 6, 6, 4, 3, 3, 2, 1
5, 5, 3, 2, 2, 1, 0
4, 2, 1, 1, 0, 0
1, 0, 0, -1, 0

De lo cual se deduce que la lista de adyacencias no es correcta, y no

representa ningún grafo.
(b) No, porque el algoritmo no detecta si las adyacencias son correctas, sólo
detecta que el número de estas adyacencias sea correcto. Por ejemplo,
la lista 1 tiene una secuencia de grados perfectamente correcta, pero si
miramos atentamente la lista, vemos que el vértice 6 y el 10 deberán ser
adyacentes, según el listado de vértices adyacentes al vértice 6, pero al
listado de vértices adyacentes al vértice 10 no aparece el vértice 6. Por lo
tanto, esta lista 1 no es correcta, aun cuando su secuencia de grados lo
sea.

123. (t2002-final4 ) ¿Hay algún grafo con secuencia de grados 9, 9, 9, 9, 8, 6,

5, 2, 2, 2, 1, 1, 1, 1, 1? Justifica la respuesta.

Solución
Usaremos la caracterización de Havel-Hakimi para averiguar si la secuencia dada
corresponde a una secuencia gráfica:
9 9 9 9 8 6 5 2 2 2 1 1 1 1 1
8 8 8 7 5 4 1 1 1 1 1 1 1 1
7 7 6 4 3 0 0 0 1 1 1 1 1
7 7 6 4 3 1 1 1 1 1 0 0 0
6 5 3 2 0 0 0 1 1 0 0 0
6 5 3 2 1 1 0 0 0 0 0 0
4 2 1 0 0 -1 0 0 0 0 0
Vemos que aparece un valor negativo, por lo tanto, no existe ningún grafo que
tenga esta secuencia de grados.

124. (t2002-pac31 )

(a) Considera estas 2 secuencias de números enteros:

8, 7, 6, 5, 5, 3, 2, 1 7, 5, 5, 4, 4, 3, 2, 1
Di si son secuencias gráficas y justificadlo (no puedes utilizar el algoritmo
de Havel-Hakimi).
Fundamentos de grafos 71

(b) Considera estas 2 secuencias de números enteros:

7, 6, 5, 4, 4, 3, 2, 1 7, 6, 6, 4, 3, 3, 2, 1
Utiliza el algoritmo de Havel-Hakimi para justificar si son secuencias gráfi-
cas.
En los casos que sean secuencias gráficas, construye y dibuja un grafo que tenga
esta secuencia.

Solución
Todas las secuencias tienen 8 elementos, por lo tanto, habrán de representar
grafos de orden 8. La primera secuencia no puede ser de ningún grafo puesto
que el grado de cada vértice debe ser inferior a la medida (Proposición 6.6).
La segunda secuencia tampoco puede ser de un grafo puesto que contiene un
número impar de vértices de grado impar (Proposición 6.11).
Para la tercera secuencia aplicamos el algoritmo de Havel -Hakimi:
7, 6, 5, 4, 4, 3, 2, 1
5, 4, 3, 3, 2, 1, 0
3, 2, 2, 1, 0, 0
1, 1, 0, 0, 0
0, 0, 0, 0
Por lo tanto, se trata de la secuencia del grafo:

Para la cuarta secuencia aplicamos también el algoritmo de Havel-Hakimi:

7, 6, 6, 4, 3, 3, 2, 1
5, 5, 3, 2, 2, 1, 0
4, 2, 1, 1, 0, 0
1, 0, 0, -1, 0
Recorridos y conectividad 72

De lo cual se deduce que no puede ser la secuencia de grados de ningún grafo.

Capı́tulo 6

Recorridos y conectividad

125. (p99-final7 ) Demuestra que un grafo con secuencia de grados 444444444

debe ser necesariamente conexo.

Solución
Si este grafo no fuera conexo, tendrı́a varias componentes conexas. Tomamos 2
cualquiera de estas componentes conexas, G1 y G2. En cada una de estas dos
componentes, hay un vértice de orden 4, por lo tanto, deben tener, como mı́nimo
5 vértices. Por lo tanto, deberemos concluir que, como mı́nimo, el grafo tiene 10
vértices, cosa que se contradice con el enunciado.

126. (t2004-pac32 ) La tabla siguiente muestra los tipos de cambio que una
sucursal bancaria permite hacer entre varios tipos de monedas. Por ejemplo, si
rAB = 0,8 significa que para convertir la moneda A en la moneda B deberemos
multiplicar el valor de la moneda A por 0,8. Observa que si rAB = 0,8 y rBC =
0,85 entonces rAC = 0,8 × 0,85 = 0,68 será el tipo de cambio para pasar de A
1
a C si primer hacemos el cambio a la moneda B. Del mismo modo, rBA = rAB
es el tipo de cambio por pasar de la moneda B a la moneda A. Cuando una
casilla a la derecha de la diagonal está vacı́a, esto indica que la sucursal no
permite cambiar directamente entre ambas monedas. Por ejemplo, la sucursal
no permite cambiar euros y rublos directamente.
Euro $USA £ Yen $Can SFranc Rub
Euro 1 0.81 1.47 0.007
$USA 1 0.75 28.50
£ 1 0.005 0.42
Yen 1 86.36
$Can 1 21.36
SFranc 0.96 1 22.20
Rub 1
Usando la teorı́a de grafos,

(a) Dibuja el grafo que representa esta situación.

73
Recorridos y conectividad 74

(b) Justifica, usando el grafo y el algoritmo más convenientes, si es posible

hacer la conversión entre cualquiera de las 7 monedas.
(c) Calcula, usando el algoritmo adecuado, el menor número de cambios que
hace falta hacer para convertir Euros en francos suizos (SFranc).
(d) Utilizando el algoritmo de Dijkstra y modificando el grafo conveniente-
mente, justifica como calcuları́as el tipo de cambio de valor mı́nimo para
convertir Euros en Rublos.

Solución

(a) Podemos representar la conversión entre monedas como un grafo dirigido

y ponderado:

en el que solo hemos representado los arcos en un sentido. También exis-

1
tirán arcos en el otro sentido con pesos rBA = rAB .
(b) Para ver si es posible hacer la conversión entre las 7 monedas debemos
comprobar si el grafo subyacente es conexo. Aplicando el test de conexión
basado en el algoritmo DFS se puede comprobar que el grafo subyacente
es conexo y, por lo tanto, que es posible la conversión entre cualquier par
de monedas.
(c) En este caso debemos considerar el grafo dirigido anterior pero sin pesos, es
decir, no ponderado. Ahora, aplicaremos el algoritmo BFS para encontrar
el mı́nimo número de cambios. El camino mı́nimo es Euro → Yen →
SFranc, y, por lo tanto, harı́a falta hacer dos cambios.
(d) El algoritmo de Dijkstra encuentra la distancia mı́nima entre dos vértices
del grafo. Pero observa que a cada paso la distancia a un nuevo vértice se
obtiene sumando la del vértice anterior. Como que el tipo de cambio es
un producto, no es aplicable el algoritmo directamente. Una manera de
solucionar el problema es observar que

rABC = rAB · rBC ⇔ log rABC = log rAB + log rBC

Por lo tanto, podemos sustituir el peso de cada arista por su logaritmo.

Ahora ya es aplicable el algoritmo de Dijkstra y al final obtendrı́amos el
log rEuro−Rublo mı́nimo. Finalmente,

rEuro−Rublo = exp(log rEuro−Rublo )

Recorridos y conectividad 75

127. (t2004-pac43 ) Dos proyectos de conexión de siete puntos se pueden modelar

con dos grafos cuyas matrices de adyacencia son:
   
0 0 0 0 1 0 1 0 1 0 1 0 0 0
0 0 0 0 1 1 0 1 0 1 0 1 0 0
   
0 0 0 0 1 1 1 0 1 0 1 0 1 0
   
0 0 0 0 0 1 1
A= B = 1 0 1 0 0 0 0
  
1 1 1 0 0 0 0 0 1 0 0 0 1 1
   
0 1 1 1 0 0 0 0 0 1 0 1 0 1
1 0 1 1 0 0 0 0 0 0 0 1 1 0

El coste de las conexiones es, en cada caso, c(i, j) = i · j; donde la enumeración

de los vértices coincide con las filas y columnas de la respectiva matriz de ady-
acencia.

(a) Determina si los grafos de las dos propuestas son isomorfos.

(b) Si se quiere escoger el proyecto que tenga el diámetro mı́nimo, ¿cuál de los
dos se deberá escoger? Di qué algoritmo se ha de utilizar para encontrarlo
y da la tabla o la matriz resultante de este algoritmo. Puedes usar el applet
de apoyo que tenéis para la asignatura.
(c) Si, en cambio, se quisiera eliminar de cada proyecto aquellas conexiones
que no son imprescindibles para mantener la conexión entre todos los
puntos, ¿qué proyecto escogerı́as?

Solución

(a) Aun cuando tienen la misma secuencia de grados, no son isomorfos; ası́, el
primero es bipartido y el segundo no lo es: por ejemplo, este último tiene
el ciclo 567. Estos son los grafos:

(b) Se tendrı́a que utilizar, por ejemplo, el algoritmo de Floyd, que nos da el
camino mı́nimo entre todos los pares de vértices de un grafo; el valor más
grande será el diámetro del grafo. En nuestro caso, la matriz final en cada
Recorridos y conectividad 76

caso es:
   
0 15 20 35 5 27 7 0 2 8 4 12 26 47
15 0 25 36 10 12 22 2 0 6 6 10 24 45
   
20 25 0 42 15 18 21 8 6 0 12 16 18 51
   
35
FA =  36 42 0  B 4
40 24 28 F = 6 12 0 16 30 51


5 10 15 40 0 22 12 12 10 16 16 0 30 35
   
27 12 18 24 22 0 34 26 24 18 30 30 0 42
7 22 21 28 12 34 0 47 45 51 51 35 42 0

Se puede comprobar como en el primer caso el máximo es 42, mientras que

en el segundo caso, el máximo es 51. Por lo tanto, los diámetros son 42 y
51, respectivamente. Ası́, pues, debemos escoger el primer proyecto. Estas
matrices se pueden encontrar, también, utilizando el JavApplet, aplicando
el algoritmo Dijkstra para cada uno de los vértices de los grafos, y ası́ nos
evitamos la carga de aplicar el algoritmo de Floyd.

(c) En este caso, hace falta aplicar, por ejemplo, el algoritmo de Kruskal a
cada uno de los grafos. Para el grafo A, el algoritmo de Kruskal da un
peso de 73, mientras que por el grafo B, el algoritmo da un peso de 75. En
este caso, pues, también se debe escoger el primer proyecto, y las aristas
escogidas son (1, 5), (1, 7), (2, 5), (2, 6), (3, 5) y (4, 6)

128. (t99-pac25 ) Utilizando el algoritmo BFS, encuentra un árbol generador

de este grafo:

Solución
El vértice inicial es 1
Recorridos y conectividad 77

Cola Vértice Vértice Arista Aristas Vértices

añadido eliminado añadida
1 1 ∅ 1
12 2 12 12 1,2
125 5 15 12,15 1,2,5
1256 6 16 12,15,16 1,2,5,6
256 1 12,15,16 1,2,5,6
2563 3 23 12,15,16,23 1,2,5,6,3
25637 7 27 12,15,16,23,27 1,2,5,6,3,7
5637 2 12,15,16,23,27 1,2,5,6,3,7
56374 4 54 12,15,16,23,27,54 1,2,5,6,3,7,4
5637410 10 510 12,15,16,23,27,54,510 1,2,5,6,3,7,4,10
637410 5 12,15,16,23,27,54,510 1,2,5,6,3,7,4,10
6374108 8 68 12,15,16,23,27,54,510,68 1,2,5,6,3,7,4,10,8
63741089 9 69 12,15,16,23,27,54,510,68,69 1,2,5,6,3,7,4,10,8,9
3741089 6 12,15,16,23,27,54,510,68,69 1,2,5,6,3,7,4,10,8,9
741089 3 12,15,16,23,27,54,510,68,69 1,2,5,6,3,7,4,10,8,9
41089 7 12,15,16,23,27,54,510,68,69 1,2,5,6,3,7,4,10,8,9
1089 4 12,15,16,23,27,54,510,68,69 1,2,5,6,3,7,4,10,8,9
89 10 12,15,16,23,27,54,510,68,69 1,2,5,6,3,7,4,10,8,9
9 8 12,15,16,23,27,54,510,68,69 1,2,5,6,3,7,4,10,8,9
∅ 9 12,15,16,23,27,54,510,68,69 1,2,5,6,3,7,4,10,8,9

Este es el árbol generador:

129. (t2000-pac22 ) La tabla siguiente representa la matriz de adyacencia de un

grafo con pesos positivos en las aristas:

0 5 6 4 3 7
5 0 2 4 8 5
6 2 0 4 8 8
4 4 4 0 2 5
3 8 8 2 0 4
7 5 8 5 4 0

Utilizando el algoritmo DFS, encuentra un árbol generador de este grafo. Haz

Recorridos y conectividad 78

la tabla (donde se vea el contenido de la pila) que registra el funcionamiento del

algoritmo.
El árbol generador obtenido con este algoritmo ¿es un árbol generador minimal?

Solución
La tabla siguiente muestra el algoritmo DFS:

Pila Vértice Añadido Vértice eliminado Arista añadida

1 1 - -
12 2 - 12 (5)
123 3 - 23 (2)
1234 4 - 34 (4)
12345 5 - 45 (2)
123456 6 - 56 (4)
12345 - 6 -
1234 - 5 -
123 - 4 -
12 - 3 -
1 - 2 -
∅ - 1 -

El peso total de este árbol es 17. Pero, si aplicamos el algoritmo de Kruskal:

(2, 3), (4, 5), (1, 5), (2, 4), (5, 6)

obtenemos un árbol generador minimal de peso 15. Por lo tanto, el árbol obtenido
con el algoritmo DFS no es minimal.

130. (t2000-pac23 ) Dado el grafo dirigido (dı́grafo) y ponderado de la figura

usa el algoritmo de Dijkstra para encontrar la distancia mı́nima del vértice 1

al resto de vértices. A cada paso i usa una tabla como la que mostramos para
indicar los estados del algoritmo (esta tabla representa el estado inicial):

vértices 1 2 3 4 5 6 7
Vi 1 0 0 0 0 0 0
E() 0 ∞ ∞ ∞ ∞ ∞ ∞

Solución
Tablas que se obtienen:
Recorridos y conectividad 79

vértices 1 2 3 4 5 6 7
i=0 Vi 1 0 0 0 0 0 0
E() 0 ∞ ∞ ∞ ∞ ∞ ∞
vértices 1 2 3 4 5 6 7
i=1 Vi 1 0 0 1 0 0 0
E() 0 2 ∞ 1 ∞ ∞ ∞
vértices 1 2 3 4 5 6 7
i=2 Vi 1 1 0 1 0 0 0
E() 0 2 3 1 3 9 5
vértices 1 2 3 4 5 6 7
i=3 Vi 1 1 0 1 1 0 0
E() 0 2 3 1 3 9 5
vértices 1 2 3 4 5 6 7
i=4 Vi 1 1 1 1 1 0 0
E() 0 2 3 1 3 9 5
vértices 1 2 3 4 5 6 7
i=5 Vi 1 1 1 1 1 0 1
E() 0 2 3 1 3 8 5
vértices 1 2 3 4 5 6 7
i=6 Vi 1 1 1 1 1 1 1
E() 0 2 3 1 3 6 5

131. (t2001-pac32 ) Un gran número de personas vuelan atravesar la frontera

entre una localidad C0 y otra C8 . Las posibles rutas están representadas por la
tabla siguiente:

0 1 2 3 4 5 6 7 8
0 0 4 6 8 0 0 0 0 0
1 4 0 2 0 2 0 0 0 0
2 6 2 0 3 5 7 0 0 0
3 8 0 3 0 0 0 0 0 0
4 0 2 5 0 0 0 4 8 0
5 0 0 7 0 0 0 3 0 7
6 0 0 0 0 4 3 0 0 6
7 0 0 0 0 8 0 0 0 4
8 0 0 0 0 0 7 6 4 0

donde el valor de la posición (i, j) representa la distancia entre la ciudad Ci y

la ciudad Cj . Usando la teorı́a de grafos,

(a) Dibuja el grafo ponderado.

(b) Encuentra la distancia mı́nima entre la ciudad C0 y la ciudad C8 . Haz una
tabla que muestre el algoritmo utilizado.
(c) Encuentra a partir de la tabla el camino que habrán de seguir las personas.
Recorridos y conectividad 80

(d) Si en el algoritmo modificamos la condición

si (E(ui ) + ω(ui , v)) < E(v) entonces . . .

por
si (E(ui ) + ω(ui , v)) ≤ E(v) entonces . . .
¿qué cambios obtendrı́amos en la solución del problema?

Solución
El gráfico siguiente muestra el grafo:

(a) Aplicamos el algoritmo de Dijkstra con vértice inicial C0 y obtenemos la

tabla siguiente:

0 1 2 3 4 5 6 7 8
(0,0) (∞,0) (∞,0) (∞,0) (∞,0) (∞,0) (∞,0) (∞,0) (∞,0)
(0,0) (4,0) (6,0) (8,0) (∞,0) (∞,0) (∞,0) (∞,0) (∞,0)
(0,0) (4,0) (6,0) (8,0) (6,1) (∞,0) (∞,0) (∞,0) (∞,0)
(0,0) (4,0) (6,0) (8,0) (6,1) (13,2) (∞,0) (∞,0) (∞,0)
(0,0) (4,0) (6,0) (8,0) (6,1) (13,2) (10,4) (14,4) (∞,0)
(0,0) (4,0) (6,0) (8,0) (6,1) (13,2) (10,4) (14,4) (∞,0)
(0,0) (4,0) (6,0) (8,0) (6,1) (13,2) (10,4) (14,4) (16,6)
(0,0) (4,0) (6,0) (8,0) (6,1) (13,2) (10,4) (14,4) (16,6)
(0,0) (4,0) (6,0) (8,0) (6,1) (13,2) (10,4) (14,4) (16,6)

De esta tabla se deduce que la distancia mı́nima de C0 a C8 es 16.

(b) A partir de la última fila de la tabla podemos reconstruir el camino: A C8
se llega desde C6 , a C6 desde C4 , a C4 desde C1 y a C1 desde C0 . Ası́ el
camino mı́nimo es: C0 → C1 → C4 → C6 → C8 .

(c) La distancia mı́nima será la misma pero el camino puede ser diferente
puesto que puede haber más de una manera de lograr la distancia mı́nima.

132. (t2001-final3 ) Una empresa suiza de aviación amplió el verano pasado su

negocio, abriendo vuelos diarios entre 6 ciudades. Esta tabla da las distancias
Recorridos y conectividad 81

entre estas 6 ciudades:

Berlı́n Dublı́n Helsinki Ginebra Praga Palermo
Berlı́n − 1530 1430 1139 348 2533
Dublı́n 1530 − 2665 1570 1819 3440
Helsinki 1430 2665 − 2381 1739 4007
Ginebra 1139 1570 2381 − 948 1990
Praga 348 1819 1739 948 − 2294
Palermo 2533 3440 4007 1990 2294 −

(a) Por motivos meteorológicos, hoy estas lı́neas no despegarán, ni en un

sentido ni en el otro: Praga/Dublı́n, Praga/Ginebra, Palermo/Helsinki,
Palermo/Ginebra, Berlı́n/Dublı́n y Berlı́n/Helsinki. Utiliza alguno de los
algoritmos que conoces por encontrar la manera de ir de Dublı́n en Praga
recorriendo la mı́nima distancia posible.
(b) Debido a una crisis de la empresa, el mes próximo cerrará algunas de
las lı́neas. ¿Cuáles son las lı́neas que habrı́a de utilizar para mantener
conectadas todas estas ciudades con el mı́nimo de lı́neas posible, de forma
que los desplazamientos sean el más cortos posible? (Utiliza el algoritmo
de Prim)

Solución

(a) Utilizamos el algoritmo de Dijkstra:

B D H G Pr P
∞ (0, D) (2665, D) (1570, D) ∞ (3440, D)
(2709, G) (0, D) (2665, D) (1570, D) ∞ (3440, D)
(2709, G) (0, D) (2665, D) (1570, D) (4404, H) (3440, D)
(2709, G) (0, D) (2665, D) (1570, D) (3057, B) (3440, D)

Por lo tanto, el camino es Dublı́n/Ginebra/Berlı́n/Praga.

B D H G Pr P
(348,Pr) (1819,Pr) (1739,Pr) (948,Pr) (0,Pr)* (2294,Pr)
(348,Pr)* (1530,B) (1430,B) (948,Pr) (0,Pr) (2294,Pr)
(b) (348,Pr) (1530,B) (1430,B) (948,Pr)* (0,Pr) (1990,G)
(348,Pr) (1530,B) (1430,B)* (948,Pr) (0,Pr) (1990,G)
(348,Pr) (1530,B)* (1430,B) (948,Pr) (0,Pr) (1990,G)
(348,Pr) (1530,B) (1430,B) (948,Pr) (0,Pr) (1990,G)*
Por lo tanto, el árbol resultante es:
Recorridos y conectividad 82

133. (t2001-final11 ) Dado este grafo ponderado:

(a) Encuentra el camino más corto de A a G utilizando el algoritmo de Dijkstra

e indicando todos los pasos que haces.
(b) ¿Es único este camino?

Solución

(a)

A B C D E F G
(0, A) (30, A) (50, A) ∞ ∞ ∞ ∞
(0, A) (30, A) (49, B) (36, B) (70, B) ∞ ∞
(0, A) (30, A) (49, B) (36, B) (70, B) (59, D) ∞
(0, A) (30, A) (49, B) (36, B) (70, B) (59, D) ∞
(0, A) (30, A) (49, B) (36, B) (70, B) (59, D) (79, F )
(0, A) (30, A) (49, B) (36, B) (70, B) (59, D) (78, E)

por lo tanto, el camino es ABEG.

Recorridos y conectividad 83

(b) El camino ABDFEG también une A y G con el mı́nimo peso.

134. (p2002-pac34 ) Dado este grafo ponderado incompleto:

Observa este inicio de una tabla de un algoritmo:

A B C D E F G H
(0,A) (∞,A) (∞,A) (∞,A) (∞,A) (∞,A) (∞,A) (∞,A)
(0,A)∗ (60,A) (50,A) (∞,A) (90,A) (∞,A) (∞,A) (130,A)
(0,A) (60,A) (50,A)∗ (∞,A) (90,A) (∞,A) (80,A) (130,A)

(a) Completa los pesos del grafo anterior.

(b) ¿De qué algoritmo se trata? ¿Qué hace este algoritmo?
(c) Ésta es la tabla completa del algoritmo anterior:
A B C D E F G H
(0,A) (∞,A) (∞,A) (∞,A) (∞,A) (∞,A) (∞,A) (∞,A)
(0,A)∗ (60,A) (50,A) (∞,A) (90,A) (∞,A) (∞,A) (130,A)
(0,A) (60,A) (50,A)∗ (∞,A) (90,A) (∞,A) (80,C) (130,A)
(0,A) (60,A)∗ (50,A) (70,B) (90,A) (∞,A) (80,C) (130,A)
(0,A) (60,A) (50,A) (70,B)∗ (80,D) (150,C) (80,C) (130,A)
(0,A) (60,A) (50,A) (70,B) (80,D)∗ (150,C) (80,C) (130,A)
(0,A) (60,A) (50,A) (70,B) (80,D) (130,G) (80,C)∗ (130,A)
(0,A) (60,A) (50,A) (70,B) (80,D) (130,G)∗ (80,C) (130,A)
(0,A) (60,A) (50,A) (70,B) (80,D) (130,G) (80,C) (130,A)∗
Encuentra los errores, explı́calos y corrı́gelos.

Solución

(a)
Recorridos y conectividad 84

(b) El algoritmo de Dijkstra, porque sólo puede tratarse de la tabla de la

algoritmo de Dijkstra o de la de Prim. En la tercera fila, bajo la G, pone
(80,C). Si fuera el algoritmo de Prim deberı́a poner (30,C), porque 30 es
el peso de la arista CG. Por lo tanto, se trata del algoritmo de Dijkstra .
El algoritmo de Dijkstra encuentra la distancia mı́nima de cualquier vértice
al vértice A.
(c) La tabla correcta serı́a esta :
A B C D E F G H
(0,A) (∞,A) (∞,A) (∞,A) (∞,A) (∞,A) (∞,A) (∞,A)
(0,A)∗ (60,A) (50,A) (∞,A) (90,A) (∞,A) (∞,A) (130,A)
(0,A) (60,A) (50,A)∗ (∞,A) (90,A) (∞,A) (80,C) (130,A)
(0,A) (60,A)∗ (50,A) (70,B) (90,A) (∞,A) (80,C) (130,A)
(0,A) (60,A) (50,A) (70,B)∗ (80,D) (150,D) (80,C) (100,D)
(0,A) (60,A) (50,A) (70,B) (80,D)∗ (150,D) (80,C) (100,D)
(0,A) (60,A) (50,A) (70,B) (80,D) (130,G) (80,C)∗ (100,D)
(0,A) (60,A) (50,A) (70,B) (80,D) (130,G) (80,C) (100,D)∗
(0,A) (60,A) (50,A) (70,B) (80,D) (130,G)∗ (80,C) (100,D)
En la quinta fila, cuando accedemos al vértice D, la distancia de A a H
pasando por B y D es 100, menor que 130; por lo tanto, se debe cambiar,
(130,H) por (100,D). También, el (150,C) de la columna F se ha de susti-
tuir por (150,D) puesto que por llegar a F debemos pasar por D. Estos
errores se propagan y, por ello, en las dos últimas filas de la tabla, se debe
intercambiar el orden en que se escogen los vértices.

135. (p2002-final12 ) La tabla siguiente muestra el coste de volar entre varias

ciudades según la tabla oficial de precios de una lı́nea aérea:
Recorridos y conectividad 85

A B C D E F G
A 0 2 5 - - - -
B 0 3 1 - - -
C 0 2 2 - -
D 0 4 2 -
E 0 2 3
F 0 5
G 0

Se debe suponer que la tabla es simétrica y que el sı́mbolo - entre dos ciudades
significa que no hay conexión directa.

(a) Explica el algoritmo que utilizarı́as para buscar la ruta más económica por
volar de la ciudad A a el resto de ciudades. Muestra la tabla de evolución
del algoritmo. ¿Cuál será el coste mı́nimo por ir de la ciudad A a la ciudad
G? Di, también, cuál es la ruta que logra este mı́nimo.
(b) La ruta calculada en el apartado anterior, aunque óptima por el que hace
referencia al coste total, no tiene porque ser la que logre el mı́nimo número
de interconexiones (en cada interconexión hace falta hacer un aterrizaje
y un despegue). Explica como modificarı́as el algoritmo para que permita
calcular la ruta de coste mı́nimo con el mı́nimo número de interconexiones.
Muestra ahora la tabla resultante y cuál serı́a la nueva ruta.

Solución

(a) Aplicarı́amos el algoritmo de Dijkstra sobre el grafo:

La tabla de evolución del algoritmo será:

A B C D E F G
(0,A) (∞,A) (∞,A) (∞,A) (∞,A) (∞,A) (∞,A)
(0,A)∗ (2,A) (5,A) (∞,A) (∞,A) (∞,A) (∞,A)
(0,A) (2,A)∗ (5,A) (3,B) (∞,A) (∞,A) (∞,A)
(0,A) (2,A) (5,A) (3,B)∗ (7,D) (5,D) (∞,A)
(0,A) (2,A) (5,A)∗ (3,B) (7,D) (5,D) (∞,A)
(0,A) (2,A) (5,A) (3,B) (7,D) (5,D)∗ (10,F)
(0,A) (2,A) (5,A) (3,B) (7,D)∗ (5,D) (10,F)
(0,A) (2,A) (5,A) (3,B) (7,D) (5,D) (10,F)∗
De esta tabla se deduce que el coste total mı́nimo será 10 y que la ruta
óptima calculada será: A, B, D, F, G.
Recorridos y conectividad 86

(b) Si queremos minimizar el número de interconexiones habremos de tener-

lo en cuenta en el algoritmo y etiquetar cada vértice u con tres valores
(E(u), Y (u), v) siendo E(u) es el coste acumulado por llegar al vértice u,
Y (u) es el número de interconexiones por llegar al mismo vértice y v es el
vértice del cual provenimos.
Además, hará falta seleccionar a cada paso del algoritmo aquel vértice con
mı́nimo E(u) y, si hay igualdad, el de mı́nimo Y (u). Lo mismo habremos
de hacer al mismo tiempo que se actualizan las etiquetas.
La tabla resultante será:
A B C D E F G
(0,0,A) (∞,∞,A) (∞,∞,A) (∞,∞,A) (∞,∞,A) (∞,∞,A) (∞,∞,A)
(0,0,A)∗ (2,1,A) (5,1,A) (∞,∞,A) (∞,∞,A) (∞,∞,A) (∞,∞,A)
(0,0,A) (2,1,A)∗ (5,1,A) (3,2,B) (∞,∞,A) (∞,∞,A) (∞,∞,A)
(0,0,A) (2,1,A) (5,1,A) (3,2,B)∗ (7,3,D) (5,3,D) (∞,∞,A)
(0,0,A) (2,1,A) (5,1,A)∗ (3,2,B) (7,2,C) (5,3,D) (∞,∞,A)
(0,0,A) (2,1,A) (5,1,A) (3,2,B) (7,2,C) (5,3,D)∗ (10,4,F)
(0,0,A) (2,1,A) (5,1,A) (3,2,B) (7,2,C)∗ (5,3,D) (10,3,E)
(0,0,A) (2,1,A) (5,1,A) (3,2,B) (7,2,C) (5,3,D) (10,3,E)∗
De esta tabla se deduce que la ruta óptima es: A, C, E, G.

136. (t2002-final8 ) La tabla siguiente:

s v2 v3 v4 v5 v6 v7
(0, s) (10, s) (6, s) (1, v2 ) (30, v6 ) (15, v7 )∗ (14, v2 )

representa una de las filas (no necesariamente la última) de la tabla que se

obtiene tras aplicar el algoritmo de Dijkstra sobre el grafo G con vértice inicial
s.
A partir de estos valores, justifica si son ciertas o falsas las afirmaciones sigu-
ientes:

(a) El camino de peso mı́nimo de s a v6 tiene peso 15 .

(b) El camino de peso mı́nimo de s a v6 debe pasar por v2 .
(c) El camino de peso mı́nimo de s a v5 debe pasar por v2 .
(d) Hay un camino de s a v5 que tiene peso 30.

Solución
En el algoritmo de Dijkstra, a cada paso se fija la distancia de uno de los vértices
del grafo.

(a) Cierta. En esta fila hemos fijado la etiqueta del vértice v6 que ya no se
modificará. Por lo tanto, esta etiqueta nos dará el valores del peso del
camino mı́nimo de s a v6 .
(b) Cierta. La etiqueta de v6 nos dice que el camino de peso mı́nimo de s a
v6 pasa por v7 , y la etiqueta de v7 nos dice que también pasa por v2 .
Recorridos y conectividad 87

(c) Falsa. Como que no sabemos si esta fila es la última de la tabla, no podemos
afirmar que el camino de peso mı́nimo de s a v5 pase por v2 .
(d) Cierta. Como que la etiqueta de v5 es menor que ∞ podemos asegurar
que hay un camino de peso 30 entre s y v5 .

137. (t2002-pac34 ) La tabla siguiente representa las distancias entre varias

gasolineras que pertenecen a una compañı́a de distribución de carburantes:
1 2 3 4 5 6 7
1 2 4 1
2 2 3 10
3 4 2 5
4 1 3 2 2 8 4
5 10 2 6
6 5 8 1
7 4 6 1
Además, las gasolineras están interconectadas por una red de computadores
con las conexiones determinadas por la tabla anterior, es decir, la gasolinera 1
está conectada con la 2, 3, 4; la 2 con la 1, 4, 5;... Di a qué variante del camino
mı́nimo pertenece cada uno de los siguientes problemas y resuélvelo (tienes que
utilizar el algoritmo adecuado por resolver cada problema y mostrar en una
tabla los pasos del algoritmo aplicado):

(a) Cálculo de las distancias mı́nimas entre el centro de distribución (situado

a la gasolinera 1) y el resto de gasolineras.
(b) Búsqueda del número mı́nimo de nodos de interconexión que separan cada
gasolinera del centro de distribución.
(c) Búsqueda de las gasolineras que están más alejadas entre sı́.

Solución
La tabla de distancias es la tabla de pesos de un grafo ponderado de orden 7.

(a) Es el problema del camino mı́nimo desde un vértice inicial en un grafo pon-
derado. Para calcular la distancia mı́nima entre la gasolinera 1 y el resto
de gasolineras utilizaremos el algoritmo de Dijkstra. La tabla siguiente
resume los pasos del algoritmo:
1 2 3 4 5 6 7
(0, 1) (∞, 1) (∞, 1) (∞, 1) (∞, 1) (∞, 1) (∞, 1)
(0, 1)∗ (2, 1) (4, 1) (1, 1) (∞, 1) (∞, 1) (∞, 1)
(0, 1) (2, 1) (3, 4) (1, 1)∗ (3, 4) (9, 4) (5, 4)
(0, 1) (2, 1)∗ (3, 4) (1, 1) (3, 4) (9, 4) (5, 4)
(0, 1) (2, 1) (3, 4)∗ (1, 1) (3, 4) (8, 3) (5, 4)
(0, 1) (2, 1) (3, 4) (1, 1) (3, 4)∗ (8, 3) (5, 4)
(0, 1) (2, 1) (3, 4) (1, 1) (3, 4) (6, 7) (5, 4)∗
(0, 1) (2, 1) (3, 4) (1, 1) (3, 4) (6, 7)∗ (5, 4)
Árboles 88

La última lı́nea muestra las distancias desde la gasolinera 1 al resto.

(b) En el segundo caso, es un problema de camino mı́nimo hasta un vértice
destino en un grafo no ponderado. Como el grafo no es dirigido entonces
será suficiente calcular la distancia desde el vértice 1 al resto de vértices
en un grafo no ponderado. Utilizaremos el algoritmo BFS.
La tabla siguiente resume los pasos del algoritmo:
Q Vértice añadido Vértice eliminado dist
1 1 - [0, ∞, ∞, ∞, ∞, ∞, ∞]
12 2 - [0, 1, ∞, ∞, ∞, ∞, ∞]
123 3 - [0, 1, 1, ∞, ∞, ∞, ∞]
1234 4 - [0, 1, 1, 1, ∞, ∞, ∞]
234 - 1 [0, 1, 1, 1, ∞, ∞, ∞]
2345 5 - [0, 1, 1, 1, 2, ∞, ∞]
345 - 2 [0, 1, 1, 1, 2, ∞, ∞]
3456 6 - [0, 1, 1, 1, 2, 2, ∞]
456 - 3 [0, 1, 1, 1, 2, 2, ∞]
4567 7 - [0, 1, 1, 1, 2, 2, 2]
567 - 4 [0, 1, 1, 1, 2, 2, 2]
67 - 5 [0, 1, 1, 1, 2, 2, 2]
7 - 6 [0, 1, 1, 1, 2, 2, 2]
∅ - 7 [0, 1, 1, 1, 2, 2, 2]
De esta última lı́nea deducimos que las gasolineras 2,3 y 4 están directa-
mente conectadas a la central y que las gasolineras 5, 6 y 7 tienen un nodo
que las separa de la gasolinera 1.
(c) Finalmente, necesitamos calcular el diámetro del grafo. Podemos utilizar el
algoritmo del ejercicio 6-71 basado en el algoritmo de Floyd. Por lo tanto,
es un problema del camino mı́nimo entre todas las parejas de vértices en
un grafo ponderado.
Mostramos sólo las tablas iniciales y finales del algoritmo de Floyd:
   
∞ 2 4 1 ∞ ∞ ∞ 0 2 3 1 3 6 5
 2 ∞ ∞ 3 10 ∞ ∞   2 0 5 3 5 8 7 
   
 4 ∞ ∞ 2 ∞ 5 ∞   3 5 0 2 4 5 6 
   
d0 = 
 1 3 2 ∞ 2 8 4  d 7
=  1 3 2 0 2
 5 4 

 ∞ 10 ∞ 2 ∞ ∞ 6   3 5 4 2 0 7 6 
   
 ∞ ∞ 5 8 ∞ ∞ 1   6 8 5 5 7 0 1 
∞ ∞ ∞ 4 6 1 ∞ 5 7 6 4 6 1 0

De esta tabla se desprende que las gasolineras más alejadas son la 2 y la

6 que están a una distancia de 8.
Capı́tulo 7

Árboles

138. (p99-pac22 ) ¿Cuál es el número de vértices de un árbol que tiene 3 vértices

de grado 2, 2 vértices de grado 3, 1 vértice de grado 4 y el resto de grado 1?

Solución
Suponemos que este árbol tiene n vértices. Por lo tanto, el número de aristas
es n − 1. También sabemos que la suma de los grados de los vértices es igual al
doble de las aristas. Por lo tanto, la suma de los grados es 10 + n. O sea:
10 + n = 2(n − 1)
resolvemos esta ecuación y n = 12. Es un grafo de 12 vértices.

139. (p99-final5 ) ¿Cuál es el valor de la suma de los grados de los vértices de

un árbol de orden n? ¿Cuál es el número de vértices de un árbol que tiene 13
vértices de grado 2, 12 vértices de grado 3, 10 vértices de grado 4 y el resto de
grado 1?

Solución
Es sabido que la suma de los grados de los vértices de un árbol es el doble del de
las aristas. Ahora bien, las aristas, en este caso, son n − 1. Por lo tanto, la suma
de grados es igual a 2(n − 1). Por la fórmula anterior, 13 · 2 + 12 · 3 + 10 · 4 + n =
2(13 + 12 + 10 + n − 1), siendo n el número de vértices de grado 1. Resolviendo
esta ecuación, n = 34. Por lo tanto, el número de vértices de este árbol es 69.

140. (t99-pac23 ) Halla todos los árboles que tienen 1 vértice de grado 3, 3
vértices de grado 2 y el resto de vértices, de grado 1.

Solución
Según la relación entre los grados de los vértices y el número de aristas, se debe
cumplir que: 1 × 3 + 3 × 2 + n = 2(1 + 3 + n − 1) Por lo tanto, el árbol tiene 3

89
Árboles 90

hojas. Además, el grafo tiene 7 vértices.

Supongamos que el vértice de grado 3 es adyacente a los 3 vértices de grado 2;
este es el único árbol con estas caracterı́sticas:

Suponemos que 2 vértices de grado 2 son adyacentes al vértice de grado 3:

Suponemos que sólo 1 de los vértices de grado 2 es adyacente al de grado 3:

Cualquiera otra disposición de vértices y aristas es isomorfa a una de éstas. Por

lo tanto, esencialmente, hay 3 posibles árboles de estas caracterı́sticas.

141. (t99-final5 ) José Colmillo, un antiguo noble de la estirpe de los Colmillo

de Ripoll tuvo 4 hijos, 10 de sus descendentes tuvieron 3 hijos cada uno y
15 tuvieron 2. El resto de descendientes murieron sin descendencia. ¿Cuántos
descendentes tuvo José?

Solución
Esta situación (los descendientes de diferentes generaciones de en José Colmillo)
se puede modelizar con un árbol. Este árbol tiene 1 vértice de grado 4 (la raı́z),
10 vértices de grado 4 (los que corresponden a los nodos que tienen tres hijos) y
15 vértices de grado 3. El resto de vértices, n, tienen grado 1. Es puede aplicar la
conocida fórmula, que asegura que la suma de grados es el doble del número de
vértices menos 1: 89 + n = 2(26 + n − 1). En definitiva, n = 39. En José Colmillo
tuvo 39 descendentes que murieron sin descendencia.

142. (t2000-final4 ) Justifica si es cierta o falsa la siguiente afirmación: Un

bosque con k árboles y n vértices tiene n − k + 1 aristas.

Solución
Árboles 91

P
Sean n1 , . . . , nk, ni = n los órdenes de los k árboles del bosque. Y m1 , . . . , mk ,
P
mi = |A| las medidas de cada árbol. Entonces,
X X X
|A| = mi = (ni − 1) = ni − k = n − k

Por lo tanto, la afirmación es falsa.

143. (t2000-final10 ) Justifica si es cierta o falsa la siguiente afirmación: Un

árbol de n vértices en el cual la mitad de los vértices son hojas debe tener un
mı́nimo de 4 vértices.

Solución
Llamemos F al conjunto de hojas. Aplicando el lema de los grados,
X X X
2(n − 1) = g(v) + g(v) = |F | + g(v)
v∈F v6∈F v6∈F
3n
≥ |F | + 2(n − |F |) =
2

De aquı́, n ≥ 4.

144. (t2000-final16 ) Justifica si es cierta o falsa la siguiente afirmación: si un

grafo es conexo y tiene la secuencia de grados 1, 1, 1, 3, 3, 3 entonces contiene un
circuito.

Solución
Si G es conexo y no contiene ningún circuito entonces es un árbol. Pero, G
contiene 6 vértices y 12/2 = 6 aristas. Ası́ no puede ser un árbol y, por lo tanto,
contiene un circuito.

145. (t2001-final4 ) Justifica si son ciertas o falsas las afirmaciones siguientes:

(a) Si un grafo G no tiene ciclos entonces todo subgrafo de G tampoco tiene

ciclos.
(b) Si un grafo es conexo y tiene la secuencia de grados 1, 1, 1, 3, 3, 3 entonces
contiene un ciclo.

Solución

(a) Cierto. Si un subgrafo de G tuviera un ciclo entonces este mismo ciclo

también lo seria de G.
Árboles 92

(b) Cierto. Un grafo conexo sin ciclos debe ser un árbol. Este grafo tiene 6
vértices y, por el lema de los grados, 6 aristas. Entonces no puede ser un
árbol.

146. (t2001-final8 ) Di si son ciertas o falsas las afirmaciones siguientes. Justifica

tus respuestas:

(a) Un árbol con un mı́nimo de 2 vértices tiene un mı́nimo de 2 vértices que

no son articulación.
(b) Hay árboles de grado superior a 2 que son regulares.
(c) Un bosque con k árboles y n vértices tiene n − k + 1 aristas.
(d) Un árbol puede tener esta secuencia de grados 2,3,1,1,2,1,2,2,4.

Solución

(a) Cierto. Un árbol con un mı́nimo de 2 vértices tiene un mı́nimo de 2 hojas

que no son articulaciones.
(b) Falso. Si un árbol tiene más de dos vértices entonces tendrá un mı́nimo de
dos hojas que tienen grado 1. Ası́ los únicos árboles regulares son el grafo
trivial y el grafo trayecto de orden 2.
(c) Falso. Si denotamos por n1 , . . . , nk los órdenes de los k árboles, entonces
podemos contar el número total de aristas
n1 − 1 + · · · + nk − 1 = n1 + · · · + nk − k = n − k

(d) Falso. Aplicando el lema de los grados

1
|A| = (2 + 3 + 1 + 1 + 2 + 1 + 2 + 2 + 4) = 9
2
que es igual al número de vértices del grafo. Por lo tanto no puede corre-
sponder a un árbol.

147. (t2002-final7 ) Si G(V, A) es un bosque con 28 vértices y 21 aristas,

¿cuántos componentes conexos tiene? Justifica la respuesta.

Solución
Si G(V, A) es un bosque, sabemos que todos sus componentes son árboles. Para
cada uno de estos árboles Gi (Vi , Ai ) se cumple que |Ai | = |Vi | − 1. Ası́, con-
siderando todo el bosque en conjunto, y suponiendo que hay k componentes,
k
X k
X
|A| = |Ai | = (|Vi | − 1) = |V | − k
i=1 i =1
Árboles 93

Sustituyendo los valores del enunciado en esta expresión

21 = 28 − k ⇒ k = 7 componentes.

148. (t2002-final3 ) Dibuja el árbol, con raı́z, de la siguiente expresión ar-

itmética: (2x + y)(5a − b)ˆ3. Usa el árbol por encontrar la representación de la
expresión en notación prefija, en notación infija y en notación postfija.

Solución

∗
PPP
 PP


)  P PP
q
P
+ ˆ
Q Q
Q  Q
Q  Q
Q
s
Q 

+ Qs
Q
∗ y − 3
@ @
@ @
@ @
@R
@ @
R
@
2 x ∗ b
@
@
@
@
R
@
5 a
La representación prefija es el recorrido en preorden del árbol: ∗ + ∗ 2 x y ˆ −
∗5ab3
La representación infija es el recorrido en inorden del árbol: 2 ∗ x + y ∗ 5 ∗
a − bˆ3
La representación postfija es el recorrido en postorden del árbol: 2 x ∗ y +
5 a ∗ b − 3ˆ∗

149. (p2000-pac22 ) Utiliza el algoritmo de Kruskal para encontrar un árbol

generador minimal del siguiente grafo:
Árboles 94

Indica el orden en el que vamos cogiendo las aristas en cada paso del algoritmo
y da el peso del árbol construido.

Solución
Empezamos por inicializar la variable k := 1 y el conjunto de aristas Ak − 1 =
∅.
El resto de pasos del algoritmo vienen dados por:
A1 = {A}, k=2
A2 = {A, D}, k=3
A3 = {A, D, Y }, k=4
A4 = {A, D, Y, F }, k=5
A5 = {A, D, Y, F, C}, k=6
A6 = {A, D, Y, F, C, H}, k=7
El árbol generador de peso mı́nimo está formato por las aristas A6 = {A, D, Y, F, C, H}
y su peso vale 18.

150. (p2001-pac43 ) Una empresa de telecomunicaciones pretende crear una red

de cable que una las ciudades de la tabla. El departamento de gastos ha calculado
el coste de construcción de cada una de las obras para cablear dos poblaciones
directamente; este es el resultado de su análisis (en millones de euros):
Barcelona Tarragona Lleida Girona Terrassa Ripoll
Tarragona 10,3 −− −− −− −− −−
Lleida 9,4 10,1 −− −− −− −−
Girona 8,9 17,8 8,5 −− −− −−
Terraza 5,5 7,8 7,5 8 −− −−
Ripoll 6,5 11,9 6,3 5,9 3,6 −−
Amposta 10,8 2,8 6,7 18,4 7,9 10,2

(a) Determina la red de telecomunicaciones por cable más económica, uti-

lizando el algoritmo de Kruskal.

(b) ¿La solución es única? En caso afirmativo, ¿existe algún valor para el
que los gastos de la conexión entre Terrassa y Barcelona no tengan una
solución única?

Solución

(a) Tenemos que escoger las aristas con peso inferior y que no formen ciclo:
ATa (2,8), TeRi(3,6), BTe(5,5), GRi(5,9), RiLl(6,3) y ALl(6,7), tal y como
muestra esta representación.
Árboles 95

(b) Sı́: 6,5. En este caso, se podrı́a escoger entre BTe ó BRi.

151. (p2001-final10 ) Una empresa quı́mica almacena 6 productos diferentes

en 6 depósitos subterráneos diferentes. Las reglas de almacenamiento de estos
productos no permiten que se construya un túnel directo entre los depósitos
de algunos pares de estos productos. Si enumeramos los productos del 1 al 6,
este grafo presenta los túneles directos entre los productos que no se pueden
construir.

Entre los otros pares de productos sı́ que se pueden construir túneles directos.
El coste de un túnel entre dos depósitos es proporcional a la suma entre los
números que representan estos productos (por ejemplo, el coste del túnel entre
el depósito 1 y el 6 es 7).

(a) Construye el grafo que representa los túneles que se pueden construir.
(b) ¿Cuáles son los túneles que se deben construir de forma que el coste de
toda la obra sea mı́nima? ¿Hay alguna otra opción con el mismo coste?
Justifica la respuesta.

Solución

(a) Se trata del grafo complementario:

Árboles 96

(b) Los costes de la construcción de cada túnel son:

Siguiendo el algoritmo de Prim, podemos comprobar fácilmente que este

es el árbol generador minimal resultante:

152. (t2000-p7 ) Dado este grafo:

Árboles 97

(a) Llena la tabla que reproduce el algoritmo en profundidad para recorrer un

grafo empezando por el vértice 0. Pon las aristas y los vértices en el orden
en que se van recorriendo y explica brevemente, a continuación, como has
aplicado el algoritmo.
(b) Un viajante trabaja en un pequeño grupo de 7 islas del archipiélago
malayo. Cada dı́a se deberı́a desplazar a todas las islas diversas veces.
El billete para ir de una isla a otra es válido para todo el dı́a. Esta tabla
muestra el valor del billete entre las islas que están comunicadas directa-
mente:

Islas Kabia Kabaena Butung Tuk. Muna Alor Atauro

Kabia 11 5 5
Kabaena 7
Butung 4 5 8
Tukangbesi 6 10 6
Muna 13 5
Alor
Atauro

¿Cuál es la forma más económica en que puede viajar por todas las islas?
¿A cuando asciende el gasto en transporte?

Solución

(a) Una posibilidad es esta:

Árboles 98

(b) Se trata de encontrar el árbol generador minimal del grafo anterior, con
los pesos que se muestran a la tabla, teniendo en cuenta que los vértices
coinciden con estas islas:

Islas número
Kabia 0
Kabaena 1
Butung 2
Tukangbesi 3
Muna 4
Alor 5
Atauro 6
Las aristas que escogemos con el algoritmo de Kruskal son: 23, 24, 03,
06, 14, 25. El precio total es: 4 + 5 + 5 + 5 + 7 + 8 = 34.

153. (t2000-final5 ) El nuevo gobierno del archipiélago de Sealand ha decidido

unir sus 6 islas mediante puentes que permitan conectarlas directamente. Los
costes de construcción de los puentes dependen de la distancia entre las islas y
se resumen en la tabla siguiente:
A B C D E F
A − 5 6 4 3 7
B − − 2 4 8 5
C − − − 4 8 8
D − − − − 2 5
E − − − − − 4
F − − − − − −

(a) Determina cuales son los puentes que se deben construir para que todas
las islas queden conectadas y el coste total de la obra sea mı́nimo.
(b) Si las dos islas más grandes, la C y D han de estar conectadas entre sı́,
¿cuál serı́a la solución? Razona la respuesta.

Solución

(a) Definimos el grafo G(V, A) siendo V = {x|x es una de las 6 islas } y A =

{(x, y)|x, y se han de unir por un puente }. Además, para cada (x, y) ∈ A
definimos su peso como

w(x, y) = coste de la construcción del puente que une x y y

El grafo resultante es K6 y hace falta buscar un árbol generador de peso

total mı́nimo. Aplicando el algoritmo de Kruskal obtenemos el árbol:

(B, C), (D, E), (A, E), (E, F ), (B, D)

con un coste total w(G) = 15.

Árboles 99

(b) En este caso, la arista (C, D) tendrá que estar a la solución. Pero entonces
tendrı́amos un circuito. Por lo tanto, podemos eliminar la arista de peso
más grande de este circuito que seria la arista (B, D). Ası́ el nuevo árbol
será:
(B, C), (D, E), (A, E), (E, F ), (C, D)
y el coste total continúa siendo w(G) = 15.

154. (t2000-final11 ) La tabla siguiente recoge la distancia (en millas) entre

varias ciudades del estado de Indiana (USA):
Bloomington Evansville Fort Wayne Gary Indianapolis South Bend
Evansville 119 −− −− −− −− −−
Fuerte Wayne 174 290 −− −− −− −−
Gary 198 277 132 −− −− −−
Indianapolis 52 168 121 153 −− −−
South Bend 198 303 79 58 140 −−
Terre Haute 58 113 201 164 71 196

Se quiere construir un sistema de carreteras que comunique estas siete ciudades.

(a) Suponiendo que el coste de construcción de una milla de carretera está fi-
jado, determina qué carreteras se deben construir para que el coste total
de la construcción sea mı́nimo.
(b) ¿La solución es única? Justifica la respuesta.

Solución

(a) Definimos el grafo G(V, A), siendo V = {x|x representa cada una de las 7 ciudades }
y A = {(x, y)|x, y se han de unir por una carretera}. Además, para cada
(x, y) ∈ A, definimos su peso como w(x, y) = distancia en millas entre x y y.
El grafo resultante es K7 y hace falta busca un árbol generador de peso
total mı́nimo. Aplicando el algoritmo de Kruskal obtenemos el árbol:

(I, B)(B, T H), (SB, G), (F W, SB), (T H, E), (I, F W )

con un peso total w(G) = 480.

(b) En este caso, obtenemos un único árbol generador de peso mı́nimo puesto
que en la aplicación del algoritmo de Kruskal siempre hemos escogido la
única arista posible.

155. (t2000-final17 ) Siete computadores están interconectados por una red de

baja velocidad. La tabla siguiente da los tiempos (en milisegundos) que tardan
los mensajes al recorrer cada segmento de la red:
Segmento (A,B) (A,C) (A,D) (B,C) (C,D) (B,E) (B,F) (D,F) (E,F) (E,G) (F,G)
Tiempo 5 4 4 3 2 4 2 3 2 3 4
Árboles 100

El administrador de la red, situado en el punto C, ha de enviar diariamente

mensajes a todos los ordenadores. Para optimizar los recursos, interesa enviar
los mensajes de forma que el tiempo total necesario porque todas las estaciones
reciban el mensaje sea mı́nimo.

(a) Determina cuál será la subred por la cual se enviarán los mensajes y el
tiempo total necesario para que todas las estaciones reciban el mensaje.
(b) Si la conexión entre los ordenador B y F falla, indica como se puede mod-
ificar la subred anterior sin necesidad de volver a repetir los cálculos.

Solución

(a) Definimos un grafo G(V, A),

V = {x|x es un computador }

A = {(x, y)|x, y están interconectados }

Además, para cada (x, y) ∈ A, definimos su peso como

w(x, y) = { tiempo entre x e y}

Para resolver el problema hace falta busca un árbol generador de peso

total mı́nimo. Aplicando el algoritmo de Kruskal obtenemos el árbol:

(B, F ), (C, D), (E, F ), (B, C), (E, G), (A, C)

con un tiempo total w(G) = 16.

(b) En este caso, sólo hace falta suprimir (B, F ) y añadir la arista de peso
mı́nimo que no forme circuito con las anteriores. El nuevo árbol seria:

(C, D), (E, F ), (B, C), (D, F ), (E, G), (A, C)

con un tiempo total w(G) = 17.

156. (t2001-final7 ) El gráfico siguiente muestra (de forma resumida) el plano del
metro de Barcelona. Cada recta representa una lı́nea de metro y cada punto una
estación. Los valores que hay entre dos estaciones consecutivas representan la
distancia en kilómetros y el tiempo mediano que tardan los trenes. Por ejemplo,
El valor 4/12 que hay entre las estaciones de la lı́nea 1, UN(Universidad) y
CL(Clot) significa que hay 4 kilómetros y se tarda 12 minutos. Observa que hay
estaciones que se encuentran en más de una lı́nea.
Árboles 101

Para cada uno de los problemas siguiente indica qué grafo considerarı́as (da los
vértices, las aristas y los pesos), a qué tipo de problema de grafos corresponde
y qué algoritmo utilizarı́as por resolverlo:

(a) Calcular el tiempo mediano mı́nimo necesario por conectar dos estaciones.
(b) Calcular la cantidad mı́nima de cable necesario por conectar todas las
estaciones.
(c) Calcular el número mı́nimo de trasbordos que hace falta hacer para co-
municar dos estaciones.
(d) Comprobar si, des la estación de Clot (CL), es posible acceder a todas las
otras estaciones del metro.

Solución

(a) V = {vi |vi ∈ Estaciones }, A = {(vi , vj )|vi , vj son adyacentes }, w(vi , vj ) =tiempo
mediano. Es un problema de distancia entre vértices y utilizarı́amos el al-
goritmo de Dijkstra.
(b) V = {vi |vi ∈ Estaciones }, A = {(vi , vj )|vi , vj son adyacentes }, w(vi , vj ) =
distancia. Es un problema de árboles generadores y podrı́amos utilizado
el algoritmo de Kruskal o el de Prim.
(c) V = {vi |vi ∈ Lı́neas }, A = {(vi , vj )|vi , vj tienen una estación en común },
w(vi , vj ) = 1. Es un problema de distancia mı́nima en grafo no ponderado.
Aplicariamos el algoritmo de Dijsktra.
(d) V = {vi |vi ∈ Estaciones }, A = {(vi , vj )|vi , vj son adyacentes }, w(vi , vj ) =
1. Es un problema de conectividad. Podrı́amos aplicar el DFS para com-
probar si todos los vértices son accesibles.

157. (p2002-pac44 ) Dada esta tabla:

Árboles 102

A B C D E
A 6 3 8 7
B 5 2 4
C 4 5
D 3
E

(a) Enuncia un problema (sin resolverlo) basado en esta tabla que sólo se
pueda resolver con el algoritmo de Dijkstra . Explı́calo.
(b) Enuncia un problema (sin resolverlo) basado en esta tabla que se deba
resolver con el algoritmo de Prim y no con el algoritmo de Kruskal. Ex-
plı́calo.
(c) Aplica el algoritmo de Prim al grafo ponderado generado por la tabla
anterior, haciendo la tabla correspondiente.

Solución

(a) El algoritmo de Dijkstra permite encontrar el camino más corto de un

vértice a cualquiera de los otros. Por lo tanto, un problema podrı́a ser:
Una compañı́a de autobuses tiene varias lı́neas que unen las ciudades A,
B, C, D y E. La tabla da la relación de precios del viaje entre dos de estas
ciudades. La compañı́a radicada en la ciudad A, donde tiene la sede, quiere
reducir plantilla, y sólo quedarse con aquellas lı́neas más competitivas; es
decir, aquellas que permitan hacer todos los recorridos desde A (aunque
no sean directas), de forma que el precio por el pasajero sea el menor
posible. ¿Qué lı́neas debe mantener?
(b) El algoritmo de Prim encuentra un árbol generador minimal, de forma
conexa. Por lo tanto, un problema resuelto por este algoritmo, y que no
se pueda resolver por el algoritmo de Kruskal, podrı́a ser: Un terremoto
destruye todas las carreteras de un pequeño paı́s (y, en particular, las
que unen las ciudades A, B, C, D, E, las más importantes del paı́s). El
presidente ordena rehacer aquellas que sean imprescindibles para que las
ciudades se mantengan unidas (partiendo de A, que es la capital y donde
se encuentran todas las empresas de reconstrucción). Además, dada la
situación del paı́s tras el terremoto, se debe procurar que el coste sea
el menor a cada paso de la reconstrucción. ¿Qué carreteras se deberán
reconstruir?
Sólo se puede aplicar el algoritmo de Prim porque la reconstrucción sólo
se puede hacer de forma conexa (las otras ciudades están incomunicadas
y no tienen maquinaria para rehacer las carreteras).
(c) Esta es la tabla del algoritmo de Prim:
Árboles 103

A B C D E
(0,A) (∞,A) (∞,A) (∞,A) (∞,A)
(0,A)∗ (6,A) (3,A) (8,A) (7,A)
(0,A) (5,C) (3,A)∗ (4,C) (5,C)
(0,A) (2,D) (3,A) (4,C)∗ (3,C)
(0,A) (2,D)∗ (3,A) (4,C) (3,C)
(0,A) (2,D) (3,A) (4,C) (3,C)∗
Por lo tanto, las aristas escogidas deben ser BD, AC, DC, DE

158. (p2002-final4 ) Queremos conectar 5 ordenadores mediante un red, el máxi-

mo de económica posible, que permita la comunicación (directa o indirecta) entre
dos ordenadores cualesquiera. La tabla siguiente muestra los costes de conexión
fı́sica entre los 5 ordenadores:

A B C D E
A - 5 2 4 7
B 5 - 2 3 2
C 2 2 - 5 1
D 4 3 5 - 2
E 7 2 1 2 -

(a) Dibuja el grafo correspondiente al problema.

(b) Encuentra la solución al problema planteado (conexiones entre los orde-
nadores y coste total de la conexión) usando la teorı́a de grafos. Muestra
en una tabla los pasos del algoritmo escogido para llegar a la solución.
(c) Por necesidades de administración, queremos que los ordenadores C y D
estén conectados directamente. ¿Cuál serı́a ahora la solución del problema?
¿Podemos encontrar esta solución a partir del anterior sin necesidad de
repetir el algoritmo?

Solución

(a)

(b) La tabla siguiente muestra los pasos del algoritmo de Prim

Árboles 104

A B C D E
(0,A) (∞,A) (∞,A) (∞,A) (∞,A)
(0,A)∗ (5,A) (2,A) (4,A) (7,A)
(0,A) (2,C) (2,A)∗ (4,A) (1,C)
(0,A) (2,C) (2,A) (2,E) (1,C)∗
(0,A) (2,C)∗ (2,A) (2,E) (1,C)
(0,A) (2,C) (2,A) (2,E)∗ (1,C)

Según la tabla, las conexiones serian (B,C), (C,A), (D,E) y (E,C) con un
coste total de 7 .
(c) Si añadimos la arista (C,D) con un coste 5 entonces tendremos un ciclo
(C,D,E,C). Por tal que la solución sea óptima, sólo hace falta eliminar
la arista de coste máximo del ciclo que no sea (C,D). La nueva solución
será (B,C), (C,A), (C,D) y (E,C) con un coste total de 10 .

159. (p2002-final8 ) Dado un grafo ponderado, se le aplica un algoritmo por

encontrar el árbol generador minimal. La tabla del algoritmo es esta:
0 1 2 3 4 5 6
(0,0) (∞,0) (∞,0) (∞,0) (∞,0) (∞,0) (∞,0)
(0,0)∗ (48,0) (∞,0) (∞,0) (11,0) (59,0) (∞,0)
(0,0) (48,0) (61,4) (87,4) (11,0)∗ (55,4) (∞,0)
(0,0) (48,0)∗ (61,4) (87,4) (11,0) (55,4) (∞,0)
(0,0) (48,0) (61,4) (87,4) (11,0) (55,4)∗ (54,5)
(0,0) (48,0) (56,6) (87,4) (11,0) (55,4) (54,5)∗
(0,0) (48,0) (56,6)∗ (27,2) (11,0) (55,4) (54,5)

(a) ¿Qué algoritmo se ha aplicado? ¿Como lo has deducido?

(b) Modifica este grafo como creas oportuno para que con la tabla anterior se
encuentre su árbol generador.
(c) ¿Crees que el algoritmo se ha acabado? ¿Por qué?
Grafos eulerianos y grafos hamiltonianos 105

Solución

(a) El algoritmo de Prim, porque la tabla del algoritmo de Kruskal es más

sencilla, dado que no hace falta que el árbol que se va construyendo sea
conexo.
(b) Se debe modificar el peso de la arista {3, 6}, que debe ser más grande que
87 en el 6 paso; de lo contrario, se deberı́a modificar el valor del vértice 3
en el 6 paso.
(c) No, porque no se han recorrido todos los vértices. Ahora bien, el último
paso sólo nos trae al último vértice, tal y como se ve a la tabla:
0 1 2 3 4 5 6
(0,0) (∞,0) (∞,0) (∞,0) (∞,0) (∞,0) (∞,0)
(0,0)∗ (48,0) (∞,0) (∞,0) (11,0) (59,0) (∞,0)
(0,0) (48,0) (61,4) (87,4) (11,0)∗ (55,4) (∞,0)
(0,0) (48,0)∗ (61,4) (87,4) (11,0) (55,4) (∞,0)
(0,0) (48,0) (61,4) (87,4) (11,0) (55,4)∗ (54,5)
(0,0) (48,0) (56,6) (87,4) (11,0) (55,4) (54,5)∗
(0,0) (48,0) (56,6)∗ (27,2) (11,0) (55,4) (54,5)
(0,0) (48,0) (56,6) (27,2)∗ (11,0) (55,4) (54,5)
Capı́tulo 8

Grafos eulerianos y grafos

hamiltonianos

160. (p99-pac23 ) Comprueba si estos dos grafos conexos son eulerianos o hamil-
tonianos, y explica el motivo.

Solución
El grafo de la izquierda es euleriano porque todos los vértices son de grado par.
El grafo de la derecha no es euleriano porque hay varios vértices de grado impar.
El grafo de la izquierda no es hamiltoniano porque no es 2-conexo: si quitamos
el vértice rojo el grafo se desconecta. En cambio, el grafo de la derecha es
hamiltoniano: la lı́nea roja marca un ciclo hamiltoniano.

106
Grafos eulerianos y grafos hamiltonianos 107

161. (t99-pac22 ) Estudia si este grafo es hamiltoniano o euleriano:

Solución
Evidentemente, no es euleriano porque hay un vértice (de hecho, más) que tiene
grado impar (por ejemplo, el vértice 5). Vamos a ver si es hamiltoniano. Consid-
eramos este conjunto de vértices: 2, 4, 6 y 10. Cada uno de ellos tiene grado 3.
Ahora bien, sólo 2 de estas 3 aristas se encontrarán en el ciclo hamiltoniano; por
lo tanto, estos 4 vértices aportan 8 aristas al ciclo hamiltoniano. Ahora bien, el
ciclo hamiltoniano necesita 10 aristas y las aristas que restan, tras escoger 2 de
cada uno de los vértices del conjunto anterior son estas 3: 38, 79, 15. Se puede
suponer que las aristas del ciclo son 38 y 79 y 15 no pertenece al ciclo; por lo
tanto

45, 510, 16 y 12 pertenecen al ciclo (porque no pertenece 15).

se puede escoger entre 23 y 27: si se escoge 23, entonces se continúa por
710. A partir de aquı́ ya no se puede seguir: 68 o 49 cierran dos ciclos más
pequeños. Si se escoge 27, pasa algo de parecido.

Si escogemos cualquier otro par de aristas de este grupo de 3, pasa exactamente

lo mismo. Por lo tanto, el grafo no es hamiltoniano.

162. (t99-final4 ) Estudia si el siguiente grafo es hamiltoniano. Razona la re-

spuesta.

Solución
No es hamiltoniano, porque si eliminamos las 5 aristas numeradas:
Grafos eulerianos y grafos hamiltonianos 108

quedan 6 componentes conexas:

163. (t99-final11 ) El esquema siguiente corresponde a una red de comunica-

ciones entre varias ciudades.

Los vértices son las ciudades y las aristas, las comunicaciones: Se debe hacer un
recorrido de inspección y mantenimiento de la red empezando y acabando a A.
El recorrido deberı́a pasar por todos los tramos o carreteras una única vez.

(a) ¿Es posible diseñar un recorrido de este tipo?

(b) ¿Es posible diseñar un recorrido de estas caracterı́sticas que empiece a A
y acabe a B?

Solución
Grafos eulerianos y grafos hamiltonianos 109

(a) No es posible. El grafo que modeliza esta situación no es euleriano porque

el vértice A tiene grado 3 aristas incidentes.
(b) Sı́. Sólo hace falta seguir este camino, donde los números indican la suce-
sión de vértices: 1234563576847814

164. (p2000-pac21 ) La matriz de adyacencia de un grafo es

 
0 1 1 1 0 0 0
1 0 1 0 1 0 0
 
1 1 0 1 0 0 0
 
1 0 1 0 0 1 0
 
0 1 0 0 0 1 1
 
0 0 0 1 1 0 1
0 0 0 0 1 1 0

Di cuál de las siguientes caracterı́sticas son aplicables a este grafo y razona la

respuesta: es conexo, es completo, es bipartido, es un grafo estrella, es hamilto-
niano, es euleriano.

Solución
El grafo es el siguiente:

Es conexo, puesto que dados dos vértices cualesquiera siempre podemos

encontrar un camino que va de uno a otro.
No es completo, puesto que hay vértices que no son adyacentes, por ejem-
plo los vértices 1 y el 5.
No es bipartido, puesto que existe un triángulo (vértices 1, 2 y 3) y esto
en un grafo bipartido es imposible.
Grafos eulerianos y grafos hamiltonianos 110

No es un grafo estrella. La matriz de adyacencia deberı́a tener una fila y

una columna todo con unos y el resto ceros.
Sı́ es hamiltoniano. Existe un camino cerrado sin vértices repetidos que
pasa por todos los del grafo. Por ejemplo el camino: 1, 4, 6, 7, 5, 2, 3, 1.
No es euleriano, puesto que hay vértices, por ejemplo el 1, que son de
grado impar y en un grafo euleriano todos los vértices son de grado par.

165. (t2000-p6 ) Considera este grafo conexo:

(a) Di si hay vértice de articulación y, en caso afirmativo, encuéntralos todos.

(b) Di cuál es su diámetro.
(c) ¿Es euleriano este grafo?
(d) ¿Es hamiltoniano?

Solución

(a) El vértice 1 es de articulación porque al eliminarlo quedan dos compo-

nentes conexas.
(b) El diámetro es 4 que es la distancia entre el vértice 0 y el 5.
(c) No, porque hay vértices de grado impar.
(d) No, porque tiene un vértice de grado 1.

166. (t2000-pac21 ) Se define el hipercubo de dimensión n (n ≥ 1) como el

grafo Qn que tiene como vértices todos los vectores binarios de n coordenadas,
siendo dos vértices adyacentes si, y sólo si, los correspondientes vectores difieren
exactamente en 1 coordenada (están a distancia 1). Por ejemplo, para n = 2 Q2
tendrı́a 4 vértices: {00, 01, 10, 11} y el vértice 00 es adyacente al 01 pero no al
11.
Grafos eulerianos y grafos hamiltonianos 111

(a) Determina el número de vértices y el número de aristas de Qn .

(b) ¿Para qué valores de n el grafo Qn es regular?
(c) ¿Para qué valores de n el grafo Qn es bipartido?
(d) ¿Para qué valores de n el grafo Qn es euleriano?

Solución

(a) |V | = 2n . Cada vértice tiene exactamente n adyacencias. Ası́,

n
2
X
2|A| = n = n · 2n
i=1

De aquı́ |A| = n · 2n−1 .

(b) Tal y como hemos indicado en el punto 1, cada vértice tiene exactamente
n adyacencias. Ası́, Qn es regular para todo n.
(c) Definimos V1 = {x ∈ Qn |x tiene un número par de 0} y V2 = V − V1 .
Entonces, V1 ∪ V2 = V , V1 ∩ V2 = ∅ y si (x, y) ∈ A, x y y difieren
exactamente en una coordenada. Ası́, si x tiene un número par de ceros,
entonces y tendrá un número impar.
(d) Como que cada vértice tiene grado n entonces, Qn será euleriano cuando
n sea par.

167. (t2000-pac24 ) En el juego del dominó:

(a) ¿Es posible obtener una secuencia circular que contenga todas las fichas?
(b) Lo mismo que antes, si prescindimos de todas las fichas que contienen 6
puntos en alguno de los lados.
(c) ¿Y si sólo consideramos las fichas que, sumando los puntos de los dos
lados, da un resultado menor o igual que N puntos (0 ≤ N ≤ 12)?
(d) Si eliminamos la ficha [1|2], es posible obtener una secuencia (circular o
no) que contenga todas las otras fichas?

Nota: Por secuencia circular entendemos una disposición de las fichas de forma
que dos fichas adyacentes tienen los mismos puntos. Por ejemplo, las fichas
[0 | 6][6 | 6][6 | 1][1 | 0] forman una secuencia circular.

Solución
El dominó está formato por 28 fichas. 7 dobles y 21 fichas con puntos diferentes
a cada lado. Definimos el grafo G(V, A) por V = {x|x = 0, . . . , 6} y A =
{(x, y)|x, y es una ficha }. El grafo resultante es un grafo completo de 7 vértices
y un lazo en cada vértice (pseudografo). Ası́ cada vértice tendrá grado 8. Definido
ası́, se trata de un problema de grafos eulerianos.
Grafos eulerianos y grafos hamiltonianos 112

(a) Sı́ que es posible construir un circuito euleriano porque todos los vértices
tienen grado par.
(b) Si prescindimos de las fichas que tienen seis puntos en alguno de los la-
dos, entonces cada vértice tendrá grado impar y no podremos construir el
circuito.
(c) Sólo será posible para N = 0, 11, 12.
(d) Si eliminamos la ficha [1|2] entonces no podremos formar circuito pero sı́ un
itinerario puesto que habrá exactamente dos vértices de grado impar.

168. (t2001-final12 ) Responde estas cuestiones razonadamente:

(a) Demuestra que si G es un grafo bipartido con un número impar de vértices,

G no es hamiltoniano.
(b) ¿Este grafo es hamiltoniano?

Solución

(a) En un grafo bipartido un ciclo ha de tener un número par de vértices. Por

lo tanto, un grafo bipartido con un número impar de vértices no puede ser
hamiltoniano.

(b) Sólo hace falta ver que es bipartido, cosa evidente:

Grafos eulerianos y grafos hamiltonianos 113

169. (p2002-pac33 )

(a) ¿Para qué valores de n el grafo completo de grado n es euleriano? ¿y el

grafo Kn,m ?

(b) Dada esta figura, di si es posible dibujar una lı́nea continua que, partiendo
del punto A, corte exactamente una vez cada segmento de recta interior al
rectángulo, (esta lı́nea no puede pasar por las intersecciones de segmentos).
Explı́calo en términos de teorı́a de grafos. En caso afirmativo, dibújala.

(c) Repite el problema con la figura siguiente:

Solución

(a) En el caso de Kn , cuando n es impar, porque el grado de cada vértice es

n − 1, par. En el caso de Kn,m , cuando n y m son impares, por razones
similares.
(b) Si modelizamos la figura anterior en forma de grafo, obtenemos:

Debemos ver si este grafo es euleriano. Claramente, no lo es porque hay

vértices de grado impar.

(c) En este caso, el grafo correspondiente a la figura anterior es:

Grafos eulerianos y grafos hamiltonianos 114

que claramente es euleriano. Una lı́nea que corta todos los segmentos sin
repetir ninguno puede ser:

170. (p2002-pac31 ) El grafo hipercubo de dimensión n se define recursivamente

de la manera siguiente:

K2 si n = 1
Qn =
Qn−1 × K2 si n > 1

Qn−1 × K2 significa el grafo producto de Qn−1 y K2 .

(a) Dibuja los grafos Q2 y Q3 .

(b) Calcula, en función de n, el orden y la medida del grafo Qn.
(c) ¿Para qué valores de n el grafo Qn es regular?
(d) ¿Para qué valores de n el grafo Qn es bipartido?

(e) ¿Para qué valores de n el grafo Qn es euleriano?

Solución

(a)

(b) Por inducción se comprueba que el orden es 2n y la medida es n2n−1 .

Grafos eulerianos y grafos hamiltonianos 115

(c) Por inducción podemos ver que el grado de cada vértice es n. Por n = 1
es evidente. Suponemos que el grado de cada vértice de Qn−1 es n − 1.
Entonces, podemos describir los vértices de Qn como (v, x), siendo v es
un vértice de Qn−1 y x ∈ {1, 2}. Entonces, dos vértices de Qn serán
adyacentes si son de la forma (v, x) y (w, x) con v y w adyacentes a Qn−1 ,
o de la forma (v, 1) y (v, 2). En total, n posibilidades.
Ası́, el grafo será regular.
(d) De nuevo, vamos a ver que es bipartido por inducción. Si n = 1 es ev-
idente. Suponemos que Qn−1 es bipartido y que el dos subconjuntos de
vértices son V1 (Qn−1 ) y V2 (Qn−1 ). Entonces definimos los subconjuntos
de Qn siguientes: V1 = (V1 (Qn−1 ), 1) ∪ (V2 (Qn−1 ), 2) y V2 (V2 (Qn−1 ), 1) ∪
(V1 (Qn−1 ), 2). Entonces, dos vértices de Qn son adyacentes sólo si uno
pertenece a V1 y el otro a V2 .
(e) Como que el grado de cada vértice es n sólo podrá será euleriano cuando
n sea par.

171. (p2002-final3 ) Si denotamos por Tn el grafo trayecto de n vértices, entonces

definimos el grafo parrilla como el grafo producto de dos grafos trayecto: Gn,m =
T n × T m, (n, m ≥ 2).

(a) Dibuja los grafos G2,3 y G4,4 .

(b) Calcula, en función de n y m el orden y la medida del grafo Gn,m .
(c) Calcula, en función de n y m, la secuencia de grados de Gn,m .
(d) ¿Para qué valores de n y m el grafo Gn,m es regular?
(e) ¿Para qué valores de n y m el grafo Gn,m es bipartido?
(f) ¿Para qué valores de n y m el grafo Gn,m es euleriano?

Solución

(a)

(b) orden=nm, medida=n(m − 1) + m(n − 1)

Grafos eulerianos y grafos hamiltonianos 116

(c) 4 vértices de grado 2, 2n + 2m − 8 vértices de grado 3 y (n − 2)(m − 2)

vértices de grado 4 .
(d) Para n = m = 2.
(e) Si denotamos por 1, 2, . . . , n los vértices de T n y por 1, 2, . . . , m los vértices
de Tm entonces los vértices de Gn,m serán parejas de la forma (x, y) con
1 ≤ x ≤ n y 1 ≤ y ≤ m. Observamos, además, que dos vértices (x1 , y1 ),
(x2 , y2 ) son adyacentes si tienen una misma coordenada igual y la otra
difiere en una unidad.
Ahora, consideramos V1 = {(x, y) ∈ Gn,m | x + y es par} y V2 el resto.
Entonces, dos parejas de V1 (igualmente V2 ) no pueden ser adyacentes y
toda arista de Gn,m une un vértice de V1 con un de V2 .
(f) Sólo cuando n = m = 2

172. (t2004-pac41 ) Un código de Gray es una ordenación de las palabras binarias

de longitud n, que cumple estas dos condiciones:

Dos palabras consecutivas sólo difieren en un dı́gito.

La primera y la última palabras sólo difieren en un dı́gito.

Si n = 3:

(a) Define y dibuja el grafo que modele la primera condición de las dos ante-
riores.
(b) Usa tus conocimientos sobre grafos para determinar una codificación de
Gray.

Solución

(a) Este problema se puede modelar mediante un grafo, los vértices del cual
son las palabras binarias de longitud 3 y dos palabras son adyacentes si
difieren exactamente en un dı́gito. El grafo obtenido es el cubo:
Grafos eulerianos y grafos hamiltonianos 117

(b) Para resolver el problema sólo debemos encontrar un ciclo hamiltoniano

al cubo. Por ejemplo, un ciclo hamiltoniano seria 000, 001, 011, 010, 110,
111, 101, 100, 000.

173. (t2004-pac42 ) Dado un grafo G(V, A) de orden n y medida m, definimos

el grafo lı́nea de G, L(G), como el grafo que tiene por conjunto de vértices el
conjunto de aristas de G y dos vértices de L(G) son adyacentes si las correspon-
dientes aristas de G son adyacentes (tienen un vértice en común).

(a) Demuestra que si G es un árbol que no es un trayecto, entonces L(G) no

es un árbol. ¿Cómo es L(G) si G es un grafo trayecto?

(b) Demuestra que si G es euleriano entonces L(G) es euleriano y hamiltoni-

ano.

Solución

(a) Si G es un árbol que no es un trayecto, entonces existe algún vértice

de, como mı́nimo, grado 3; sea v este vértice, y sean v1 , v2 y v3 vértices
adyacentes a v. Las aristas {v, v1 }, {v, v2 }, {v, v3 } serán vértices de L(G)
y formarán un ciclo. Por lo tanto, L(G) no puede ser un árbol.
Si G es un trayecto, es muy sencillo darse cuenta que L(G) es un trayecto
con un vértice menos.
(b) Si G es euleriano entonces cada vértice de G tiene grado par. Sea a un
vértice de L(G). Observa que a = uv será una arista de G y g(u) =
gu y g(v) = gv son números pares. Entonces la arista a es adyacente
gu − 1 + gv − 1 aristas de G y, por lo tanto, el vértice a ∈ L(G) es
adyacente a gu + gv − 2 vértices de L(G). Como que gu y gv son números
pares entonces el g(a) = gu + gv − 2 a L(G) también será par y L(G)
será euleriano.
Si G es euleriano podemos formar un circuito a1 , a2 , . . . , am que pase por
todas las aristas de G. Este circuito a G corresponde a un ciclo a L(G)
que pasa por todos los vértices del grafo L(G). Por lo tanto, L(G) será un
grafo hamiltoniano.

174. (t2004-pac44 ) Una empresa fabrica bombones de chocolate hexagonales de

diferentes tipos de chocolate. Con estos bombones crea la denominada pirámide
hexagonal de chocolate: se trata de poner diferentes filas de hexágonos unidos de
forma que hagan una pirámide, es decir, en la primera fila ponen un hexágono;
en la segunda dos; en la tercera, tres; etc. Por ejemplo, esta serı́a la pirámide
hexagonal de 4 filas:
Grafos eulerianos y grafos hamiltonianos 118

Una persona compra una de estas pirámides con n filas. A partir del dı́a sigu-
iente, cada dı́a se comerá una pieza, empezando por el hexágono de arriba. El
resto de dı́as se comerá un hexágono que tenga una arista en común con la pieza
que ha comido el dı́a anterior.

(a) Modela esta situación utilizando un grafo, y da su secuencia de grados y

su medida en función de n.
(b) La persona en cuestión quiere adquirir otra pirámide de este tipo con-
struida con tres tipos de hexágonos, cada tipo hecho con un chocolate
diferente. Esta pirámide quiere comérsela de igual manera, pero imponien-
do, además, que en tres dı́as consecutivos no repita el tipo de chocolate.
¿Como construirı́as la pirámide para que esto fuera posible? Indica la se-
cuencia de hexágonos que deberı́a seguir esta persona a la hora de comer
una pirámide con 5 filas, y di cómo se describirı́a en términos de grafos
esta secuencia.
(c) ¿Hay ninguna pirámide hexagonal del tipo descrito al apartado anterior
que tenga el mismo número de piezas de cada uno de los tres tipos de
chocolate? Si la respuesta es afirmativa, di la condición que debe cumplir
el número de filas, n, de la pirámide. Pon algunos ejemplos.

Solución

(a) Para n = 5 éste es el grafo:

Observamos que hay tres vértices de grado 2, 3 · 3 = 9 vértices de grado

4 y tres vértices de grado 6. En general, una pirámide hexagonal de n
Grafos eulerianos y grafos hamiltonianos 119

filas tiene n(n+1)

2 vértices. De estos, tres vértices tienen grado 2, 3(n − 2)
vértices tienen grado 4 y el resto, es decir, (n−3)(n−2)
2 tienen grado 6. La
medida será, pues:
(n−3)(n−2)
2 · 3 + 4 · 3(n − 2) + 6 · 2 3n(n − 1)
=
2 2

(b) Si coloreamos (o enumeramos) los vértices del grafo, de forma que cada
color se asocia a un chocolate diferente, veremos que obtendremos un grafo
como el siguiente:

si observamos la diagonal empezando por el vértice superior bajando por

la izquierda, siempre tendrá una secuencia de colores (1=negro, 2=ro-
jo, 3=verde): 123123123123123... La siguiente diagonal paralela al ante-
rior será: 312312312312312... La siguiente diagonal tendrá una secuencia:
231231231231231... Y a partir de aquı́ se vuelven a repetir las secuencias
diagonales. Por lo tanto, ésta es la distribución de colores (chocolates)
que buscamos. Ahora se trata de recorrer todos los vértices del grafo sin
repetición, y de manera que cada grupo de tres vértices seguidos tengan
colores diferentes. Esta secuencia, si existe, será un camino hamiltoniano.
Es fácil ver que existe, por ejemplo:

además, este camino se puede hacer para cualquier pirámide hexagonal,

de forma parecida.

(c) Sólo hace falta encontrar grafos de este tipo de orden múltiplo de 3, puesto
que si el orden de un grafo es múltiplo de 3, siguiendo el camino hamil-
Grafos eulerianos y grafos hamiltonianos 120

toniano que hemos encontrado en el apartado anterior, pasaremos por el

mismo número de vértices de cada color.
El orden del grafo es n(n+1)
2 y debe ser múltiplo de 3. Por lo tanto, n(n+1)
debe ser múltiplo de 6. Es fácil encontrar muchas n que cumplen esta
condición: 2, 3, 5, 6, 8, 9 ...

175. (t2000-final12 ) Las tarjetas de circuitos necesitan tener agujeros para

poder insertar circuitos integrados, resistencias y otros componentes electrónicos.
La tabla siguiente representa la posición en la que se debe hacer cada agujero
en las tarjetas:
A B C D E F G H Y
(0, 0) (−1, 0) (1, 0) (−1, 3) (0, 1) (1, 3) (−1, −3) (0, −1) (1, −3)
La broca se mueve sobre las tarjetas siguiendo sólo recorridos verticales y hor-
izontales y, para minimizar costes, sólo hace recorridos de un máximo de 3mm
(sumando el recorrido vertical y la horizontal) entre dos perforaciones. Partien-
do de la posición A, di si será posible que la broca perfore todos los agujeros
sin pasar dos veces por la misma posición y volviendo a la posición inicial. En
caso negativo, di si lo podrá hacer sin necesidad de volver a la posición inicial.
Justifica las respuestas.

Solución
Definimos G(V, A) siendo

V = {x|x representa un agujero }

A = {(x, y)|x, y están a menos de 3mm. }

El grafo resultante es el siguiente:

Grafos eulerianos y grafos hamiltonianos 121

Sı́ que existe un ciclo hamiltoniano. Por ejemplo, A − H − Y − G − B − D −

E − F − C − A.

176. (t2002-pac43 ) Considera el grafo representado por la lista de adyacencias

siguiente:
A : E
B : G, C, A
C : E
D : B, F, E,
E :
F : C, B, E, A
G : A

Supón que cada vértice representa una tarea i, que una arista entre el vértice
i y el vértice j significa que la tarea i se debe realizar antes de que la tarea j.
Se quiere obtener un orden de ejecución de las tareas de forma que se cumplan
todas las restricciones de las precedencias. Para conseguirlo, sigue estos pasos:

(a) Se quiere aplicar el algoritmo BFS, de forma que la lista de vértices visi-
tados sea la solución al problema. ¿Cuál es el mejor vértice para empezar
este algoritmo?
(b) Aplica el algoritmo BFS y da la lista de vértices visitados. ¿El listado de
vértices resultante de la aplicación del algoritmo cumple la condición?
(c) ¿Qué modificación harı́ais al algoritmo para que la lista resultante cumpla
la condición?
Grafos eulerianos y grafos hamiltonianos 122

(d) ¿Qué complejidad tendrá el algoritmo propuesto?

Solución
El algoritmo BFS empezando por el vértice D (que es el mejor vértice posible,
porque tiene grado de entrada 0) no da una lista de vértices que cumpla la condi-
ción de precedencia. Podemos utilizar el algoritmo BFS con las modificaciones
siguientes:

Asociamos a cada vértice su grado de entrada.

Empezaremos por un vértice de grado de entrada 0. Inicialmente, el vértice
D.

Decrementaremos el grado de entrada de todos los vértices adyacentes al

vértice analizado. Si vale 0 lo añadiremos a la cola.

La tabla siguiente resume la aplicación del algoritmo:

Q Vértices Añadidos Vértice eliminado R

D D - -
DF F -
F - D D
FB B - D
B - F DF
BCG C,G - DF
CG - B DFB
CG - - DFB
G - C DFBC
GA A - DFBC
A - G DFBCG
AE E - DFBCG
E - A DFBCGA
∅ - E DFBCGAE

Este algoritmo tiene la misma complejidad que el algoritmo BFS básico, es decir,
O(n + m).

177. (t2002-pac44 ) Considera el problema del viajante de comercio sobre el

grafo definido por la tabla de pesos

v1 v2 v3 v4 v5
v1 − 8 2 6 2
v2 8 − 10 2 −
v3 2 10 − − 8
v4 6 2 − − 2
v5 2 − 8 2 −
Grafos eulerianos y grafos hamiltonianos 123

(a) ¿Cuántas son las posibilidades que deberemos probar si quisiéramos re-
solver el problema exhaustivamente?
(b) Encuentra, de manera razonada, una aproximación a la solución óptima
de este problema.
(c) ¿Por qué no podemos aplicar el algoritmo TSP-aproximado por encontrar
una solución aproximada al problema?

Solución

(a) Si n es el orden del grafo, deberemos probar (n−1)!

2 posibilidades (aunque,
como el grafo no es completo, algunas no corresponden a posibilidades
reales). En nuestro caso, 4!2 = 12.

(b) Podemos aplicar el algoritmo de Kruskal o el de Prim por encontrar un

árbol generador minimal del grafo. La tabla siguiente resume los pasos del
algoritmo de Prim:

1 2 3 4 5
(0, 1) (∞, 1) (∞, 1) (∞, 1) (∞, 1)
(0, 1)∗ (8, 1) (2, 1) (6, 1) (2, 1)
(0, 1) (8, 1) (2, 1)∗ (6, 1) (2, 1)
(0, 1) (8, 1) (2, 1) (2, 5) (2, 1)∗
(0, 1) (2, 4) (2, 1) (2, 5)∗ (2, 1)
(0, 1) (2, 4)∗ (2, 1) (2, 5) (2, 1)

De esta tabla se deduce que el ciclo hamiltoniano de peso mı́nimo de-

berá tener una longitud mı́nima de 8 .
(c) En este caso no podemos utilizar el algoritmo TSP-aproximado porque el
grafo no cumple la desigualdad triangular. Por ejemplo, 8 = w(v3 , v5 ) >
w(v3 , v1 ) + w(v1 , v5 ) = 4.

178. (p2003-pac44 ) Aprovechando el caos de la posguerra, una banda interna-

cional de ladrones quiere asaltar el museo arqueológico de un paı́s devastado por
la guerra. Han conseguido un plano del museo, que es este:
Grafos eulerianos y grafos hamiltonianos 124

(a) El primer plan consiste en entrar por la entrada y recorrer todas las salas
vaciando todas las vitrinas, intentando no repetir el paso por ningún sala
(para no perder tiempo). Hace falta tener en cuenta que los patios no son
accesibles y que desde una sala se puede ir a cualquier otra sala adyacente.
Formula este plan en términos de teorı́a de grafos y averigua si es posible
llevarlo a cabo (también en términos de teorı́a de grafos)
(b) El jefe de esta banda de malhechores se entera que el museo dispone de
un dispositivo que, cuando hay peligro, cierra automáticamente todas las
puertas entre salas, excepto la puerta de entrada. Este plano reproduce el
tiempo que tardarı́an en encontrar el código de apertura de cada una de
las puertas (siempre que se pasa por una puerta, tanto para entrar como
para salir con el botı́n, tardarı́an el tiempo indicado).
Grafos eulerianos y grafos hamiltonianos 125

i. Indica, sin resolver, como se puede modelar el problema de asaltar el

museo utilizando el menor tiempo posible en términos de la teorı́a de
grafos. ¿Qué algoritmo utilizarı́as para solucionarlo?
ii. ¿El problema cumple todas las condiciones para poder ser resuelto
por este algoritmo?
iii. Sabemos que la alarma del museo sonará cuando los ladrones entren
al museo. La policı́a del paı́s, que no tiene muchos recursos, tar-
dará dos horas en llegar al museo tras saltar la alarma. ¿Conseguirán
estos ladrones salir con el botı́n sin encontrarse con la policı́a? Utiliza
recursos de teorı́a de grafos por contestar esta pregunta.

Solución

(a) Construyendo el grafo simple correspondiente a esta situación

Grafos eulerianos y grafos hamiltonianos 126

hace falta ver si es hamiltoniano; es fácil comprobar que el grafo es bipar-

tido, pero al tener orden impar no se puede dividir el conjunto de vértices
en dos conjuntos con el mismo número de vértices. Por lo tanto, el proyec-
to de los malhechores no se puede llevar a término tal y como lo habı́an
planificado.
(b) i. Se trata de intentar resolver el T SP −aproximado utilizando el grafo
anterior, con los pesos dados por el tiempo que se tarda en abrir las
puertas. Pero como sabemos que el grafo no es completo, no se puede
aplicar el T SP −aproximado. Deberemos transformar el grafo inicial
con el algoritmo de Floyd, y ası́ obtendrı́amos un grafo completo con
las distancias mı́nimas entre vértices. Ahora, podrı́amos aplicar el
algoritmo T SP − aproximado.
ii. Si el grafo es el original, no, porque no cumple la desigualdad trian-
gular: entre la sala 5 y 6, la puerta tarda en abrirse 40 minutos, pero
yendo por las salas 5 − 7 − 8 − 6, se tarda 18 + 13 + 6 = 37 minutos.
En cambio, sı́ que se puede hacer si utilizamos el grafo resultante de
aplicar el algoritmo de Floyd .
iii. Afortunadamente, la policı́a siempre llegará a tiempo, porque es obvio
que el mı́nimo de tiempo que tardará la banda al pasar todas las
puertas es igual al peso del árbol generador minimal del grafo del
apartado a. En este caso, el peso es de 6+9+11+13+15+18+18+22 =
112 minutos. Cómo tendrán que recorrer alguna sala más para salir
Grafos eulerianos y grafos hamiltonianos 127

(recordamos que no es hamiltoniano), tardarán más de 120 minutos

para salir.