Principio Palomar

 PRINCIPIO DEL PALOMAR

El Principio del Palomar (o Principio de Dirichlet) establece que si n palomas se distribuyen en m palomares, y n > m, entonces al menos un palomar debe contener más de una paloma.

FORMULACIÓN MATEMÁTICA

Si n > m, entonces al distribuir n objetos en m grupos, al menos un grupo debe contener al menos ⌈n/m⌉ objetos.

Donde ⌈n/m⌉ representa el menor entero mayor o igual que n/m.

FORMULACIÓN GENERALIZADA

Si n objetos se distribuyen en m grupos, entonces al menos un grupo debe contener al menos ⌈n/m⌉ objetos, y al menos un grupo debe contener a lo sumo ⌊n/m⌋ objetos.
10 palomas en 9 palomares: al menos un palomar tiene más de una paloma


DEMOSTRACIÓN POR CONTRADICCIÓN

  1. Supongamos que cada palomar contiene a lo sumo una paloma.
  2. Entonces, el número máximo de palomas sería igual al número de palomares (m).
  3. Pero tenemos n palomas, donde n > m.
  4. Esto es una contradicción, por lo que nuestra suposición es falsa.
  5. Por lo tanto, al menos un palomar debe contener más de una paloma.



Comentarios

Publicar un comentario

Entradas más populares de este blog

Productos Cartesianos

Imagen
¿QUÉ SON LOS PRODUCTOS CARTESIANOS? E l  producto cartesiano  de dos  conjuntos  es una  operación , que resulta en otro conjunto, cuyos  elementos  son todos los  pares ordenado s  que pueden formarse de forma que el primer elemento del par ordenado pertenezca al primer conjunto y el segundo elemento pertenezca al segundo conjunto. Formula A x B = { (a,b) | a  ∈ A   y    b  ∈ B } Ejemplo Producto cartesiano del los conjuntos { x , y , z } y {1,2,3} EJEMPLO 2 Si A = {1,2} y B = {a,b,c}, entonces: A x B = {(1.a), (1,b), (1,c), (2,a), (2,b), (2,c)} Video de ejemplo
Leer más

Funciones

Imagen
 FUNCIÓN GENERAL Una función f: A  ⭢ B es una relación que asocia a cada elemento x  ∈ A exactamente un elemento y  ∈ B. Definición normal   Una función f de A en B es un subconjunto de A x B tal que: Para todo x  ∈ A, existe al menos un par (x,y)  ∈ f. Si (x,y)  ∈ f y (x,z)  ∈ f, entonces y = z. Notación: f: A  ⭢ B, x  ↦  f (x) A es el dominio de f B es el codominio de f El conjunto {f(x) | x ∈ A} es el rango. FUNCIÓN INYECTIVA Una función es inyectiva  si cada elemento del conjunto de llegada corresponde como máximo a un elemento del conjunto de partida. Otra definición es la siguiente: una función f: A -> B es inyectiva, si no existen 2 elementos de A (conjunto de llegada) con una misma imagen. Veamos algunos ejemplos: Para determinar si una función es inyectiva, tenemos que analizar la siguiente condición: FUNCIÓN SOBREYECTIVA Una función es sobreyectiva  si cada elemento del conjunto de llegada (codo...
Leer más

Relaciones

Imagen
 ¿QUÉ SON LAS RELACIONES? Una Relación R de A a B es un subconjunto del producto cartesiano  A x B. Es decir, R  ⊆  A x B. Ejemplo de Relación: Si A = {1, 2, 3} y B = {a, b, c}, una posible relación R podría ser: R = { (1,a), (2,b), (3,c) } Esta relación asocia cada número con una letra específica. RELACIÓN REFLEXIVA: Una relación R sobre un conjunto A es reflexiva si todo elemento está relacionado consigo mismo, es decir: ∀a ∈ A, (a,a) ∈ R Ejemplo: Sea A = {1, 2, 3}, entonces una relación reflexiva puede ser: R = {(1,1), (2,2), (3,3)} RELACIÓN SIMÉTRICA  Una relación R es simétrica si cuando un elemento está relacionado con otro, el otro también está relacionado con el primero, es decir: Si (a,b) ∈ R, entonces (b,a) ∈ R Ejemplo: Sea A = {1, 2}, entonces una relación simétrica puede ser: R = {(1,2), (2,1)} RELACIÓN TRANSITIVA Una relación R es transitiva si cuando un elemento está relacionado con otro, y ese otro con un tercero, entonces el primero también está ...
Leer más