Leccion3

Vista previa del material en texto

Apuntes de Matemática Discreta
3. Principios Básicos de Conteo
Francisco José González Gutiérrez
Cádiz, Octubre de 2004
Universidad de Cádiz Departamento de Matemáticas
ii
Lección 3
Principios Básicos de Conteo
Contenido
3.1 Partición de un Conjunto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.1.1 Definición . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.1.2 Recubrimiento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.1.3 Cardinal de un conjunto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.2 Principio de Adición . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.2.1 Teorema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.2.2 Regla de la Suma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.3 Principio de Multiplicación . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.3.1 Teorema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.3.2 Regla del Producto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.4 Principio de Inclusión-Exclusión . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.4.1 Teorema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.4.2 Teorema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.4.3 Generalización del Principio de Inclusión-Exclusión . . . . . . . . . . . . . . . . 59
3.5 Principio de Distribución . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
3.5.1 Teorema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
3.5.2 Corolario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
Desarrollamos en esta lección los principios básicos para contar elementos de un conjunto, el de Adición,
el de Multiplicación, el de Inclusión-Exclusión y finalizaremos con el de Distribución.
3.1 Partición de un Conjunto
3.1.1 Definición
Dado un conjunto A, diremos que los subconjuntos de A, A1, A2, . . . , An, constituyen una partición
del mismo si se cumplen las siguientes condiciones:
1. Ai 6= ∅; ∀i = 1, 2, . . . . . . , n
2. Ai ∩Aj = ∅; ∀i 6= j, i, j = 1, 2, . . . . . . n
3. A1 ∪A2 ∪ · · · · · · ∪An = A
37
Universidad de Cádiz Departamento de Matemáticas
3.1.2 Recubrimiento
Si los subconjuntos B1, B2, . . . . . . , Bn de un conjunto A cumplen las condiciones 1. y 3. de la
definición anterior, diremos que B1, B2, . . . . . . , Bn constituyen un recubrimiento de A.
Ejemplo 3.1
A1
A2 A3
A4
A
Partición del conjunto A. Ejemplo 3.1
Los subconjuntos A1, A2, A3 y A4 constituyen una partición de A. �
Ejemplo 3.2 Si A = {a, b, c, d, e, f, g, h, i, j, k}, los conjuntos
A1 = {a, b, c, d}
A2 = {c, d, e, f, g}
A3 = {g, h, i}
A4 = {j, k}
constituyen un recubrimiento del conjunto A.
Solución
En efecto,
Ai 6= ∅; i = 1, 2, 3, 4
A1 ∪A2 ∪A3 ∪A4 = {a, b, c, d} ∪ {c, d, e, f, g} ∪ {g, h, i} ∪ {j, k} = {a, b, c, d, e, f, g, h, i, j, k} = A
38
Matemática Discreta Francisco José González Gutiérrez
Sin embargo no es una partición ya que, por ejemplo,
A1 ∩A2 = {a, b, c, d} ∩ {c, d, e, f} = {c, d} 6= ∅
�
3.1.3 Cardinal de un conjunto
Si A es un conjunto finito no vaćıo, designaremos por cardinal de A al número de elementos que tiene
A. Si A es el conjunto vaćıo, entonces su cardinal es cero. Lo notaremos |A|.
3.2 Principio de Adición
Estudiamos el más básico y simple de los principios para contar elementos de un conjunto.
3.2.1 Teorema
Si A1, A2, . . . , An es una colección de conjuntos finitos no vaćıos, disjuntos dos a dos, entonces
|A1 ∪A2 ∪ · · · ∪An| = |A1|+ |A2|+ · · ·+ |An|
Demostración
Procederemos por inducción sobre el número de conjuntos n.
Paso básico. Veamos que el teorema es cierto para n = 2.
En efecto, sean A1 y A2 dos conjuntos finitos tales que A1 ∩A2 = ∅. Pues bien, si
A1 = {a1, a2, . . . , aq} y A2 = {b1, b2, . . . , br}
al ser disjuntos no tendrán elementos comunes, de aqúı que
A1 ∪A2 = {a1, a2, . . . , aq, b1, b2, . . . , br}
luego,
|A1 ∪A2| = q + r = |A1|+ |A2|
y el teorema es cierto para n = 2.
Paso inductivo. Supongamos que el teorema es cierto para n = p, es decir, si A1, A2, . . . , Ap son una
familia de conjuntos finitos y disjuntos dos a dos, entonces∣∣∣∣∣
p⋃
i=1
Ai
∣∣∣∣∣ =
p∑
i=1
|Ai|
Veamos que el teorema es cierto para n = p + 1. En efecto, sea A1, A2, . . . , Ap, Ap+1 una familia de
conjuntos finitos y dos a dos disjuntos, entonces por la asociatividad de la unión de conjuntos,
p+1⋃
i=1
Ai = A1 ∪A2 ∪ · · · ∪Ap ∪Ap+1 = (A1 ∪A2 ∪ · · · ∪Ap) ∪Ap+1 =
(
p⋃
i=1
Ai
)
∪Ap+1
39
Universidad de Cádiz Departamento de Matemáticas
siendo, (
p⋃
i=1
Ai
)
∩Ap+1 = (A1 ∪A2 ∪ · · · ∪Ap) ∩Ap+1
= (A1 ∩Ap+1) ∪ (A2 ∩Ap+1) ∪ · · · ∪ (Ap ∩Ap+1)
= ∅ ∪ ∅ ∪ · · · ∪ ∅
= ∅
luego, ∣∣∣∣∣
p+1⋃
i=1
Ai
∣∣∣∣∣ =
∣∣∣∣∣
(
p⋃
i=1
Ai
)
∪Ap+1
∣∣∣∣∣
=
∣∣∣∣∣
p⋃
i=1
Ai
∣∣∣∣∣+ |Ap+1| {Paso básico}
=
p∑
i=1
|Ai|+ |Ap+1| {Hipótesis de inducción}
=
p+1∑
i=1
|Ai|
Consecuentemente, por el primer principio de inducción, la propiedad es cierta para todo entero positivo
n y,
|A1 ∪A2 ∪ · · · ∪An| = |A1|+ |A2|+ · · ·+ |An|
�
Obsérvese que en este tipo de problemas, la palabra “o” aparece o se sobrentiende impĺıcitamente. En
cualquier caso en el que tengamos una acción simple a realizar y que debe satisfacer una condición u otra
siendo las condiciones mutuamente excluyentes, utilizaremos normalmente el principio de adición. Este
primer principio del conteo puede expresarse como sigue:
3.2.2 Regla de la Suma
Si una primera tarea puede realizarse de m formas distintas, mientras que una segunda tarea puede
realizarse de n formas distintas, y no es posible realizar ambas tareas de manera simultánea, entonces,
para llevar a cabo cualquiera de ellas pueden utilizarse cualquiera de m + n formas.
Ejemplo 3.3 Se lanza al aire una moneda cuatro veces. ¿De cuántas formas distintas pueden obtenerse
una, dos, tres o cuatro caras?
Solución
Sea Ai el conjunto formado por todos los resultados posibles en los que aparezcan, exactamente, “i caras”
al lanzar cuatro veces la moneda. Entonces,
A1 = {(c, x, x, x), (x, c, x, x), (x, x, c, x), (x, x, x, c)}
A2 = {(c, c, x, x), (c, x, c, x), (c, x, x, c), (x, c, c, x), (x, c, x, c), (x, x, c, c)}
A3 = {(c, c, c, x), (c, c, x, c), (c, x, c, c), (x, c, c, c)}
A4 = {(c, c, c, c)}
y el conjunto A1 ∪ A2 ∪ A3 ∪ A4 estará formado por todos los resultados en los que aparecen una, dos,
tres o cuatro caras, por tanto el número pedido es el cardinal de dicho conjunto. Al ser los Ai dos a dos
disjuntos, por el principio de adición, tendremos que habrá
|A1 ∪A2 ∪A3 ∪A4| = |A1|+ |A2|+ |A3|+ |A4| = 15
40
Matemática Discreta Francisco José González Gutiérrez
formas distintas de obtener una, dos, tres o cuatro caras. �
3.3 Principio de Multiplicación
Este principio nos va a permitir resolver con más comodidad situaciones que involucren procesos que
consistan en acciones sucesivas.
Supongamos una acción que consista en una secuencia de pasos. Por ejemplo tirar un dado, luego otro
y a continuación un tercero. Diremos que los pasos son independientes si el número de formas en que
puede hacerse cada uno de ellos no depende del número de formas en que pueden realizarse cada uno de
los otros.
3.3.1 Teorema
Si A1, A2, . . . , An es una colección de conjuntos finitos no vaćıos, entonces
|A1 ×A2 × · · · ×An| = |A1| · |A2| · · · · · |An|
Demostración
Procederemos por inducción sobre el número de conjuntos, n.
Paso básico. Veamos si el teorema es cierto para n = 2. En efecto, sean A1 y A2 dos conjuntos finitos
no vaćıos,
A1 = {a1, a2, . . . , aq} y A2 = {b1, b2, . . . , br}
Por definición de producto cartesiano,
A1 ×A2 = {(ai, bj) : ai ∈ A1 y bj ∈ A2}
para cada uno de los ai, 1 6 i 6 q, tendremos los pares distintos,(ai, b1), (ai, b2), . . . , (ai, br)
es decir, r pares o r elementos de A1 ×A2. Haciendo lo mismo para cada uno de los ai ∈ Ai, 1 6 i 6 q,
tendremos
(a1, b1), (a1, b2), . . . , (a1, br)
(a2, b1), (a2, b2), . . . , (a2, br)
. . . . . . . . . . . . . . . . . . . . . . . . . . .
(aq, b1), (aq, b2), . . . , (aq, br)
o sea, un total de q · r pares distintos en A1 ×A2, luego
|A1 ×A2| = q · r = |A1| · |A2|
por tanto, la proposición es cierta para n = 2.
Paso inductivo. Supongamos que es cierta para n = p, es decir si A1, A2, . . . , Ap es una colección de
conjuntos finitos no vaćıos. Entonces,
|A1 ×A2 × · · · ×Ap| = |A1| · |A2| · · · · · |Ap|
Veamos si la proposición es cierta para n = p + 1. En efecto, si A1, A2, . . . , Ap, Ap+1 es una colección de
conjuntos finitos no vaćıos, entonces
|A1 ×A2 × · · · ×Ap ×Ap+1| = |(A1 ×A2 × · · · ×Ap)×Ap+1| {Asociatividad de ×}
= |A1 ×A2 × · · · ×Ap| · |Ap+1| {Paso básico}
= |A1| · |A2| · · · · · |Ap| · |Ap+1| {Paso inductivo}
41
Universidad de Cádiz Departamento de Matemáticas
Consecuentemente, por el Principio de inducción matemática, el teorema es cierto para todo entero
positivo, n, es decir,
|A1 ×A2 × · · · ×An| = |A1| · |A2| · · · · · |An|
�
Ejemplo 3.4 ¿Cuántos resultados distintos son posibles al tirar tres dados diferentes?
Solución
Sean A1, A2 y A3 los conjuntos formados por los posibles resultados que podamos obtener al tirar cada
uno de los tres dados, entonces |Ai| = 6, i = 1, 2, 3 y cada resultado es un elemento del producto
cartesiano A1 ×A2 ×A3, luego por el principio de multiplicación, habrá
|A1 ×A2 ×A3| = |A1| · |A2| · |A3| = 6 · 6 · 6 = 216
resultados distintos.
Obsérvese que al ser diferentes los dados, podemos etiquetarlos como primero, segundo y tercero y tratar
la tirada como una acción con tres pasos sucesivos, cada uno de las cuales tiene seis resultados posibles.
El número de posibilidades será, por tanto,
6 · 6 · 6 = 216
Obsérvese también que si los dados no fueran diferentes, la respuesta seŕıa distinta. Por ejemplo seŕıa
imposible distinguir entre el resultado 152 y el 251. �
Ejemplo 3.5 Un número de teléfono consta de siete d́ıgitos. Si la primera ha de ser un número entre
2 y 9, ambos inclusive, la segunda y la tercera han de ser números entre 1 y 9 ambos inclusive. ¿Cuántos
números de teléfono distintos pueden formarse con estas condiciones?
Solución
Sean los conjuntos,
A1 = {2, 3, 4, 5, 6, 7, 8, 9}
A2 = A3 = {1, 2, 3, 4, 5, 6, 7, 8, 9}
A4 = A5 = A6 = A7 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
El número de teléfonos con numeraciones distintas que pueden formarse son los del conjunto
A1 ×A2 ×A3 ×A4 ×A5 ×A6 ×A7
Por el principio de multiplicación,
|A1 ×A2 · · · ×A7| = |A1| · |A2| · |A3| · |A4| · |A5| · |A6| · |A7|
= 8 · 9 · 9 · 10 · 10 · 10 · 10
= 6.480.000
�
3.3.2 Regla del Producto
Si un procedimiento puede descomponerse en las etapas primera y segunda, y si existen m resultados
posibles de la primera etapa y si, para cada uno de estos resultados, existen n resultados posibles para
la segunda etapa, entonces el procedimiento entero puede realizarse, en el orden dado, de mn formas.
Ejemplo 3.6 Se dispone de una baraja de 40 cartas de la cual extraemos cuatro de dos formas difer-
entes:
42
Matemática Discreta Francisco José González Gutiérrez
(a) Sin devolución de cada carta extráıda.
(b) Con devolución de la carta en cada extracción.
Calcular el número de formas diferentes de obtener cuatro cartas en cada caso.
Solución
Consideraremos el experimento como una acción con cuatro pasos independientes.
(a) Para el primer paso tenemos 40 opciones posibles y como la carta extráıda no se devuelve quedarán
39 opciones para el segundo paso y, por la misma razón, 38 y 37 opciones para el tercero y el cuarto,
respectivamente. Aśı pues el experimento podrá hacerse de
40 · 39 · 38 · 37 = 2193360
formas distintas.
(b) Cada carta extráıda se devuelve a la baraja. Por tanto, para cada una de las cuatro extracciones
dispondremos de las cuarenta. Aśı pues, el número de formas diferentes de obtener las cuatro cartas
es
40 · 40 · 40 · 40 = 2560000
�
Ejemplo 3.7 Se lanzan dos dados, uno azul y otro rojo, a continuación se registra el resultado de cada
tirada.
(a) ¿En cuántos resultados la suma es 7 u 11?
(b) ¿En cuántos resultados uno y sólo uno de los dados muestra un 2?
(c) ¿En cuántos resultados ninguno de los dados muestra un 2?
Solución
(a) Sean a y b los resultados de los dados azul y rojo, respectivamente. Entonces,
a, b ∈ {1, 2, 3, 4, 5, 6}
y el par (a, b) puede considerarse como un par ordenado.
Pues bien, si A es el conjunto formado por todos los pares ordenados cuya suma sea 7 y B el
formado por aquellos que suman 11, entonces,
A = {(1, 6), (2, 5), (3, 4), (4, 3), (5, 2), (6, 1)}
B = {(5, 6), (6, 5)}
y el número de resultados en los cuales la suma es 7 u 11 será igual al cardinal de A∪B. Al ser A
y B disjuntos, por el principio de adición, habrá
|A ∪B| = |A|+ |B| = 8
resultados que cumplan las condiciones requeridas.
43
Universidad de Cádiz Departamento de Matemáticas
(b) Sean
A1 = {2}
B1 = {1, 3, 4, 5, 6}
y
A2 = {1, 3, 4, 5, 6}
B2 = {2}
donde Ai y Bi, i = 1, 2, representan, respectivamente, los resultados de los dados azul y rojo.
Entonces, todos los resultados en los cuales aparece un 2 en uno sólo de los dados, son los elementos
del conjunto
(A1 ×B1) ∪ (A2 ×B2)
siendo A1 ×B1 y A2 ×B2, disjuntos.
Consecuentemente, por el principio de adición y luego por el de multiplicación tendremos que el
número de resultados en los que uno sólo de los dados muestra un 2 es
|(A1 ×B1) ∪ (A2 ×B2)| = |A1 ×B1|+ |A2 ×B2|
= |A1| · |A2|+ |B1| · |B2|
= 1 · 5 + 1 · 5 = 10
(c) Utilizando los mismos conjuntos que en el apartado anterior, los resultados en los que ninguno de
los dos dados muestra un 2 son los elementos de A2×B1. Por el principio de multiplicación, habrá
|A2 ×B1| = |A2| · |B1| = 5 · 5 = 25
resultados que cumplen la condiciones pedidas. �
Ejemplo 3.8 Un viajante de comercio ha de visitar n ciudades sin pasar dos veces por ninguna de
ellas. ¿Cuántas rutas distintas puede tomar si el viaje ha de empezar y terminar en la ciudad A?
Solución
El viajante elige cualquiera de las n − 1 ciudades restantes para la primera visita, las opciones para la
segunda seŕıan n−2 y n−3 posibilidades para la siguiente. Seguimos aśı sucesivamente y por el principio
de multiplicación, el número de rutas distintas seŕıa:
(n− 1)(n− 2) · · · 3 · 2 · 1
Obsérvese que al contar de esta forma, el orden en que se visitan las ciudades es importante, es decir una
ruta tal como ABCDEFA es distinta de la AFEDCBA. Si las rutas que se recorren en sentidos inversos
las consideramos iguales, el número de posibilidades se reduciŕıa a:
(n− 1)(n− 2) · · · 3 · 2 · 1
2
es decir, la mitad de opciones. �
En el siguiente ejemplo, veremos una situación en la cual se mezclan los principios de adición y multipli-
cación.
Ejemplo 3.9 El viajante de comercio del ejemplo anterior ha de visitar cinco ciudades A,B,C,D y E,
teniendo su base en la ciudad A. ¿Cuántas rutas distintas puede tomar si no puede visitar la ciudad E
hasta después de haber visitado la B o la C?
Solución
Como la ciudad E no puede ser visitada hasta después de visitar B o C, la primera visita deberá ser a B
o a C o a D.
44
Matemática Discreta Francisco José González Gutiérrez
− Si la primera visita es a la ciudad B, entonces el viajante tiene tres opciones para la segunda, dos
para la siguiente y una para la última, luego por el principio de multiplicación hay
3 · 2 · 1 = 6
rutas distintas teniendo a B como la primera ciudad visitada.
− Si la primera ciudad visitada es C, un razonamiento idéntico al anterior ofrecerá al viajante el
mismo número de opciones, es decir, seis rutas distintas.
− Si la primera ciudad visitada es la D, entonces hay dos opciones para la segunda (B y C), dos
opciones para la siguiente y una para la última. Consecuentemente,el número de opciones distintas
es, en este caso, por el principio de multiplicación
2 · 2 · 1 = 4
Aśı pues, por el principio de adición existen un total de
6 + 6 + 4 = 16
rutas posibles que puede tomar el viajante. �
3.4 Principio de Inclusión-Exclusión
El principio de adición establećıa que si X es la unión de una colección de conjuntos A1, A2, . . . , An,
disjuntos dos a dos, entonces
|X| = |A1|+ |A2|+ · · ·+ |An| .
En muchas ocasiones, necesitaremos calcular el número de elementos de un conjunto X que es la unión
de una colección de conjuntos A1, A2, . . . , An que no sean disjuntos. El principio de inclusión-exclusión
nos dice como hacerlo en función del número de elementos de los conjuntos A1, A2, . . . , An.
En śıntesis, este principio nos dice que si sabemos contar elementos de intersecciones de conjuntos,
entonces podremos determinar el tamaño de la unión de dichos conjuntos.
3.4.1 Teorema
Sean A y B dos subconjuntos de un conjunto universal arbitrario, U . Entonces,
|A ∪B| = |A|+ |B| − |A ∩B|
Demostración
45
Universidad de Cádiz Departamento de Matemáticas
A ∪B
A
A \B A ∩B B \A
B
U
Principio de Inclusión-Exclusión
Intuitivamente, podemos justificar este teorema examinando la figura. Si sumamos el número de elemen-
tos que hay en A y en B, entonces contamos los elementos de A∩B dos veces. Aśı pues, para encontrar
el |A ∪B| debeŕıamos sumar |A| a |B| y restar |A ∩B|. Veamos una demostración formal.
Sea x un elemento cualquiera de U . Entonces,
x ∈ (A ∪B) ⇐⇒ (x ∈ A) ∨ (x ∈ B). (3.1)
Ahora bien, si un elemento x está en A, puede estar en A y no en B o en A y en B, es decir,
x ∈ A ⇐⇒ [(x ∈ A) ∧ (x /∈ B)] ∨ [(x ∈ A) ∧ (x ∈ B)]
o sea,
x ∈ A ⇐⇒ [x ∈ (A \B)] ∨ [x ∈ (A ∩B)] (3.2)
de aqúı que
A = (A \B) ∪ (A ∩B) (3.3)
También, si un elemento x está en B, razonando exactamente igual, tendremos
x ∈ B ⇐⇒ [x ∈ (B \A)] ∨ [x ∈ (A ∩B)] (3.4)
luego
B = (B \A) ∪ (A ∩B) (3.5)
Llevando los resultados (3.2) y (3.4) a (3.1), obtenemos
x ∈ (A ∪B) ⇐⇒ [x ∈ (A \B)] ∨ [x ∈ (A ∩B)] ∨ [x ∈ (B \A)] (3.6)
es decir, si un elemento pertenece a A ∪B, entonces puede estar en A y no en B o en B o en A y en B
o en B y no en A.
46
Matemática Discreta Francisco José González Gutiérrez
De (3.6) se sigue directamente que
A ∪B = (A \B) ∪ (A ∩B) ∪ (B \A) . (3.7)
Además,
(A \B) ∩ (A ∩B) = (A ∩Bc) ∩ (A ∩B)
= A ∩ (Bc ∩B)
= A ∩ ∅
= ∅
(A \B) ∩ (B \A) = (A ∩Bc) ∩ (B ∩Ac)
= A ∩Bc ∩B ∩Ac
= A ∩ ∅ ∩Ac
= ∅
(A ∩B) ∩ (B \A) = (A ∩B) ∩ (B ∩Ac)
= A ∩B ∩Ac
= A ∩Ac ∩B
= ∅
es decir, los tres conjuntos son disjuntos dos a dos, por lo tanto (3.3), (3.5) y (3.7) son, respectivamente,
descomposiciones de los conjuntos A, B y A ∪B en unión de subconjuntos disjuntos, de aqúı que por el
principio de adición,
|A| = |A \B|+ |A ∩B| =⇒ |A \B| = |A| − |A ∩B|
|B| = |B \A|+ |A ∩B| =⇒ |B \A| = |B| − |A ∩B|
|A ∪B| = |A \B|+ |A ∩B|+ |B \A|
y sustituyendo los dos primeros resultados en la tercera igualdad,
|A ∪B| = |A| − |A ∩B|+ |B| − |A ∩B|+ |A ∩B| = |A|+ |B| − |A ∩B|
�
Ejemplo 3.10 De un grupo de programadores, 35 están familiarizados con ordenadores del tipo A, 41
con ordenadores del tipo B y 46 con algunos de los dos. ¿Cuántos están familiarizados con ambos?
Solución
Sea P el conjunto de todos los programadores y sean A y B los subconjuntos de P formados por los
que están familiarizados con los ordenadores de tipo A y tipo B, respectivamente. Los que lo están con
ambos son, por tanto, los del conjunto A ∩B. Pues bien, según los datos del enunciado,
|A| = 35
|B| = 41
|A ∪B| = 46.
Aplicando el principio de inclusión-exclusión,
|A ∪B| = |A|+ |B| − |A ∩B| =⇒ |A ∩B| = 35 + 41− 46 = 30
Hay, por tanto, 30 programadores que están familiarizados con ambos tipos de ordenadores. �
Ejemplo 3.11 Los 100 alumnos de una facultad se han examinado de Matemática Discreta y de Lógica
Matemática, obteniendo los siguientes resultados en los exámenes.
47
Universidad de Cádiz Departamento de Matemáticas
20 alumnos no han aprobado ninguna de las dos asignaturas.
Han aprobado las dos asignaturas un total de 25 personas.
El número de alumnos que han aprobado Matemática discreta es el doble de los que han aprobado
el Lógica Matemática.
¿Cuántos alumnos aprobaron únicamente Matemática discreta?
¿Cuántos alumnos aprobaron únicamente Lógica Matemática?
Solución
Un diagrama de Venn que refleja la situación planteada en el ejercicio es el de la figura, donde D y
L son los conjuntos cuyos elementos son los alumnos que han aprobado Matemática Discreta y Lógica
Matemática, respectivamente.
Dc ∩ Lc
D
D ∩ Lc D ∩ L Dc ∩ L
L
U
Ejemplo 3.11
Los alumnos que han aprobado una de las dos asignaturas puede que no hayan aprobado la otra o que
si la hayan aprobado, luego
D = (D ∩ Lc) ∪ (D ∩ L),
L = (D ∩ L) ∪ (Dc ∩ L)
y
D ∪ L = (D ∩ Lc) ∪ (D ∩ L) ∪ (Dc ∩ L)
donde
(D ∩ Lc) ∩ (D ∩ L) = D ∩ Lc ∩ L = D ∩ ∅ = ∅
48
Matemática Discreta Francisco José González Gutiérrez
y
(D ∩ L) ∩ (Dc ∩ L) = D ∩Dc ∩ L = ∅ ∩D = ∅
de aqúı que por el Principio de Adición,
|D| = |D ∩ Lc| + |D ∩ L|
|L| = |D ∩ L| + |Dc ∩ L|
|D ∪ L| = |D ∩ Lc| + |D ∩ L| + |Dc ∩ L| .
Por otra parte, si llamamos U al conjunto formado por los 100 alumnos,
U = (D ∪ L) ∪ (D ∪ L)c
donde,
(D ∪ L) ∪ (D ∪ L)c = ∅
de aqúı que nuevamente por el Principio de Adición,
|U | = |D ∪ L|+ |(D ∪ L)c|
Pues bien, según los datos aportados por el enunciado:
X 20 alumnos no han aprobado ninguna de las dos asignaturas, es decir,
|(D ∪ L)c| = 20.
luego
|D ∪ L| = 100− 20 = 80.
X Han aprobado las dos asignaturas un total de 25 personas, o sea,
|D ∩ L| = 25
X El número de alumnos que han aprobado Matemática discreta es el doble de los que han aprobado
el Lógica Matemática, es decir,
|D| = 2 |L| .
Datos que sustituidos en las ecuaciones anteriores, nos llevan a
2 |L| = |D ∩ Lc| + 25
|L| = 25 + |Dc ∩ L|
80 = |D ∩ Lc| + 25 + |Dc ∩ L| .
de aqúı que
|D ∩ Lc| = 45
|Dc ∩ L| = 10
luego hay 45 alumnos que han aprobado únicamente la Matemática Discreta y 10 que aprobaron únicamente
el Lógica Matemática. �
3.4.2 Teorema
Sean A,B y C tres subconjuntos de un conjunto universal arbitrario, U . Entonces,
|A ∪B ∪ C| = |A|+ |B|+ |C| − |A ∩B| − |A ∩ C| − |B ∩ C|+ |A ∩B ∩ C|
Demostración
49
Universidad de Cádiz Departamento de Matemáticas
Apoyándonos en el teorema anterior y en la distributividad de la intersección respecto a la unión de
conjuntos,
|A ∪B ∪ C| = |A ∪ (B ∪ C)|
= |A|+ |B ∪ C| − |A ∩ (B ∪ C)|
= |A|+ |B|+ |C| − |B ∩ C| − |(A ∩B) ∪ (A ∩ C)|
= |A|+ |B|+ |C| − |B ∩ C| − (|A ∩B|+ |A ∩ C| − |(A ∩B) ∩ (A ∩ C)|)
= |A|+ |B|+ |C| − |A ∩B| − |A ∩ C| − |B ∩ C|+ |A ∩B ∩ C|
�
Ejemplo 3.12 ¿Cuántos números existen entre 1 y 1000, ambos inclusive, que no sean ni cuadrados
perfectos, ni cubos perfectos ni cuartas potencias?
Solución
Sea Z el conjunto de todos los enteros entre 1 y 1000 y sean A1, A2 y A3 los subconjuntos de Z formados
por los cuadrados perfectos, los cubos perfectos y las cuartas potencias, respectivamente. Entonces,
A1 =
{
x : x = n2, n ∈ Z
}
A2 =
{
x : x = n3, n ∈ Z
}
A3 =
{
x : x = n4, n ∈ Z
}
Pues bien,
312 = 961 < 1000 y 322 = 1024 > 1000, luego |A1| = 31
103 = 1000, luego |A2| = 10
54 = 625 y 64 = 1296, luego |A3| = 5
Observemos ahora lo siguiente:
A1 ∩A2 =
{
x : ∃n ∈ Z+; x = n2 y x = n3
}
=
{
x : ∃n ∈ Z; x = n6
}
y al ser 36 = 729 < 1000 y 46 = 4096 > 1000, tendremos que |A1 ∩A2| = 3.
Por otra parte,
x ∈ A3 ⇐⇒ x = n4, n ∈ Z =⇒ x =
(
n2
)2
, n ∈ Z ⇐⇒ x ∈ A1
es decir cada cuarta potencia es también un cuadrado, luego A3 ⊆ A1 y, por tanto, A1 ∩ A3 = A3 y
|A1 ∩A3| = 5. También,
A2 ∩A3 =
{
x : x = n3 y x = n4, n ∈ Z+
}
=
{
x : x = n12, n ∈ Z+
}
luego el conjunto A2 ∩ A3 estará formado por todos los números que son a un tiempo, cubos y cuartas
potencias, es decir son de la forma n12 para algún entero n y al ser 212 = 4096 > 1000, tendremos que
|A2 ∩A3| = 1.
Finalmente,
x ∈ A2 ∩A3 ⇐⇒ x = n12 =⇒ x =
(
n6
)2
, n ∈ Z ⇐⇒ x ∈ A1
luegolas doceavas potencias son también cuadrados, es decir, A2 ∩A3 ⊆ A1 de aqúı que
A1 ∩A2 ∩A3 = A2 ∩A3
50
Matemática Discreta Francisco José González Gutiérrez
y
|A1 ∩A2 ∩A3| = 1
Con todos estos datos,
|A1 ∪A2 ∪A3| = |A1|+ |A2|+ |A3| − |A1 ∩A2| − |A1 ∩A3| − |A2 ∩A3|+ |A1 ∩A2 ∩A3|
= 31 + 10 + 5− 3− 5− 1 + 1
= 38
Consecuentemente, el número de enteros entre 1 y 1000 que no son cuadrados, cubos o cuartas potencias
son 1000− 38 = 962. �
Ejemplo 3.13 Demostrar que
|A ∪B ∪ C| = |A \ (B ∪ C)| + |B \ (A ∪ C)| + |C \ (A ∪B)|
+ |(A ∩B) \ C| + |(A ∩ C) \B| + |(B ∩ C) \A|
+ |A ∩B ∩ C|
donde A,B y C están incluidos en un universal arbitrario U .
Solución
En efecto, sea x un elemento arbitrario de U . Entonces
x ∈ (A ∪B ∪ C) ⇐⇒ (x ∈ A) ∨ (x ∈ B) ∨ (x ∈ C) .
Pues bien, si x está en A, entonces puede estar en A y no estar en B ni en C, o estar en A y en B pero
no estar en C o estar en A y en C pero no en B o estar en A, en B y en C (la situación planteada puede
apreciarse con claridad en la figura), es decir,
C \ (A ∪B) (B ∩ C) \A B \ (A ∪ C)
A ∩B ∩ C
A \ (B ∪ C)
(A ∩ C) \B (A ∩B) \ C
A
C B
U
Ejemplo 3.13
51
Universidad de Cádiz Departamento de Matemáticas
x ∈ A ⇐⇒ [(x ∈ A) ∧ (x /∈ B) ∧ (x /∈ C)] ∨ [(x ∈ A) ∧ (x ∈ B) ∧ (x /∈ C)]
∨ [(x ∈ A) ∧ (x /∈ B) ∧ (x ∈ C)]
∨ [(x ∈ A) ∧ (x ∈ B) ∧ (x ∈ C)]
⇐⇒ [(x ∈ A) ∧ (x ∈ Bc) ∧ (x ∈ Cc)] ∨ [(x ∈ A) ∧ (x ∈ B) ∧ (x ∈ Cc)]
∨ [(x ∈ A) ∧ (x ∈ Bc) ∧ (x ∈ C)]
∨ [(x ∈ A) ∧ (x ∈ B) ∧ (x ∈ C)]
⇐⇒ [x ∈ (A ∩Bc ∩ Cc)] ∨ [x ∈ (A ∩B ∩ Cc)] ∨ [x ∈ (A ∩Bc ∩ C)] ∨ [x ∈ (A ∩B ∩ C)]
de aqúı que
A = (A ∩Bc ∩ Cc) ∪ (A ∩B ∩ Cc) ∪ (A ∩Bc ∩ C) ∪ (A ∩B ∩ C)
y razonando de forma análoga para los conjuntos B y C, tendremos
B = (Ac ∩B ∩ Cc) ∪ (A ∩B ∩ Cc) ∪ (Ac ∩B ∩ C) ∪ (A ∩B ∩ C)
y
C = (Ac ∩Bc ∩ C) ∪ (A ∩Bc ∩ C) ∪ (Ac ∩B ∩ C) ∪ (A ∩B ∩ C) .
Si ahora unimos los tres, tendremos que
A ∪B ∪ C = (A ∩Bc ∩ Cc) ∪ (A ∩B ∩ Cc) ∪ (A ∩Bc ∩ C) ∪ (A ∩B ∩ C)
∪ (Ac ∩B ∩ Cc) ∪ (Ac ∩B ∩ C) ∪ (Ac ∩Bc ∩ C) .
Además, en cada pareja de conjuntos que tomemos, en uno de sus miembros aparece un conjunto y en
el otro su complementario, por lo tanto su intersección es vaćıa. Por ejemplo,
(A ∩Bc ∩ Cc) ∩ (A ∩B ∩ Cc) = A ∩Bc ∩ Cc ∩A ∩B ∩ Cc = A ∩Bc ∩B ∩ Cc = A ∩ ∅ ∩ Cc = ∅.
Consecuentemente, la igualdad que obtuvimos anteriormente es una descomposición de A ∪ B ∪ C en
unión de conjuntos disjuntos y aplicando el principio de adición, tendremos que
|A ∪B ∪ C| = |A ∩Bc ∩ Cc| + |A ∩B ∩ Cc| + |A ∩Bc ∩ C| + |A ∩B ∩ C|
+ |Ac ∩B ∩ Cc| + |Ac ∩B ∩ C| + |Ac ∩Bc ∩ C|
y ahora bastaŕıa aplicar las leyes de De Morgan y la definición de diferencia de conjuntos para obtener
el resultado,
|A ∪B ∪ C| = |A \ (B ∪ C)| + |B \ (A ∪ C)| + |C \ (A ∪B)|
+ |(A ∩B) \ C| + |(A ∩ C) \B| + |(B ∩ C) \A|
+ |A ∩B ∩ C|
�
Ejemplo 3.14 Una encuesta realizada entre 200 personas arrojó el resultado siguiente:
40 leen Diario de Cádiz.
42 leen El Mundo.
45 leen El Páıs.
13 leen Diario de Cádiz y El Mundo.
20 leen El Mundo y El Páıs.
18 leen Diario de Cádiz y El Páıs.
7 leen los tres periódicos.
52
Matemática Discreta Francisco José González Gutiérrez
(a) ¿Cuántas personas no leen ninguno de los tres periódicos?
(b) ¿Cuántas personas leen únicamente el Diario de Cádiz?
(c) ¿Cuántas personas leen un sólo periódico?
Solución
Un diagrama de Venn de la situación planteada se muestra en la figura.
U
D
MP
D ∩M c ∩ P c
D ∩M c ∩ P D ∩M ∩ P c
D ∩M ∩ P
Dc ∩M c ∩ P Dc ∩M ∩ P Dc ∩M ∩ P c
Dc ∩M c ∩ P c
Ejemplo 3.14
Sea U el conjunto formado por todas las personas encuestadas y sean D,M y P los conjuntos formados
por las personas que leen Diario de Cádiz, El Mundo y El Páıs, respectivamente. Según los datos del
enunciado
|D| = 40
|M | = 42
|P | = 45
|D ∩M | = 13
|M ∩ P | = 20
|D ∩ P | = 18
|D ∩M ∩ P | = 7
53
Universidad de Cádiz Departamento de Matemáticas
(a) Veamos cuántas personas no leen ninguno de los tres periódicos.
El conjunto D∪M ∪P está formado por las personas que leen, al menos, uno de los tres periódicos,
luego el conjunto de las personas que no leen ninguno de los tres periódicos será su complementario
(D ∪M ∪ P )c y al ser D∪M ∪P y (D ∪M ∪ P )c disjuntos, por el principio de adición, tendremos
|U | = |(D ∪M ∪ P ) ∪ (D ∪M ∪ P )c| = |D ∪M ∪ P |+ |(D ∪M ∪ P )c|
de aqúı que
|(D ∪M ∪ P )c| = |U | − |D ∪M ∪ P | .
Por el principio de inclusión-exclusión para tres conjuntos, tendremos
|D ∪M ∪ P | = |D|+ |M |+ |P | − |D ∩M | − |M ∩ P | − |D ∩ P |+ |D ∩M ∩ P |
= 40 + 42 + 45− 13− 20− 18 + 7
= 134− 51
= 83
por lo tanto,
|(D ∪M ∪ P )c| = 200− 83 = 117
(b) Calculemos ahora el número de personas que leen únicamente Diario de Cádiz.
Las personas que leen únicamente Diario de Cádiz serán aquellas que lean Diario de Cádiz y no
lean El Mundo ni El Páıs, es decir las del conjunto D ∩ M c ∩ P c. Para calcular el número de
estas personas, y teniendo en cuenta los datos que proporciona el enunciado, habrá que hacerlo en
función de |D|, |D ∩M |, |D ∩ P | y |D ∩M ∩ P |.
Pues bien, las personas que leen Diario de Cádiz puede que lean alguno de los otros dos periódicos
(D ∩ (M ∪ P )) o que no lean ninguno de los otros dos (D ∩ (M ∪ P )c), es decir,
D = [D ∩ (M ∪ P )] ∪ [D ∩ (M ∪ P )c]
siendo esta descomposición en unión de disjuntos. Aplicando el principio de adición y, posterior-
mente, el de inclusión-exclusión,
|D| = |D ∩ (M ∪ P )|+ |D ∩ (M ∪ P )c|
= |(D ∩M) ∪ (D ∩ P )|+ |D ∩M c ∩ P c|
= |D ∩M |+ |D ∩ P | − |D ∩M ∩ P |+ |D ∩M c ∩ P c|
de donde,
|D ∩M c ∩ P c| = |D| − |D ∩M | − |D ∩ P |+ |D ∩M ∩ P | = 40− 13− 18 + 7 = 16
(c) Veamos ahora cuántas personas leen un sólo periódico.
Las personas que leen únicamente un sólo periódico serán aquellas que lean únicamente Diario de
Cádiz (ni El Mundo, ni El Páıs) o que únicamente lean El Mundo (ni Diario de Cádiz ni El Páıs)
o que lean únicamente El Páıs (ni Diario de Cádiz ni El Mundo), es decir las del conjunto
(D ∩M c ∩ P c) ∪ (Dc ∩M ∩ P c) ∪ (Dc ∩M c ∩ P )
y como estos tres conjuntos son disjuntos dos a dos, por el principio de adición, tendremos
|(D ∩M c ∩ P c) ∪ (Dc ∩M ∩ P c) ∪ (Dc ∩M c ∩ P )| = |D ∩M c ∩ P c|+ |Dc ∩M ∩ P c|
+ |Dc ∩M c ∩ P | (3.8)
El primero de los sumandos lo hemos calculado en el apartado anterior.
Si seguimos un camino análogo para calcular los otros dos, tendremos:
|Dc ∩M ∩ P c| = |M | − |M ∩ P | − |D ∩M |+ |D ∩M ∩ P | = 42− 20− 13 + 7 = 16 (3.9)
54
Matemática Discreta Francisco José González Gutiérrez
y
|Dc ∩M c ∩ P | = |P | − |M ∩ P | − |D ∩ P |+ |D ∩M ∩ P | = 45− 20− 18 + 7 = 14. (3.10)
Sustituyendo (3.9) y (3.10) junto con el resultado obtenido en el apartado anterior en (3.8) ten-
dremos que el número de personas que leen únicamente un periódico es
|(D ∩M c ∩ P c) ∪ (Dc ∩M ∩ P c) ∪ (Dc ∩M c ∩ P )| = 16 + 16 + 14 = 46
�
Ejemplo 3.15 Se ha comprado un lote de banderas monocolores, bicolores y tricolores. En todas ellas
figura, al menos, el blanco, el rojo o el negro. Además, en ocho de ellas no figura el blanco, en diez
no figura el rojo y en cuatro no figura el negro. Por otra parte, cinco banderas tienen, al menos, los
colores rojo y blanco, siete el blanco y el negro y seis el rojo y el negro. Finalmente, cuatro tienen los
tres colores. Averiguar:
(a) Número total de banderas.
(b) Número de monocolores rojas.
Solución
Sean
B: Conjunto formado por las banderas en las que figura, al menos, el blanco.
N : Conjunto formado por las banderas en las que figura, al menos, el negro.
R: Conjunto formado por las banderas en las que figura, al menos, el rojo.
(a) Número total de banderas.
Como en todas las banderas figura, al menos, uno de los tres colores, el número total de banderas
será el cardinal del conjunto B ∪R ∪N .
Veamos que datos aporta el enunciado.
X En ocho de ellas no figura el blanco. Entonces,
|Bc| = 8
X En diez de ellas no figura el rojo, es decir,
|Rc| = 10
X En cuatro de ellas no figura el negro, luego,
|N c| = 4
X Cinco tienen, al menos, los colores rojo y blanco.Pues bien,
|B ∩R| = 5
X Siete tienen, al menos, los colores blanco y negro, o sea,
|B ∩N | = 7
55
Universidad de Cádiz Departamento de Matemáticas
X Seis tienen, al menos, los colores rojo y negro, es decir,
|R ∩N | = 6
X Cuatro tienen los tres colores, es decir,
|B ∩R ∩N | = 4.
A la vista de estos datos parece que lo más lógico es utilizar el principio de inclusión-exclusión
para 3 conjuntos:
|B ∪N ∪R| = |B|+ |N |+ |R| − |B ∩N | − |B ∩R| − |N ∩R|+ |B ∩N ∩R|
y utilizando el principio de adición,
B ∪Bc = B ∪N ∪R =⇒ |B|+ |Bc| = |B ∪N ∪R| =⇒ |B| = |B ∪N ∪R| − |Bc|
N ∪N c = B ∪N ∪R =⇒ |N |+ |N c| = |B ∪N ∪R| =⇒ |N | = |B ∪N ∪R| − |N c|
R ∪Rc = B ∪N ∪R =⇒ |R|+ |Rc| = |B ∪N ∪R| =⇒ |R| = |B ∪N ∪R| − |Rc|
Si ahora sustituimos estos resultados en la igualdad anterior,
−2 |B ∪N ∪R| = − |Bc| − |N c| − |Rc| − |B ∩N | − |B ∩R| − |N ∩R|+ |B ∩N ∩R|
de donde se sigue que el número total de banderas es
|B ∪N ∪R| = |B
c|+ |N c|+ |Rc|+ |B ∩N |+ |B ∩R|+ |N ∩R| − |B ∩N ∩R|
2
=
8 + 10 + 4 + 5 + 7 + 6− 4
2
= 18
B
RN
B \ (N ∪R)
(B ∩N) \R (B ∩R) \N
B ∩R ∩N
N \ (B ∪R) (R ∩N) \B R \ (B ∪N)
Ejemplo 3.15
56
Matemática Discreta Francisco José González Gutiérrez
(b) Número de monocolores rojas.
El conjunto de banderas que tienen únicamente el color rojo es R \ (B ∪N) o Bc ∩N c ∩R. Pues
bien las banderas que tienen el color rojo, puede que tengan, además, uno de los otros dos colores
o ninguno de los dos, es decir,
R = [R ∩ (B ∪N)] ∪ [R ∩ (B ∪N)c]
siendo ésta una descomposición de R en unión de subconjuntos disjuntos. Aplicando el principio
de adición y el principio de inclusión-exclusión,
|R| = |R ∩ (B ∪N)|+ |R ∩ (B ∪N)c|
= |(B ∩R) ∪ (N ∩R)|+ |Bc ∩N c ∩R|
= |B ∩R|+ |N ∩R| − |B ∩N ∩R|+ |Bc ∩N c ∩R|
si ahora sustituimos |R| por |B ∪N ∪R| − |Rc| y despejamos,
|Bc ∩N c ∩R| = |B ∪N ∪R| − |Rc| − |N ∩R| − |B ∩R|+ |B ∩N ∩R|
= 18− 10− 6− 5 + 4
= 1
luego hay una sola bandera de color rojo. �
Ejemplo 3.16 En una muestra de 1000 individuos elegida para el estudio las preferencias gastronómicas
de una población, se observa que sesenta comen pescado y carne pero no huevos, cuarenta comen pescado
y huevos pero no carne, treinta carne y huevos pero no pescado, cincuenta comen únicamente pescado,
cuarenta sólo carne y treinta comen únicamente, huevos. Todos comen al menos, una de las tres cosas.
(a) ¿Cuántos comen las tres cosas?
(b) ¿Cuántos comen pescado?
Solución
Sean C,H y P los conjuntos formados por los individuos que comen, respectivamente, carne, huevos y
pescado.
(a) Los individuos que comen las tres cosas serán los del conjunto C ∩ H ∩ P es decir, tenemos que
calcular |C ∩H ∩ P |.
Descompondremos el conjunto C∪H∪P en unión de conjuntos disjuntos, para lo cual razonaremos
igual que en los ejercicios anteriores. En efecto, si un individuo come una de las tres cosas, puede
que coma también las otras dos, una o ninguna. Por ejemplo, si come carne, puede que también
coma huevos y pescado o huevos y no coma pescado o pescado y no coma huevos o que no coma
huevos ni pescado. Esto en términos de los conjuntos C,H y P quiere decir lo siguiente:
C = (C ∩H) ∪ (C ∩Hc)
= (C ∩H ∩ P ) ∪ (C ∩H ∩ P c) ∪ (C ∩Hc ∩ P ) ∪ (C ∩Hc ∩ P c)
H = (C ∩H) ∪ (Cc ∩H)
= (C ∩H ∩ P ) ∪ (C ∩H ∩ P c) ∪ (Cc ∩H ∩ P ) ∪ (Cc ∩H ∩ P c)
P = (C ∩ P ) ∪ (Cc ∩ P )
= (C ∩H ∩ P ) ∪ (C ∩Hc ∩ P ) ∪ (Cc ∩H ∩ P ) ∪ (Cc ∩Hc ∩ P )
57
Universidad de Cádiz Departamento de Matemáticas
y si ahora unimos los tres, tendremos que
C ∪H ∪ P = (C ∩H ∩ P ) ∪ (C ∩H ∩ P c) ∪ (C ∩Hc ∩ P ) ∪ (C ∩Hc ∩ P c)
∪ (Cc ∩H ∩ P ) ∪ (Cc ∩Hc ∩ P ) ∪ (Cc ∩H ∩ P c) .
Donde, como siempre, los conjuntos que integran el segundo miembro son disjuntos dos a dos ya
que en cada pareja que elijamos figura un conjunto en uno de sus miembros y su complementario
en el otro. Tenemos, por tanto, una descomposición de C ∪H ∪P en unión de conjuntos disjuntos,
luego por el principio de adición,
|C ∪H ∪ P | = |C ∩H ∩ P | + |C ∩H ∩ P c| + |C ∩Hc ∩ P | + |C ∩Hc ∩ P c|
+ |Cc ∩H ∩ P | + |Cc ∩Hc ∩ P | + |Cc ∩H ∩ P c| .
La situación se refleja en la figura.
C
HP
C ∩Hc ∩ P c
C ∩Hc ∩ P C ∩H ∩ P c
C ∩H ∩ P
Cc ∩Hc ∩ P Cc ∩H ∩ P Cc ∩H ∩ P c
Ejemplo 3.16
Observemos ahora los datos que proporciona el enunciado.
> Sesenta comen pescado y carne pero no huevos. Entonces,
|C ∩Hc ∩ P | = 60
> Cuarenta comen pescado y huevos pero no carne, es decir,
|Cc ∩H ∩ P | = 40
> Treinta comen carne y huevos pero no comen carne, o sea,
|C ∩H ∩ P c| = 30
58
Matemática Discreta Francisco José González Gutiérrez
> Cincuenta comen únicamente pescado. Entonces,
|Cc ∩Hc ∩ P | = 50
> Cuarenta comen sólo carne, o sea,
|C ∩Hc ∩ P c| = 40
> Treinta comen sólo huevos. Entonces,
|Cc ∩H ∩ P c| = 30
> Todos comen, al menos, una de las tres cosas.
|C ∪H ∪ P | = 1000
Sustituyendo estos datos en la expresión de |C ∪H ∪ P | que teńıamos al principio,
|C ∪H ∪ P | = |C ∩H ∩ P | + |C ∩H ∩ P c| + |C ∩Hc ∩ P | + |C ∩Hc ∩ P c|
+ |Cc ∩H ∩ P | + |Cc ∩Hc ∩ P | + |Cc ∩H ∩ P c| .
se sigue que
1000 = |C ∩H ∩ P | + 30 + 60 + 40 + 40 + 50 + 30
de aqúı que los individuos que comen las tres cosas sean,
|C ∩H ∩ P | = 750
(b) Los individuos que comen pescado son los del conjunto P , y según vimos anteriormente, una
descomposición de este conjunto en unión de subconjuntos disjuntos era:
P = (C ∩H ∩ P ) ∪ (C ∩Hc ∩ P ) ∪ (Cc ∩H ∩ P ) ∪ (Cc ∩Hc ∩ P )
luego por el principio de adición,
|P | = |C ∩H ∩ P | + |C ∩Hc ∩ P | + |Cc ∩H ∩ P | + |Cc ∩Hc ∩ P |
= 750 + 60 + 40 + 50
= 900
Aśı pues, son 900 los individuos que comen pescado. �
En los dos teoremas anteriores hemos probado el principio de inclusión-exclusión para dos y tres con-
juntos. Se puede generalizar a n conjuntos, aunque para hacerlo se necesitan coeficientes binomiales.
3.4.3 Generalización del Principio de Inclusión-Exclusión
Sean A1, A2, . . . , An subconjuntos de algún universal U . Entonces,∣∣∣∣∣
n⋃
i=1
Ai
∣∣∣∣∣ =
n∑
i=1
|Ai| −
∑
i,j
|Ai ∩Aj |+
∑
i,j,k
|Ai ∩Aj ∩Aj |+ · · ·+ (−1)n−1
∣∣∣∣∣
n⋂
i=1
Ai
∣∣∣∣∣
Ejemplo 3.17 En una encarnizada batalla al menos el 70% de los combatientes pierde un ojo, al menos
un 75% pierden una oreja, como mı́nimo un 80% pierde un brazo y al menos el 85% una pierna.
¿Cuántos han perdido por lo menos, las cuatro cosas?
Solución
Sean
59
Universidad de Cádiz Departamento de Matemáticas
U . Conjunto de todos los combatientes en la batalla.
O. Conjunto de los combatientes que pierden un ojo.
J . Conjunto de los combatientes que pierden una oreja.
B. Conjunto de los combatientes que pierden un brazo.
P . Conjunto de los combatientes que pierden una pierna.
Según los datos del ejercicio,
~ Al menos el 70% pierde un ojo =⇒ |O| > 70 |U |
100
~ Al menos el 75% pierden una oreja =⇒ |J | > 75 |U |
100
~ Como mı́nimo el 80% pierden un brazo =⇒ |B| > 80 |U |
100
~ Al menos el 85% pierden una pierna =⇒ |P | > 85 |U |
100
Tenemos que calcular el tanto por ciento mı́nimo del |O ∩ J ∩B ∩ P |.
Pues bien, por el principio de inclusión-exclusión,
|(O ∩ J) ∪ (B ∩ P )| = |O ∩ J |+ |B ∩ P | − |O ∩ J ∩B ∩ P |
de aqúı que
|O ∩ J ∩B ∩ P | = |O ∩ J |+ |B ∩ P | − |(O ∩ J) ∪ (B ∩ P )| (3.11)
Ahora bien, es obvio que
|(O ∩ J) ∪ (B ∩ P )| 6 |U |
y
|O ∩ J | = |O|+ |J | − |O ∪ J | > 70 |U |
100
+
75 |U |
100
− |U |
análogamente,
|B ∩ P | = |B|+ |P | − |B ∪ P | > 80 |U |
100
+
85 |U |
100
− |U |
y llevando estos resultados a (3.11), tendremos
|O ∩ J ∩B ∩ P | > 310 |U |
100
− 3 |U | = 10 |U |
100
luego al menos un 10% de los combatientes han perdido las tres cosas. �
Ejemplo 3.18 Se lanzan tres monedas simultáneamente al aire, realizándose este experimento 100
veces. La de 100 ptas. muestra cara en 70 ocasiones, la de 50 ptas. muestra cara 50 ocasiones y 56 veces
ha salido cara en la de 25 ptas. Las de 100 ptas. y 50 ptas. obtienen cara simultáneamente 31 veces, y
las de 50 y 25 ptas. han dado cara simultáneamente en 28 ocasiones. Demostrar que las tres monedas
mostraron cara simultáneamente en 9 veces al menos, y quelas tres han mostrado simultáneamente cruz
11 veces como máximo.
Solución
Llamaremos Ai, i = 1, 2, 3, 4, 5, 6, 7, 8 al conjunto cuyos elementos son los posibles resultados del lanza-
miento de las tres monedas en cada uno de los 100 lanzamientos. La tabla siguiente muestra la situación.
(c significa cara y x cruz)
60
Matemática Discreta Francisco José González Gutiérrez
100 50 25
A1 c c c
A2 c c x
A3 c x c
A4 c x x
A5 x c c
A6 x c x
A7 x x c
A8 x x x
Si |U | es el conjunto formado por todos los resultados posibles en los 100 lanzamientos, tendremos que
U =
8⋃
i=1
Ai : Ai ∩Aj = ∅, ∀i 6= j
luego por el principio de adición,
|U | =
∣∣∣∣∣
8⋃
i=1
Ai
∣∣∣∣∣ =⇒
8∑
i=1
|Ai| = 100
Pues bien, de los datos del ejercicio,
} La de 100 ptas. muestra cara en 70 ocasiones, luego
|A1 ∪A2 ∪A3 ∪A4| = 70 =⇒ |A1|+ |A2|+ |A3|+ |A4| = 70
} La de 50 ptas. muestra cara en 50 ocasiones, luego
|A1 ∪A2 ∪A5 ∪A6| = 50 =⇒ |A1|+ |A2|+ |A5|+ |A6| = 50
} 56 veces ha salido cara en la de 25 ptas., luego
|A1 ∪A3 ∪A5 ∪A7| = 56 =⇒ |A1|+ |A3|+ |A5|+ |A7| = 56
} Las de 100 ptas. y 50 ptas. obtienen cara simultáneamente 31 veces, luego
|A1 ∪A2| = 31 =⇒ |A1|+ |A2| = 31
} Las de 50 y 25 ptas. han dado cara simultáneamente en 28 ocasiones, luego
|A1 ∪A5| = 28 =⇒ |A1|+ |A5| = 28
Pues bien,
|A1|+ |A2|+ |A5|+ |A6| = 50
|A1|+ |A2| = 31
|A1|+ |A5| = 28
 =⇒ |A1| − |A6| = 9
de aqúı que al ser |A6| > 0,
|A1| = 9 + |A6| =⇒ |A1| > 9
es decir, las tres monedas mostraron cara simultáneamente, al menos, en nueve ocasiones.
Análogamente,
8∑
i=1
|Ai| = 100 =⇒ |A8| = 100−
7∑
i=1
|Ai| .
61
Universidad de Cádiz Departamento de Matemáticas
Ahora bien,
|A1|+ |A2|+ |A3|+ |A4| = 70
|A1|+ |A2|+ |A5|+ |A6| = 50
|A1|+ |A2| = 31
 =⇒
6∑
i=1
|Ai| = 89
luego,
|A8| = 100−
6∑
i=1
|Ai| − |A7| =⇒ |A8| = 100− 89− |A7|
=⇒ |A8| = 11− |A7|
{|A7| > 0}
=⇒ |A8| 6 11
es decir, las tres monedas han mostrado cruz simultáneamente once veces, como máximo. �
Ejemplo 3.19 En un estudio sobre las posibilidades de obtener madera entre los robles y pinos de dos
parcelas, una de la sierra de Gredos y otra de la serrańıa de Villuercas, se obtuvieron entre otros, los
siguientes datos: robles, 529; pinos, 484; árboles de la sierra de Gredos, 408; árboles maderables, 158;
robles de la sierra de Gredos, 236; árboles de la sierra de Gredos no maderables, 328; robles maderables,
76; robles o árboles de Gredos o maderables, 738.
(a) Hallar el número de robles maderables de la sierra de Gredos.
(b) Hallar el número de pinos no maderables de la serrańıa de Villuercas.
Solución
En este ejemplo hay dos particiones naturales del conjunto de todos los árboles, por un lado los que están
en la Sierra de Gredos no pueden estar en la Serrańıa de Villuercas y viceversa y, por otro, los robles
no son pinos y viceversa. Sin embargo, árboles maderables y no maderables los habrá tanto en Gredos
como en Villuercas y, aún más, podrán ser robles o pinos. Aśı pues, si llamamos
G: Árboles de la Sierra de Gredos.
V : Árboles de la Serrańıa de Villuercas.
R: Robles.
G: Pinos.
M : Maderables.
tendremos que G ∩ V = ∅ y R ∩ P = ∅, es decir, en ambos casos, cada uno es complementario del otro.
La situación puede resumirse gráficamente en el diagrama siguiente.
62
Matemática Discreta Francisco José González Gutiérrez
P
R
G V
M
P ∩G ∩M c
R ∩G ∩M c R ∩ V ∩M c
P ∩ V ∩M c
P ∩G ∩M
R ∩G ∩M R ∩ V ∩M
P ∩ V ∩M
Ejemplo 3.19
Veamos que datos que proporciona el enunciado.
~ Robles, 529, es decir, |R| = 529.
~ Pinos, 484, o sea, |P | = 484.
~ Árboles de la sierra de Gredos, luego |G| = 408.
~ Árboles maderables, por lo tanto, |M | = 158.
~ Robles de la sierra de Gredos, es decir, |R ∩G| = 236.
~ Árboles de la sierra de Gredos no maderables, o sea, |G ∩M c| = 328.
~ Robles maderables, luego |R ∩M | = 76.
~ Robles o árboles de Gredos o maderables, o sea, |R ∪G ∪M | = 738.
(a) Calculemos el número de robles maderables que hay en la Sierra de Gredos.
A la vista de los datos que proporciona el enunciado, podemos aplicar el principio de inclusión-
exclusión para 3 conjuntos:
|R ∪G ∪M | = |R|+ |G|+ |M | − |R ∩G| − |R ∩M | − |G ∩M |+ |R ∩G ∩M | (3.12)
63
Universidad de Cádiz Departamento de Matemáticas
y el único dato que no conocemos es |G ∩M |. Ahora bien, los árboles de la sierra de Gredos pueden
ser maderables o no maderables, es decir,
G = (G ∩M) ∪ (G ∩M c)
siendo, ésta, una descomposición de G en unión de subconjuntos disjuntos. Aplicando el principio
de adición,
|G| = |G ∩M |+ |G ∩M c|
de donde,
|G| − |G ∩M | = |G ∩M c|
sustituimos en (3.12) y
|R ∪G ∪M | = |R|+ |M | − |R ∩G| − |R ∩M |+ |G ∩M c|+ |R ∩G ∩M |
= 738− 529− 158 + 236 + 76− 328
= 35
(b) Pinos no maderables hay en la Serrańıa de Villuercas.
Lo que nos piden es el número de elementos del subconjunto (R ∪G ∪M)c. Pues bien, si tenemos
en cuenta que el conjunto universal puede descomponerse en unión de disjuntos como R ∪ P y,
también, como (R ∪G ∪M) ∪ (R ∪G ∪M)c, aplicando las leyes de De Morgan y el principio de
adición, tendremos
R ∪ P = (R ∪G ∪M) ∪ (R ∪G ∪M)c =⇒ R ∪ P = (R ∪G ∪M) ∪ (Rc ∩Gc ∩M c)
=⇒ R ∪ P = (R ∪G ∪M) ∪ (P ∩ V ∩M c)
=⇒ |R|+ |P | = |R ∪G ∪M |+ |P ∩ V ∩M c|
=⇒ |P ∩ V ∩M c| = |R|+ |P | − |R ∪G ∪M |
=⇒ |P ∩ V ∩M c| = 529 + 484− 738
=⇒ |P ∩ V ∩M c| = 275 �
Ejemplo 3.20 En un estudio sobre sus prácticas deportivas hecho entre 150 estudiantes de la Univer-
sidad de Cádiz, se observa que los que juegan al fútbol no juegan al tenis ni al ajedrez y ninguno de los
ajedrecistas juega al baloncesto.
La encuesta arrojó además, los resultados siguientes:
25 juegan al fútbol.
52 juegan al baloncesto.
11 juegan únicamente al tenis.
15 juegan al fútbol y al baloncesto.
25 juegan al tenis y al baloncesto.
Los que juegan al ajedrez son el cuádruple de los que juegan únicamente al baloncesto.
¿Cuántos de los estudiantes encuestados no practican ninguno de estos cuatro deportes?
Solución
Los estudiantes que practican alguno de los cuatro deportes son los del conjunto F ∪ B ∪ T ∪ A por lo
tanto los que no practican ninguno son los de su complementario, es decir, (F ∪B ∪ T ∪A)c o lo que es
igual F c ∩Bc ∩ T c ∩Ac.
64
Matemática Discreta Francisco José González Gutiérrez
Por otra parte, si U es el conjunto universal formado por todos los estudiantes encuestados, tendremos
que |U | = 150 y
U = (F ∪B ∪ T ∪A) ∪ (F ∪B ∪ T ∪A)c
luego por el principio de adición,
|U | = |F ∪B ∪ T ∪A|+ |(F ∪B ∪ T ∪A)c|
de aqúı que
|(F ∪B ∪ T ∪A)c| = |U | − |F ∪B ∪ T ∪A| = 150− |F ∪B ∪ T ∪A| . (3.13)
Nuestro problema es, por tanto, calcular |F ∪B ∪ T ∪A| es decir, cuántos estudiantes practican alguno
de los cuatro deportes.
Además, del enunciado se sigue lo siguiente:
X Los que juegan al fútbol no juegan al tenis ni al ajedrez, luego
F ∩ T = ∅ y F ∩A = ∅
de aqúı que
(F ∩ T ) ∪ (F ∩A) = ∅
es decir,
F ∩ (T ∪A) = ∅
X Ninguno de los ajedrecistas juega al baloncesto, luego
B ∩A = ∅
de aqúı que
(F ∩A) ∪ (B ∩A) = ∅
o sea,
(F ∪B) ∩A = ∅
Además,
(F ∪B) ∩ (T ∪A) = [(F ∪B) ∩ T ] ∪ [(F ∪B) ∩A]
= (F ∩ T ) ∪ (B ∩ T ) ∪ [(F ∪B) ∩A]
= ∅ ∪ (B ∩ T ) ∪ ∅
= B ∩ T
La situación puede resumirse de forma gráfica en la figura siguiente:
65
Universidad de Cádiz Departamento de Matemáticas
F B T A
U
F c ∩Bc ∩ T c ∩Ac
Ejemplo 3.20
Utilizando el principio de inclusión-exclusión para dos conjuntos F ∪B y T ∪A, tendremos
|F ∪B ∪ T ∪A| = |(F ∪B) ∪ (T ∪A)|
= |F ∪B|+ |T ∪A| − |(F ∪B) ∩ (T ∪A)|
= |F ∪B|+ |T ∪A| − |B ∩ T | (3.14)
y como el enunciado proporciona, entre otros, los datos |F |, |B|, |F ∩B| y |T ∩B|, aplicamos de nuevo
el principio de inclusión-exclusión a F ∪B, es decir,
|F ∪B| = |F |+ |B| − |F ∩B|
que sustituido en (3.14), nos lleva a que
|F ∪B ∪ T ∪A| = |(F ∪B) ∪ (T ∪A)|
= |F ∪B|+ |T ∪A| − |(F ∪B) ∩ (T ∪A)|
= |F |+ |B| − |F ∩B|+ |T ∪A| − |B ∩ T | (3.15)
y el único dato que nos falta es |T ∪A|.
Pues bien, como conocemos los que juegan únicamente altenis y los que juegan al ajedrez, descompon-
dremos los que juegan al tenis o al ajedrez (T ∪ A) en los que juegan al tenis y no al ajedrez y los que
juegan al ajedrez, es decir,
T ∪A = (T ∩Ac) ∪A
y entre los que juegan al tenis y no juegan al ajedrez los hay que también juegan al baloncesto, es decir,
(T ∩Ac) = (T ∩Ac ∩B) ∪ (T ∩Ac ∩Bc) .
Sustituyendo este resultado en la igualdad anterior,
T ∪A = (T ∩Ac ∩B) ∪ (T ∩Ac ∩Bc) ∪A
y al ser los tres conjuntos disjuntos dos a dos, por el principio de adición,
|T ∪A| = |T ∩Ac ∩B|+ |T ∩Ac ∩Bc|+ |A|
66
Matemática Discreta Francisco José González Gutiérrez
y como los que juegan al ajedrez no juegan al baloncesto,
|T ∩Ac ∩B| = |T ∩B|
de aqúı que
|T ∪A| = |T ∩B|+ |T ∩Ac ∩Bc|+ |A|
donde |T ∩Ac ∩Bc| son los que juegan únicamente al tenis.
Sustituyendo en (3.15),
|F ∪B ∪ T ∪A| = |F |+ |B| − |F ∩B|+ |T ∩B|+ |T ∩Ac ∩Bc|+ |A| − |B ∩ T |
= |F |+ |B| − |F ∩B|+ |T ∩Ac ∩Bc|+ |A| (3.16)
y sólo nos queda saber cuántos juegan únicamente al baloncesto ya que |A| es el cuádruple de ése número.
Pues bien, según el enunciado los que juegan al baloncesto no juegan al ajedrez, luego sólo podrán jugar
al fútbol o al tenis y como los que juegan al fútbol no juegan al tenis, tendremos que
B = (B ∩ F ) ∪ (B ∩ F c ∩ T c) ∪ (B ∩ T )
es una descomposición de B en unión de conjuntos disjuntos. Aplicando el principio de adición,
|B| = |B ∩ F |+ |B ∩ F c ∩ T c|+ |B ∩ T |
siendo |B ∩ F c ∩ T c| el número de estudiantes encuestados que juegan únicamente al baloncesto, luego
|A| = 4 |B ∩ F c ∩ T c| = 4 |B| − 4 |B ∩ F | − 4 |B ∩ T | .
Sustituyendo en (3.16) este resultado y, posteriormente, los datos del enunciado,
|F ∪B ∪ T ∪A| = |F |+ |B| − |F ∩B|+ |T ∩Ac ∩Bc|+ 4 |B| − 4 |B ∩ F | − 4 |B ∩ T |
= |F |+ 5 |B| − 5 |F ∩B|+ |T ∩Ac ∩Bc| − 4 |B ∩ T |
= 25 + 5 · 52− 5 · 15 + 11− 4 · 25
= 25 + 260− 75 + 11− 100
= 121
Finalmente, llevando este resultado a (3.13),
|F ∪B ∪ T ∪A|c = 150− 121 = 29
es decir, 129 estudiantes de los encuestados no practican ninguno de estos cuatro deportes. �
Ejemplo 3.21 En una reunión hay más hombres que mujeres, más mujeres que beben que hombres
que fuman y más mujeres que fuman y no beben que hombres que no beben ni fuman. Demostrar que
hay menos mujeres que no beben ni fuman que hombres que beben y no fuman.
Solución
Sea
H: Conjunto formado por los hombres de la reunión.
M : Conjunto formado por las mujeres de la reunión.
F : Conjunto formado por las personas de la reunión que fuman.
B: Conjunto formado por las personas de la reunión que beben.
67
Universidad de Cádiz Departamento de Matemáticas
H M
F
B
H ∩ F ∩Bc
H ∩ F ∩B
H ∩ F c ∩B
M ∩ F ∩Bc
M ∩ F ∩B
M ∩ F c ∩B
H ∩ F c ∩Bc M ∩ F c ∩Bc
Ejemplo 3.21
Según los datos aportados por el enunciado,
X hay más hombres que mujeres, es decir,
|H| > |M | (3.17)
Descompondremos los conjuntos H y M en unión de conjuntos disjuntos.
H = (H ∩ F ) ∪ (H ∩ F c)
= (H ∩ F ∩B) ∪ (H ∩ F ∩Bc) ∪ (H ∩ F c ∩B) ∪ (H ∩ F c ∩Bc)
M = (M ∩ F ) ∪ (M ∩ F c)
= (M ∩ F ∩B) ∪ (M ∩ F ∩Bc) ∪ (M ∩ F c ∩B) ∪ (M ∩ F c ∩Bc)
Aplicando el principio de adición,
|H| = |H ∩ F ∩B|+ |H ∩ F ∩Bc|+ |H ∩ F c ∩B|+ |H ∩ F c ∩Bc|
|M | = |M ∩ F ∩B|+ |M ∩ F ∩Bc|+ |M ∩ F c ∩B|+ |M ∩ F c ∩Bc|
Sustituyendo estos resultados en (3.17)
|H ∩ F ∩B|+ |H ∩ F ∩Bc|+ |H ∩ F c ∩B|+ |H ∩ F c ∩Bc| >
|M ∩ F ∩B|+ |M ∩ F ∩Bc|+ |M ∩ F c ∩B|+ |M ∩ F c ∩Bc| (3.18)
68
Matemática Discreta Francisco José González Gutiérrez
X hay más mujeres que beben que hombres que fuman, es decir,
|M ∩B| > |H ∩ F | (3.19)
Al igual que antes, escribimos los conjuntos M ∩B y H ∩ F como unión de conjuntos disjuntos
M ∩B = (M ∩ F ∩B) ∪ (M ∩ F c ∩B)
H ∩ F = (H ∩ F ∩B) ∪ (H ∩ F ∩Bc) .
Aplicando nuevamente el principio de adición,
|M ∩B| = |M ∩ F ∩B| + |M ∩ F c ∩B|
|H ∩ F | = |H ∩ F ∩B| + |H ∩ F ∩Bc| .
y sustituyendo en (3.19)
|M ∩ F ∩B|+ |M ∩ F c ∩B| > |H ∩ F ∩B|+ |H ∩ F ∩Bc| (3.20)
X hay más mujeres que fuman y no beben que hombres que no beben ni fuman. Entonces,
|M ∩ F ∩Bc| > |H ∩ F c ∩Bc| . (3.21)
Pues bien, sumando miembro a miembro las desigualdades (3.18), (3.20) y (3.21)
|H ∩ F ∩B|+ |H ∩ F ∩Bc|+ |H ∩ F c ∩B|+ |H ∩ F c ∩Bc| +
|M ∩ F ∩B|+ |M ∩ F c ∩B| +
|M ∩ F ∩Bc| >
|M ∩ F ∩B|+ |M ∩ F ∩Bc|+ |M ∩ F c ∩B|+ |M ∩ F c ∩Bc| +
|H ∩ F ∩B|+ |H ∩ F ∩Bc| +
|H ∩ F c ∩Bc|
y simplificando,
|M ∩ F c ∩Bc| < |H ∩ F c ∩B|
luego hay menos mujeres que no fuman ni beben que hombres que beben y no fuman. �
3.5 Principio de Distribución
Supongamos que deseamos introducir m objetos en n cajas siendo mayor el número de aquellos que de
éstas, es decir, m > n. Obviamente, alguna de las cajas deberá contener más de un objeto. El principio
que estudiamos ahora prueba este resultado y lo generaliza. Este principio se conoce, también, con el
nombre de principio del cajón de Dirichlet, matemático alemán que lo usó para probar algunos resultados
en teoŕıa de números.
3.5.1 Teorema
Sean m,n y p tres números enteros positivos. Si se dispone de np + m objetos para distribuir entre n
cajas, entonces alguna caja deberá contener, al menos, p + 1 objetos.
Demostración
Supongamos que cada caja contiene, como máximo, p objetos; entonces el número de objetos contenidos
en la totalidad de las cajas será, como máximo, np. Por tanto nos sobran m objetos y como por hipótesis
m > 1, tendremos que
np < np + m
luego, en efecto, alguna de las cajas ha de contener, al menos, p + 1 objetos. �
69
Universidad de Cádiz Departamento de Matemáticas
3.5.2 Corolario
Si m1,m2, . . . ,mn son n números naturales tales que
n∑
i=1
mi
n
> p
entonces, para algún i entre 1 y n, se tiene que mi > p.
Demostración
Veamos que, al menos, alguno de los números dados es mayor que p.
En efecto,
n∑
i=1
mi
n
> p =⇒
n∑
i=1
mi > np
de aqúı que exista m > 1 tal que
n∑
i=1
mi = np + m
si ahora hacemos la suposición de que disponemos de n cajas y que mi es el número de elementos de
cada caja, por el teorema anterior alguno de los mi debe ser estrictamente mayor que p. �
Obsérvese que en términos de conjuntos, el principio de distribución puede expresarse de la forma sigu-
iente: Si se efectúa una partición de un conjunto finito A en n partes, entonces una de las partes posee,
al menos, |A| /n elementos.
Ejemplo 3.22 Se asignan de forma aleatoria a diez puntos de una circunferencia los números del 1 al
10. Demostrar que al menos una de las sumas asignadas a tres puntos consecutivos es mayor que 16.
Solución
•p9 8
•p8 6
•
p7
10
•
p6
1
• p55
• p47
• p33
•
p2
2
•
p1
4•
p10
9
Ejemplo 3.22
70
Matemática Discreta Francisco José González Gutiérrez
En la figura hemos dibujado una circunferencia con los diez puntos pi, 1 6 i 6 10 y un ejemplo de
asignación de los números.
Sea ni el número asignado al punto pi y
si = ni + ni+1 + ni+2, 1 6 i 6 8
s9 = n9 + n10 + n1
s10 = n10 + n1 + n2
Cada uno de los ni aparece en tres sumas, luego
10∑
i=1
si =
10∑
i=1
3ni = 3
10∑
i=1
ni = 3(1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10) = 3 · 55 = 165
Pues bien, por el corolario 3.5.2 existirá, al menos, una suma que vale
10∑
i=1
si
10
=
165
10
= 16, 5 > 16
Ejemplo 3.23 Sea T un triángulo equilátero de 2 cms. de lado. Demostrar que si se eligen cinco
puntos en su interior, hay al menos dos de ellos que distan entre śı menos de 1 cm.
Solución
Dividimos el triángulo en cuatro triángulos uniendo los puntos medios de sus lados.
Ejemplo 3.23
Tenemos, pues, cinco puntos a distribuir entre cuatro triángulos. Por el principio de distribución alguno
de ellos ha de contener al menos, dos puntos. Dado que la distancia máxima entre dos puntos dentro de
cualquiera de los triángulos es 1 cm, la proposición está probada. �
71
Universidad de Cádiz Departamento de Matemáticas
Ejemplo 3.24 En un ordenador hay almacenadas 500.000 palabras de cuatro o menos letras. ¿Son
todas distintas entre śı? (Se considera un alfabeto de 26 letras).
Solución
Para la primera letra de cadapalabra hay 26 opciones y para cada una de ellas 26 para la segunda y aśı
sucesivamente. Por el principio de multiplicación habrá un total de
26 · 26 · 26 · 26 = 264
palabras de cuatro letras.
Razonando de forma análoga habrá 263 palabras de tres letras, 262 de dos letras y 26 de una sola letra.
Por el principio de adición, el número total de palabras de cuatro o menos letras será
264 + 263 + 262 + 26 = 475.254
Dado que hay 500.000 palabras almacenada, no pueden ser todas distintas entre śı ya que por el principio
de distribución, al menos una palabra se repite. �
Ejemplo 3.25 Sea A un conjunto formado por 25 números enteros positivos. Probar que A contiene,
al menos, dos números que dan el mismo resto al dividirlos entre 24.
Solución
Por el Algoritmo de la división, al dividir cualquier entero positivo por 24, existirán un cociente q y un
resto r tales que
n = 24q + r
donde 0 6 r < 24.
Hay, pues, 24 restos distintos y como el conjunto A contiene 25 números, por el principio de distribución
habrá, al menos, dos que den el mismo resto al dividirlos entre 24. �
Ejemplo 3.26 ¿Cuántos habitantes debe tener una ciudad para asegurar que hay al menos dos habi-
tantes cuyas iniciales del nombre y de los dos apellidos coincidan?
Solución
Sea A el conjunto de las letras del alfabeto y supongamos que |A| = 26. Entonces, el número de opciones
para la primera letra del nombre y cada uno de los dos apellidos es el número de elementos del conjunto
A×A×A. Por el principio de multiplicación,
|A×A×A| = |A| · |A| · |A| = 263 = 17576
Ahora, por el principio de distribución, el número mı́nimo de habitantes para asegurar la existencia de
dos de ellos con las mismas iniciales es 17577. �
Ejemplo 3.27 En una oposición, cada opositor debe contestar a tres temas distintos elegidos por
sorteo entre diez. Si se han presentado 721 opositores, demostrar que
(a) Al menos a diecisiete opositores les tocaron los dos primeros temas iguales.
(b) Al menos nueve opositores deberán contestar el mismo primer tema y el mismo tercer tema.
(c) Al menos a dos opositores les coincidieron los tres temas y en el mismo orden.
Solución
Calculamos el número de resultados distintos que son posibles en el sorteo.
72
Matemática Discreta Francisco José González Gutiérrez
Para el primer tema hay diez opciones posibles, nueve para el segundo y, finalmente, hay ocho opciones
para el tercero. Por el principio de multiplicación, el número de resultados distintos es:
10 · 9 · 8 = 720
(a) Si consideramos únicamente los dos primeros temas, el número de resultados distintos posibles en el
sorteo es de 90. Observamos que el orden de los temas no influyen, es decir, el resultado de segundo
y cuarto temas es idéntico al de cuarto y segundo. Consecuentemente, el número de resultados
distintos posibles es 45. Pues bien,
721 = 45 · 16 + 1
luego, por el principio de distribución, habrá al menos, 17 opositores que se han examinado de los
mismos dos primeros temas.
(b) En este caso el orden de los temas en el sorteo si influye. En efecto, si a un opositor le tocase el
tema seis como primero y el tema ocho como segundo, y a otro el tema ocho como primero y el
tema seis como segundo seŕıan resultados distintos desde el punto de vista en que se plantea la
pregunta. Por el principio de multiplicación habŕıa 10 · 9 = 90 resultados posibles del sorteo para
los temas primero y tercero. Al ser
721 = 90 · 8 + 1
por el principio de distribución hay, al menos, un subconjunto con nueve opositores que deberán
contestar al mismo primer tema y al mismo tercer tema.
(c) Razonando igual que en el apartado anterior, el orden influye, luego el número de resultados posibles
es 10 · 9 · 8 = 720, y al ser
721 = 720 · 1 + 1
el principio de distribución asegura que al menos, dos opositores se examinaron de los mismos tres
temas y en el mismo orden. �
73