Principio del palomar

En Matemática, el principio del palomar, también llamado principio de casillas, principio de Dirichlet o principio de las cajas, 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$ palomares pueden albergar como mucho $m$ palomas si cada una de las palomas está en un palomar distinto, así que el hecho de añadir otra paloma fuerza a volver a utilizar alguno de los palomares. Esta afirmación aparentemente obvia, un tipo de argumento combinatorio, puede usarse para demostrar resultados posiblemente inesperados.

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

A pesar de que el principio de casillas aparece en 1624 en un libro atribuido a Jean Leurechon,^[1] es comúmente llamado Principio de las cajas de Dirichlet o Principio de las cajones de Dirichlet debido a un tratado sobre el principio escrito en 1834 por Johann Peter Gustav Lejeune Dirichlet con el nombre de Schubfachprinzip ("principio de los cajones").

Etimología editar

Casillas de mensajes en Universidad Stanford.

Dirichlet publicó su trabajo en francés y alemán, usando el término en alemán Schubfach o el término en francés tiroir. El significado original de esos términos corresponde al español cajón, eso es, pieza móvil de diversos muebles, cerrada por sus costados y abajo, abierta por arriba, usada para guardar diversos elementos ordenadamente. (Dirichlet escribió acerca de distribuir perlas entre esos cajones.) Esos términos se transformaron en la palabra palomar en el sentido de un espacio pequeño en un escritorio, gabinete, o pared para guardar cartas o papeles, metafóricamente arraigado en estructuras que albergan palomas.

La sugerente (aunque no engañosa) interpretación de "casillero" como "palomar" ha encontrado su camino de regreso al alemán mediante una retrotraducción del principio del palomar como "Taubenschlagprinzip".^[2]

Generalización y demostración editar

Aquí

n=10

y

m=9

.

El principio tiene varias generalizaciones y puede ser enunciado de distintas maneras. En una versión más cuantificada: para los números naturales $k$ y $m$ , si $n=km+1$ objetos son distribuidos en $m$ conjuntos, entonces por el principio de casillas afirma que al menos uno de los conjuntos contendrá al menos $k+1$ objetos. Para $n$ y $m$ arbitrarios, esto se generaliza a $k+1=\lfloor (n-1)/m\rfloor +1=\lceil n/m\rceil$ , donde $\lfloor \cdots \rfloor$ y $\lceil \cdots \rceil$ denotan las funciones suelo y techo, respectivamente.

Aunque la aplicación más directa es en conjuntos finitos (como palomas y cajas), también se utiliza con conjuntos infinitos que no pueden ser puestos en una correspondencia uno a uno. Para esto es necesario la proposición formal del principio de casillas, cual es "no existe una función inyectiva cuyo codominio es más pequeño que su dominio". Demostraciones matemáticas avanzadas como el lema de Siegel se construyen sobre este concepto más general.

Enunciemos el principio de la siguiente manera: Sean $n$ , $q$ y $r$ tres números naturales (con $1\leq r\leq q$ ). Si se desean colocar $nq+r$ objetos en $n$ casillas, alguna caja debe contener al menos $q+1$ objetos.

Demostración. Asumamos por contradicción que cada casilla contiene como mucho $q$ objetos, el número total de objetos que podemos colocar es $nq<nq+1\leq nq+r$ . Por tanto, con $q$ por caja no es posible distribuir los $nq+r$ objetos. $\blacksquare$

Esta demostración nos sirve para probar de manera análoga, el siguiente corolario: Si se desean colocar $nq+r$ objetos en $n$ casillas, alguna caja debe contener al sumo $q$ objetos.

Demostración por conjuntos editar

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

Demostración por inducción:^[3]

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 biyectiva.
Hipótesis inductiva: $f\colon A\to B\,$ no es biyectiva para todo conjunto finito $A$ y para todo conjunto finito $B$ , que cumplan $\vert A\vert >\vert B\vert$ , y $\vert B\vert \leq n$ , con $n\geq 0$ .
Tesis inductiva: Para $\vert A\vert >\vert B\vert =n+1$ , no existe una función $f\colon A\to B\$ biyectiva.
Demostración del paso inductivo: Como $A$ no es vacío, elijamos un $a\in {\mbox{A}}$ . 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 biyectiva 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 biyectiva. Como $g$ no es biyectiva, $f$ no es biyectiva. $\blacksquare$

Ejemplos editar

Problema del cumpleaños editar

El problema de cumpleaños pregunta, para un conjunto de $n$ personas seleccionadas aleatoriamente, ¿Cuál es la probabilidad que dos de ellos tengan el mismo cumpleaños? El problema en sí tiene que ver principalmente con probabilidades contraintuitivas; sin embargo, también podemos decir por el principio que, si hay 367 personas en una habitación, hay una probabilidad del 100% de que haya dos personas que compartan fechad de cumpleaños, ya que solo hay 366 posibles cumpleaños de donde elegir (incluyendo el 29 de febrero, si es necesario).

Sacando calcetines editar

Asumamos que un gaveta contiene una combinación de calcetines azules y blancos, cada uno puede ser usado en cualquier pie, y que se sacan calcetines de la gaveta sin mirar. ¿Cuál es el menor número de calcetines que se necesitan sacar para garantizar un par de un mismo color? Usando el principio de casillas ( $m=2$ casillas, utilizando una por color), solo se necesitan sacar 3 calcetines de la gaveta ( $n=3$ objetos). Se pueden tener tres de un solo color, o se puede tener dos de unos y uno de otro.

Conteo de cabellos editar

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 Guatemala con el mismo número de pelos en la cabeza.

Demostración: la cabeza de una persona tiene en torno a 150.000 cabellos y tener un millón de pelos requeriría de una cabeza gigante (nadie tiene un millón de pelos en la 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 Guatemala hay más de un millón de personas, habrá al menos dos personas con el mismo número de pelos en la cabeza. De hecho se puede asegurar con seguridad que en cualquier ciudad de más de un millón de personas hay más de 5 personas con el mismo número de pelos en la cabeza (por el principio de Dirichlet generalizado).

Usos y aplicaciones editar

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. Este 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).

Véase también editar

Referencias editar

↑ Rittaud, Benoît; Heeffer, Albrecht (2014). «The pigeonhole principle, two centuries before Dirichlet». The Mathematical Intelligencer 36 (2): 27-29. MR 3207654. S2CID 44193229. doi:10.1007/s00283-013-9389-1. hdl:1854/LU-4115264.
↑ Zimmermann, Karl-Heinz (2006). Diskrete Mathematik. p. 367. ISBN 9783833455292.
↑ Harry R. Lewis and Christos H. Papadimitriou; Elements of the Theory of Computation, Second Edition; Prentice-Hall, Englewood Cliffs, New Jersey, 1997

Bibliografía editar

Grimaldi, Ralph P. (1997), Matemáticas Discretas y Combinatoria: Una introducción con aplicaciones, 2da ed., México, Addison Wesley Iberoamericana, S.A.
Gómez Ortega, José A., Valdez Delgado, Rogelio, Vázquez Padilla, Rita, (2011) Principio de las casillas, México, Universidad Nacional Autónoma de México.
Guzmán, Miguel de (1986), Editorial Labor S.A. Barcelona, España. ¿título?

Enlaces externos editar

«Principio de Casillas». 5 de julio de 2020 – via YouTube.
Weisstein, Eric W. «Dirichlet's Box Principle». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research.

Datos: Q188276

[leurechon-1] Rittaud, Benoît; Heeffer, Albrecht (2014). «The pigeonhole principle, two centuries before Dirichlet». The Mathematical Intelligencer 36 (2): 27-29. MR 3207654. S2CID 44193229. doi:10.1007/s00283-013-9389-1. hdl:1854/LU-4115264.

[2] Zimmermann, Karl-Heinz (2006). Diskrete Mathematik. p. 367. ISBN 9783833455292.

[3] Harry R. Lewis and Christos H. Papadimitriou; Elements of the Theory of Computation, Second Edition; Prentice-Hall, Englewood Cliffs, New Jersey, 1997

[1]

[2]

[3]