El problema del palomar o pigeon hole

Una de las cosas que hacen (hacemos) los matemáticos, es buscar patrones. Es decir, buscar situaciones que se «repiten», se asemejan. Algo así como buscar peculiaridades, o cosas que varios objetos tengan en común. Así, tratamos de sacar algunas conclusiones (o teoremas) que permitan deducir que ante ciertos antecedentes (si se verifican ciertas hipótesis), se producen ciertos consecuentes (se deduce tal tesis). En lugar de conjeturar, justamente, en abstracto, déjenme mostrarles ciertos ejemplos.
Si yo preguntara ¿cuántas personas tiene que haber en un cine para estar seguros… (dije seguros)… de que al menos dos de ellos cumplen años el mismo día? (no quiere decir que hubieran nacido el mismo año, sólo que festejen el cumpleaños el mismo día).(Por supuesto, ustedes piensen solos, sin leer la respuesta que sigue.)
Antes de escribir la respuesta, quiero pensar un momento con ustedes (si es que no contestaron solos antes). Por ejemplo: si hubiera dos personas, obviamente no hay garantías de que los dos cumplan años el mismo día. Lo más probable es que no sea así. Pero más allá de probable o no probable, el hecho es que estamos buscando seguridades. Y habiendo dos personas en la sala, nunca podríamos estar seguros de que los dos nacieron el mismo día.
Lo mismo sucedería si hubiera tres personas. O incluso diez. O cincuenta. ¿No? O cien. O doscientos. O incluso trescientos. ¿Por qué? Bueno, porque si bien habiendo trescientas personas dentro de una sala, es probable que haya dos que celebren sus cumpleaños respectivos el mismo día, todavía no podemos asegurar o garantizar que sea cierto lo que queremos. Es que podríamos tener la «mala» suerte de que todos hubieran nacido en diferentes días del año.
Nos vamos acercando a un punto interesante (y estoy seguro de que ustedes ya se dieron cuenta de lo que voy a escribir ahora). Porque si hubiera 365 personas en la sala, todavía no estaríamos en condiciones de asegurar que dos cumplen años el mismo día. Podría suceder que todos hubieran nacido en todos los posibles días de un año. Peor aun: ni siquiera con 366 (por los años bisiestos). Podría ser que justo con los 366 personas que tenemos en la sala, cubran exactamente todos los posibles días de un año sin repetición.
Sin embargo, hay un argumento categórico: si en la sala hay 367 personas, no hay manera de que se escapen: al menos dos tienen que soplar las velitas el mismo día.
Claro: uno no sabe cuáles son esas personas (pero ésa no era la pregunta), ni tampoco si hay nada más que dos que cumplen con la propiedad pedida. Puede ser que haya más… muchos más, pero eso no nos interesa. La garantía es que con 367 resolvemos el problema.
Ahora, teniendo en cuenta esta idea que acabamos de discutir, propongo otro problema: ¿qué argumento podemos encontrar para demostrarle a alguien que en la ciudad de Buenos Aires hay, por lo menos, dos personas con el mismo número de pelos en la cabeza?
Claramente, la pregunta se podría contestar rápido apelando a la gente «pelada». Seguro que en Buenos Aires hay dos personas que no tienen pelo, y por lo tanto, tienen el mismo número de pelos: ¡cero! De acuerdo. Pero obviemos estos casos. Encontremos un argumento que convenza a quien preguntó de lo que quiere saber, y sin apelar al recurso de cero pelos.
Antes de que yo escriba aquí la respuesta, una posibilidad es imaginar que si estoy proponiendo este problema en este lugar, inmediatamente después de haber discutido el problema de los cumpleaños, es que alguna relación debe haber entre ambos. No es seguro, pero es muy probable. ¿Entonces? ¿Alguna idea?
Una pregunta, entonces: ¿tiene usted idea de cuántos pelos puede tener una persona en la cabeza? ¿Alguna vez se lo cuestionó? No es que haga falta para vivir, pero… si uno tiene en cuenta el grosor de un pelo y la superficie del cuero cabelludo de cualquier persona, el resultado es que no hay manera de que nadie tenga más de 200.000 pelos. Y eso sería ya en el caso de King-Kong o algo así. Es imposible imaginar una persona con 200.000 pelos. Pero, de todas formas, sigamos con la idea.
Con este dato nuevo ahora, ¿de qué sirve saber que hay a lo sumo 200.000 pelos en la cabeza de una persona? ¿Qué hacer con él?
¿Cuántas personas viven en Buenos Aires? ¿Alguna idea? De acuerdo con el censo del año 2000, viven 2.965.403 personas en la Ciudad de Buenos Aires. Para la solución del problema, no hace falta tener el dato con tanta precisión. Basta con decir, entonces, que hay más de dos millones novecientas sesenta mil personas. ¿Por qué con estos datos es suficiente? ¿Por qué este problema es el mismo ahora que el de los cumpleaños? ¿Podrían tener acaso todos los habitantes de Buenos Aires un diferente número de pelos en la cabeza?
Creo que la respuesta clara. Juntando los dos datos que tenemos (el de la cota superior de pelos que una persona puede tener en su cabeza y el del número de habitantes de la ciudad), se deduce que inexorablemente se tiene que repetir el número de pelos entre personas. Y no sólo una vez, sino muchas, muchas veces. Pero esto ya no nos importa. Lo que nos interesa es que podemos contestar la pregunta.
MORALEJA: hemos usado un mismo principio para sacar dos conclusiones. Tanto en el problema del cumpleaños como en el de los pelos, hay algo en común: es como si uno tuviera un número de agujeritos y un número de bolitas. Si uno tiene 366 agujeritos y 367 bolitas, y las tiene que distribuir todas, es inexorable que tenga que haber por lo menos un agujerito que tiene dos bolitas. Y si uno tiene 200.000 agujeritos y casi tres millones de bolitas que piensa repartir, se reproduce el mismo escenario: seguro que hay agujeritos con más de una bolita.
Este principio se conoce con el nombre de «pigeon hole principle», o principio del «palomar». Si uno tiene un número de nidos (digamos «n») y un número de palomas (digamos «m»), si el número m es mayor que el número n entonces tiene que haber por lo menos dos palomas en algún nido.

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *