Principio del palomar
| ||||||
El Principio del palomar, también llamado principio de Dirichlet, establece que si p palomas se reparten en q palomares, y si p > q, entonces al menos habrá un palomar con más de una paloma. Otra forma de decirlo es que q agujeros pueden acoger, a lo más, q objetos si cada uno de los objetos está en un agujero distinto, así que el hecho de añadir otro objeto obliga a volver a utilizar alguno de los agujeros. De otra manera: si se toman 8 personas humanas, al menos dos habrán nacido en el mismo día de la semana.
Se admite que el primigenio enunciado del principio lleve la impronta creadora de Dirichlet, en 1834, con el nombre de Schubfachprinzip ("principio de los cajones"). Es importante y necesario distinguirlo de otro principio sobre funciones armónicas, también conocido con el nombre de este creador teutón.
Bosquejo
- 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 constatación baladí, se puede utilizar para demostrar resultados sorprendentes. Por ejemplo, hay por lo menos 2 personas en La Habana 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 La Habana 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 T(n/m) objetos, donde T denota la Función techo.
Enunciado y prueba
No existe ninguna función inyectiva de A en B siempre que el cardinal de A sea mayor que el de B siendo estos, conjuntos finitos .
- Demostración por inducción
- Paso base: Supongamos |B| = 0. Entonces no existe ninguna función f: A en B, en particular no existe ninguna función inyectiva.
- Hipótesis inductiva: f: A en B no es inyectiva para todo conjunto finito A y para todo conjunto finito B, que cumplan |A| > |B|, y |B| <= n, con n >= 0.
- Tesis inductiva: Para |A| > |B| = n + 1, no existe una función f: A en B inyectiva.
- Demostración del paso inductivo: Como A no es vacío, elijamos un a que pertenece a 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 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: A - {a} en 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, 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).
Bibliografía
- Harry R. Lewis and Christos H. Papadimitriou; Elements of the Theory of Computation, Second Edition; Prentice-Hall, Englewood Cliffs, New Jersey, 1997.
Fuentes
- Grimaldi, Ralph P: Matemáticas discretas y combinatoria, Addison -Wesley Ibero Americana; Wilmington,Delawarw, E.U.A(1997) .
- De Guzmán, Miguel : Aventuras matemáticas, Editorial Labor S.A. Barcelona, España (1986).
