Hijos de Eva

15/7/2005

Principio del palomar

Filed under: — Quintanar @ 8:15 pm

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

El primer enunciado del principio se cree que proviene de Dirichlet en 1834 con el nombre de Schubfachprinzip («principio de los cajones»). A veces se conoce este enunciado como el principio de Dirichlet (pero no debe confundirse con el principio sobre funciones armónicas del mismo nombre).

Aunque el principio del palomar puede parecer una observación trivial, se puede utilizar para demostrar resultados inesperados. Por ejemplo, tiene que haber por lo menos dos personas en Madrid con el mismo número de pelos en la cabeza. Demostración: la cabeza de una persona tiene en torno a 150.000 cabellos. Es razonable suponer que nadie tiene más de un millón de pelos en la cabeza. Hay más de un millón de personas en Madrid. Si 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, al menos habrá 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 [n/m] objetos, donde […] denota la función techo.

En el ejemplo anterior, si suponemos que Madrid tiene 3.100.000 habitantes, entonces habrá al menos 4 personas que tengan el mismo número de pelos en la cabeza.

[De Wikipedia, la enciclopedia libre]

Comments are closed.

Powered by WordPress