Respuestas
Respuesta:
Las aplicaciones de este principio, casi obvio, son muchas, aunque no siempre triviales. Pongamos un par
de ejemplos.
Ejemplo 17.- Probar que, dados 12 numeros ´ enteros cualesquiera (incluso repetidos), siempre hay dos
cuya diferencia es multiplo ´ de 11.
Por el principio de la divisi´on, todo numero ´ entero puede expresarse como 11 · q + r, con
0 ≤ r < 11. Si a1, a2, . . . , a12 son los 12 numeros ´ seleccionados, entonces
ak = 11 · qk + rk, 1 ≤ k ≤ 12.
Como 0 ≤ rk < 11, s´olo hay 11 posibles restos diferentes. Ahora bien, como tenemos una
colecci´on de 12 restos, por el principio del palomar, debe haber al menos dos iguales. Sean
esos restos ri y rj , entonces
ai − aj = 11 · qi + ri − (11 · qj + rj ) = 11 · (qi − qj ).
Por lo tanto ai − aj es multiplo ´ de 11.
Ejemplo 18.- Sea A un subconjunto de seis elementos de N14. Probar que A tiene al menos dos
subconjuntos no vac´ıos cuyos elementos suman lo mismo.
Como A tiene 6 elementos, el total de subconjuntos diferentes de A es 2
6
(ver m´as adelante
el ejemplo 21), de los cuales uno es el conjunto vac´ıo. Por lo tanto A tiene 63 subconjuntos
diferentes no vac´ıos. A cada uno de esos subconjuntos le podemos asociar la suma de sus
elementos, lo que hace un total de 63 sumas diferentes posibles.
Por otro lado, la mayor suma que puede obtenerse es la correspondiente a la suma de todos
los elementos del propio conjunto A, que en el peor de los casos ser´a
9 + 10 + 11 + 12 + 13 + 14 = 69.
Sin embargo, en este caso, la menor de las sumas ser´ıa 9, lo que hace que la suma de los
elementos de los subconjuntos de A sea un numero ´ comprendido entre 9 y 69. Como esto
nos da un total de 61 sumas posibles y hay 63 subconjuntos diferentes, por el principio del
palomar, hay al menos dos sumas repetidas.
Dejamos como ejercicio el ver qu´e pasar´ıa si el conjunto A no es {9, 10, 11, 12, 13, 14}.
2.1 Principios b´asicos de conteo
Las t´ecnicas combinatorias para contar o enumerar los elementos de un conjunto se basan en una serie
de principios elementales.
Principio de adici´on.- Sean A y B dos conjuntos finitos tales que A∩B = ∅, entonces |A∪B| = |A|+|B|.
Este principio se generaliza por inducci´on. As´ı, si A1, A2, . . . , An es una colecci´on de conjuntos disjuntos
dos a dos, es decir Ai ∩ Aj = ∅ si i 6= j, entonces
|A1 ∪ A2 ∪ · · · ∪ An| = |A1| + |A2| + · · · + |An|.
Notemos que el principio del palomar es una consecuencia del principio generalizado de la suma. As´ı, si
las cajas las denominamos A1, A2, . . . , An y cada caja contiene menos de r elementos, entonces, por el
principio de adici´on,
|A1 ∪ A2 ∪ · · · ∪ An| ≤ nr < m.
Es decir, el total de elementos que hay en todas las cajas, es inferior al numero ´ de objetos que hemos
repartido m.
Tambi´en consecuencia del principio de adici´on, es el principio de inclusi´on-exclusi´on.
Principio de inclusi´on-exclusi´on.- Sean A y B dos conjuntos finitos, entonces
|A ∪ B| = |A| + |B| − |A ∩ B|.
12
Al igual que el principio de adici´on, podemos generalizar este principio por inducci´on. En este sentido,
si tenemos una colecci´on Ai (1 ≤ i ≤ n) de conjuntos finitos, entonces
|A1 ∪ A2 ∪ · · · ∪ An| =
Xn
i=1
|Ai
| −
X
1≤i<j≤n
|Ai ∩ Aj | +
X
1≤i<j<k≤n
|Ai ∩ Aj ∩ Ak| + · · · · · · + (−1)n−1
|A1 ∩ A2 ∩ · · · ∩ An|.
Ejemplo 19.- ¿Cu´antos enteros hay, entre 1 y 1000, que no son divisibles por 3, por 7 o por 11?
Sean
A = {enteros entre 1 y 1000 divisibles por 3},
B = {enteros entre 1 y 1000 divisibles por 7},
C = {enteros entre 1 y 1000 divisibles por 11}.
Lo que nos pide el problema es |(A ∪ B ∪ C)
c
| = 1000 − |A ∪ B ∪ C|. Ahora bien como uno
de cada tres numeros ´ es multiplo ´ de 3, resulta2
|A| =
1000
3
= 333.
An´alogamente, |B| =
1000
7
= 142 y |C| =
1000
11
= 90. Por otra parte, podemos
determinar los cardinales de las intersecciones teniendo en cuenta que si x ∈ |A∩B|, entonces
x es multiplo ´ de 21, por tanto
|A ∩ B| =
1000
21
= 47, |A ∩ C| =
1000
33
= 30, |B ∩ C| =
1000
77
= 12,
|A ∩ B ∩ C| =
1000
231
= 4.
Finalmente, por el principio de inclusi´on-exclusi´on
|A ∪ B ∪ C| = 333 + 142 + 90 − (47 + 30 + 12) + 4 = 480
y por tanto la soluci´on del problema es 520 .
Principio del producto.- Sean A y B dos conjuntos finitos, entonces |A × B| = |A| · |B|.
Este principio tambi´en se generaliza por inducci´on para el producto cartesiano de una colecci´on finita de
conjuntos, A1, A2, . . . , An. En este sentido,
|A1 × A2 × · · · × An| = |A1| · |A2| · · · |An|.
Podr´ıa decirse que, conocidos los principios b´asicos del conteo, la combinatoria est´a estudiada. Sin
embargo, aparecen con frecuencia conjuntos equipotentes a cuyo cardinal se le da un nombre especial.
2.2 Variaciones con repetici´on
Supongamos que queremos contar el total de posibles aplicaciones que pueden construirse de un conjunto
X, de m elementos, en otro conjunto Y , de n elementos.
Una aplicaci´on f : X −→ Y queda completamente determinada si conocemos cada una de las im´agenes
Respuesta:
me pasa la respuesta del luchito porfis