ENTRADAS

13 oct 2016

EL PRINCIPIO DEL PALOMAR

¿Existen dos personas en tu ciudad que tengan la misma cantidad de pelos en la cabeza?  Esta pregunta tiene una fácil respuesta si conocemos el llamado Principio del Palomar o principio de Dirichlet o principio de las cajas.

El principio del palomar nos dice que, si disponemos de n palomas y tenemos que distribuirlas en m palomares con m<n entonces, al menos, habrá un palomar con más de una paloma.

Esta afirmación puede parecer una perogrullada ya que, si queremos colocar las palomas en los palomares y tenemos más palomas que palomares, evidentemente, habrá palomas que compartirán palomar. Sin embargo, este principio da más de sí.

Principio del palomar

Principio del palomar

En su versión generalizada el principio del palomar afirma que si n>km para algún entero k, entonces existe un palomar que tiene k+1 palomas.

Dejemos a un lado las palomas para centrarnos en su aplicación. El principio se puede enunciar de la siguiente manera:

Sean dos conjuntos X (con n elementos) e Y (con m elementos), siendo  m<n. Se considera una aplicación f:X\rightarrow Y. Entonces existen dos elementos a, b de X tales que f(a)=f(b).

De forma más general se puede afirmar que si n>km para algún entero k, entonces hay al menos k+1 elementos distintos de X, que tienen la misma imagen, es decir:

\exists x_1,x_2,\cdots , x_{k+1} con f(x_1)=f(x_2)=\cdots =f(x_{k+1})

Si hacemos la analogía entre las dos formas de enunciar este principio, X representa al conjunto de palomas e Y a los palomares. La aplicación f es la que nos indica en qué palomar duerme cada paloma.

A la hora de resolver problemas mediante este método conviene tener claro qué elemento del problema representa las palomas y cuál el palomar.

Volvamos a continuación al problema inicial con el que comenzábamos este post. ¿Existen en tu provincia dos personas con el mismo número de pelos en su cabeza?.

Tengamos en cuenta que en una cabeza humana hay aproximadamente 150.000 pelos y que la ciudad tuviera, por ejemplo, 195.000 habitantes. En este caso los pelos juegan el papel de los palomares y los habitantes de las palomas. Se tiene por tanto que n=195.000 y m=150.000. Como n>m, podemos afirmar que existen al menos dos personas con el mismo número de pelos en la cabeza.

Pensemos por ejemplo en la provincia de Sevilla. Sevilla cuenta con 693.000 habitantes aproximadamente.

Tenemos n=693.000 y m=100.000. Además podemos comprobar fácilmente que n>4m, por lo tanto podemos afirmar que al menos existen 5 personas con la misma cantidad de pelos en la cabeza en la provincia de Sevilla.

Este principio fue enunciado por el matemático Gustav Dirichlet (1805-1859). Dirichlet planteó el problema “Con las nueve cifras significativas 1,2,3,4,5,6,7,8,9 si se seleccionan seis al azar, ¿Se puede afirmar que en cada selección tiene que haber necesariamente dos elementos cuya suma sea diez?”

Si observamos los pares cuya suma sea 10 estos son: (1,9), (2,8), (3,7), (4,6).

Si contamos las distintas formas que tenemos de escoger seis números de entre las nueve cifras, tenemos un total de 84 combinaciones posibles. Recordemos que no importa el orden y que evidentemente no hay repetición de cifras.

En este problema los pares cuyas sumas sean 10 son los palomares y las posibles elecciones de los seis números de entre los nueve posibles son las palomas. Evidentemente hay más palomas que palomares, por lo que por el principio del palomar podemos afirmar que al menos hay dos pares cuya suma sea 10.

Una curiosa aplicación de este principio la encontramos en el conocido como Teorema de la amistad enunciado por el matemático y filósofo Frank Plumton Ramsey (1903-1930) el cual nos dice:

“En cualquier grupo de seis personas del que cada par de personas son amigos o enemigos entonces existen tres mutuos amigos o tres mutuos enemigos”

Es decir, si tenemos un grupo de seis personas de los que dos a dos son o amigos o enemigos, entonces encontraremos un grupo de tres personas que sean los tres amigos o los tres enemigos.

Pensemos que hay sólo dos tipos de relación: Amigos o enemigos. Este valor constituyen los palomares, por lo tanto m=2.

Ahora sólo tenemos que contar cuántos grupos de tres personas podemos hacer de entre las seis personas que hay. Utilizando la combinatoria y teniendo en cuenta que no importa el orden y que, evidentemente, no puede haber repetición concluimos que hay 30 posibles grupos de amigos. Por lo que n=20.

En este caso tenemos que n>m, por lo que aplicando el principio del palomar se tiene que existen al menos tres mutuos amigos o tres mutuos enemigos.

Una de las principales aplicaciones del principio del palomar la encontramos en el campo de la informática, por ejemplo, en una tabla hash donde el número de posibles valores que pueden tomar los elementos de un vector exceden a menudo con sus índices.

Como podemos ver las matemáticas nos ayudan a resolver problemas que en principio poco o nada parecen tener que ver con ellas utilizando a veces técnicas muy sencillas como este principio del palomar que constituye una de las técnicas de resolución de problemas más importantes en matemáticas.

AUTOR: FRANCISCO MORANTE QUIRANTES @fdetsocial

Más entradas del autor para FdeT

Si quieres participar en el blog como colaborador en alguna de las secciones, envíanos un mail a info@fdet.es 

Grupo FdeT

Compartir:
Facebooktwittergoogle_pluslinkedin

1 Response

  1. Pingback : FdeT blog Cómo el HACKING se beneficia de la estadística

Leave a Reply

A %d blogueros les gusta esto: