Principio del palomar

Principio del palomar

Principio del palomar

La inspiración para el nombre del principio: aves en un palomar. Aquí n = 7 y m = 9.

El principio del palomar, también llamado principio de Dirichlet, establece que si n palomas se distribuyen en m palomares, y si n > m, entonces al menos habrá un palomar con más de una paloma. Otra forma de decirlo es que m huecos pueden albergar como mucho m objetos si cada uno de los objetos está en un hueco distinto, así que el hecho de añadir otro objeto fuerza a volver a utilizar alguno de los huecos. De otra manera: si se toman trece personas, al menos dos habrán nacido el mismo mes.

El primer enunciado del principio se cree que proviene de Dirichlet en 1834 con el nombre de Schubfachprinzip ("principio de los cajones"). No debe confundirse con otro principio sobre funciones armónicas, también con el nombre de este autor.

Principio de distribución, del palomar o del cajón de Dirichlet. Sean m, n y p tres números naturales. Si se desean colocar np + m objetos en n cajas, alguna caja debe contener al menos p + 1 objetos.

Demostración. Si cada caja contiene como mucho p objetos, el número total de objetos que podemos colocar es np < np + 1 ≤ np + m.

En su versión más simple, este principio dice que no puede existir una aplicación inyectiva entre un conjunto de m elementos y otro de n elementos, si m > n. Equivalentemente, si se desean colocar m objetos en n cajas, con m > n, al menos una caja debe contener al menos 2 objetos.

Aunque el principio del palomar puede parecer una observación trivial, se puede utilizar para demostrar resultados inesperados. Por ejemplo, hay por lo menos 2 personas en Madrid con el mismo número de pelos en la cabeza. Demostración: la cabeza de una persona tiene en torno a 750.000 cabellos y tener un millón de pelos requeriría de una cabeza gigante (nadie tiene un millón de pelos en al cabeza). Asignamos un palomar por cada número de 0 a 1.000.000 y asignamos una paloma a cada persona que irá al palomar correspondiente al número de pelos que tiene en la cabeza. Como en Madrid hay más de un millón de personas, habrá al menos dos personas con el mismo número de pelos en la cabeza.

Una versión generalizada de este principio dice que, si n objetos discretos deben guardarse en m cajas, al menos una caja debe contener no menos de \lceil \tfrac{n}{m} \rceil objetos, donde \lceil\dots\rceil denota la función techo.

Formulación matemática

Si A y B son conjuntos finitos con \vert A \vert > \vert B \vert entonces no existe ninguna función inyectiva de A en B.

[1] Demostración por inducción

Paso base: Supongamos \vert B \vert = 0 , es decir, B = \emptyset . Entonces no existe ninguna función f \colon A \to B \, , en particular no existe ninguna función inyectiva.

Hipótesis inductiva: f \colon A \to B \, no es inyectiva para todo conjunto finito A y para todo conjunto finito B, que cumplan \vert A \vert  > \vert B \vert , y \vert B \vert  <= n , con n > = 0.

Tesis inductiva: Para \vert A \vert > \vert B \vert = n + 1, no existe una función f \colon A \to B \ inyectiva.

Demostración del paso inductivo: . Como A no es vacío, elijamos un  a \in \mbox{A} \qquad. Pueden ocurrir dos cosas. O bien existe otro elemento distinto a a en A, llamémosle a' que cumpla f(a) = f(a'). O bien no existe tal elemento. Si el caso es que existe, la función f no es inyectiva y termina la demostración. Tomemos el caso que no existe, entonces f(a) tiene solo una preimagen que es a. Consideramos la función g \colon A - \{a\} \to B - \{f(a)\} \, que coincide con f en todos los elementos de A − {a}. Ahora aplicamos la hipótesis inductiva pues B − {f(a)} tiene n elementos y   \vert A - \{a\}\vert = \vert A \vert - 1 > \vert B \vert - 1 = \vert B - \{f(a)\}\vert = n, por lo tanto g no es inyectiva. Como g no es inyectiva, f no es inyectiva, que es lo que queríamos demostrar.


Usos y aplicaciones

El principio del palomar es encontrado a menudo en informática. Por ejemplo, las colisiones son inevitables en una tabla hash porque el número de posibles valores que pueden tomar los elementos de un vector exceden a menudo el número de sus índices. Ningún algoritmo de hashing, sin importar lo bueno que sea, puede evitar estas colisiones. Éste principio también prueba que cualquier algoritmo de compresión sin pérdida que hace al menos de un archivo de entrada otro más pequeño hará que otro fichero de entrada sea más grande. (De lo contrario, dos archivos distintos podrían ser comprimidos a un mismo archivo más pequeño y al ser restaurado habría conflicto)

Referencias

  1. Harry R. Lewis and Christos H. Papadimitriou; Elements of the Theory of Computation, Second Edition; Prentice-Hall, Englewood Cliffs, New Jersey, 1997
Obtenido de "Principio del palomar"

Wikimedia foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Mira otros diccionarios:

  • Principio del palomar — El principio del palomar establece que si n palomas se distribuyen en m palomares, y si n > m, entonces al menos habrá un palomar con más de una paloma. Otra forma de decirlo es que m huecos pueden albergar como mucho m objetos si cada uno de… …   Enciclopedia Universal

  • Lema del bombeo — En la teoría de lenguajes formales de la teoría de la computación, el lema de bombeo establece que en un lenguaje, cualquier cadena de caracteres de por lo menos una cierta longitud (llamada longitud de bombeo), contiene una sección que puede ser …   Wikipedia Español

  • Parque del Campo Grande — Coordenadas: 41°38′45″N 4°43′51″O /  …   Wikipedia Español

  • Sant Andreu de Palomar — Saltar a navegación, búsqueda Sant Andreu de Palomar es un barrio y el núcleo más antiguo del distrito de Sant Andreu de Barcelona. Antiguo municipio independente con más de 1.000 años de historia documentada, fue anexionado a Barcelona el 20 de… …   Wikipedia Español

  • Orden del Císter — Nombre latino Ordo Cisterciensis Siglas O. Cist. Nombre común …   Wikipedia Español

  • Manuel Palomar Sanz — Manuel Palomar (nacido el 14 de enero de 1964) es un profesor e investigador español de la Universidad de Alicante. Su línea de investigación se centra en las Tecnologías del Lenguaje Humano y desarrolla su labor docente en la enseñanza de las… …   Wikipedia Español

  • Ramón María del Valle-Inclán — Retrato de Valle Inclán. Nacimiento …   Wikipedia Español

  • Revolución del 43 — Arturo Rawson, Pedro Pablo Ramírez y Edelmiro Farrell, los tres generales presidentes de la Revolución del 43 (Golpe de Estado de 1943) …   Wikipedia Español

  • Catedral-Basílica de Nuestra Señora del Pilar de Zaragoza — «Basílica de Nuestra Señora del Pilar» redirige aquí. Para la basílica homónima del barrio de Recoleta, Buenos Aires, véase Basílica Nuestra Señora del Pilar (Buenos Aires). Catedral Basílica de Nuestra Señora del Pilar de Zaragoza …   Wikipedia Español

  • Incendios en el delta del Río Paraná de 2008 — Saltar a navegación, búsqueda Imagen satelital de la región afectada el viernes 18 de abril. Puede observarse la nube de humo cubriendo el Delta y toda la región nornordeste de la Provincia de Buenos Aires, incluyendo a las ciudades de Buenos… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”