Obligatorio 2 - Conteos y Grafos

Principio de Palomar

Este principio también llamado principio de las cajas y/o ”principio de Dirichlet ”, en honor a un matemático alemán de principios del siglo XIX; establece que : ”Si tenemos p palomas, las que se disponen en n nidos , donde p \(>\) n , entonces por lo menos dos palomas se deben ubicar en el mismo nido.”

Éste principio solamente asegura que un lugar será ocupado con por lo menos dos objetos, no indica que lugar , ni cuantos objetos en total se ocupan un mismo lugar.

Demostración: Si suponemos que en ningún nido hay por lo menos dos palomas, el número de éstas no puede exceder al de nidos, lo que contradice nuestra premisa inicial.

Ejemplos:

Ejemplo 1: En una reunión hay 15 personas, mostrar que por lo menos hay dos parejas de personas que cumplen el mismo mes, se entiende que pueden ser meses diferentes entre si.

Solución: Aplicamos primero tomando como palomas las personas y como nidos los meses. Como p \(>\) n, entonces, podemos asegurar que por lo menos dos personas cumplen el mismo mes. Elijamos una de esas posibles parejas y la sacamos. Entonces: tenemos 13 personas. Razonamos de igual manera, tenemos 13 palomas y 12 nidos , luego existen por lo menos dos personas que cumplen el mismo mes, encontramos entonces dos parejas de personas que cumplen en un mismo mes.

Ejemplo 2: Se considera un conjunto A = {1 , 2 ,3 ,4 ,5 ,6 , 7 ,8 ,9}, demostrar que todo subconjunto de 6 elementos de A, tiene al menos dos números cuya suma sea 10.

Solución: En éste caso se pueden distinguir 2 casos;

  • Primer caso: el 5 esta en el subconjunto , entonces quedan en el subconjunto cinco números diferentes del 5, si usamos el principio del palomar tomando como palomas los 5 números restantes y como nidos los subconjuntos {1, 9}, {2, 8}, {3, 7} y {4, 6} entonces por lo menos 2 de los números suman 10.

  • 2 y 5 no estan en el subconjunto , entonces tenemos 6 palomas para repartir en 4 nidos : {1, 9}, {2, 8}, {3, 7} y {4, 6}, entonces por lo menos hay dos números que suman 10.

  • Una alternativa similar, que no separa los dos casos es pensar en las 6 palomas (los 6 números), y 5 nidos, los subconjuntos: {1, 9}, {2, 8}, {3, 7} , {4, 6} y {5}, y usar el principio, entonces en el último nido no pueden haber 2 palomas.

Principio de inclusión y exclusión

Sea S un conjunto tal que S = N , sean c 1 , . . . , c t una serie de condiciones o propiedades, que son satisfechas por algunos, eventualmente todos , los elementos del conjunto S. Puede pasar que algunos elementos del conjunto podrían satisfacer más de una de las condiciones, mientras que otros podrían no satisfacer ninguna de ellas.

  • Para cada i : 1 \(\leq\) i \(\leq\) t, se anota N(\(c_{i}\)), a la cantidad de elementos de S que verifican \(c_{i}\), entendiendo que pueden o no satisfacer alguna de las restantes. Dados dos índices i , j , con i\(\neq\)j , 1\(\leq\)i , j\(\leq\)t, se dice que N (\(c_{i}\) \(c_{j}\)) es la cantidad de elementos de S que satisfacen simultáneamente las condiciones \(c_{i}\) y \(c_{j}\) entendiendo que pueden o no satisfacer alguna de las otras condiciones. Se utiliza la misma notación para indicar que se cumplan a la vez tres o más condiciones.

  • Para cada i tal que 1\(\leq\)i\(\leq\)t, N (\(\bar{c_{i}}\)), es la cantidad de elementos de S que no verifican la condición \(c_{i}\) , o sea N (\(\bar{c_{i}}\) ) = N- N (\(c_{i}\)).

  • Dados dos índices i, j , con i\(\neq\)j , 1\(\leq\)i , j\(\leq\)t, notaremos con N(¯\(c_{i}\) ¯\(c_{j}\)) al número de elementos que no satisfacen ninguna de las condiciones \(c_{i}\) o \(c_{j}\). De igual forma en el caso de tres o más condiciones.

Ejemplo 1: En el siguiente diagrama , N (\(c_{i}\) \(c_{j}\)) indica la cantidad de elementos del solapamiento, mientras que N (\(\bar{c_{i}}\) \(\bar{c_{j}}\)) indica la cantidad de elementos fuera de la unión.