sábado, 16 de abril de 2011

El principio del Palomar (Principio de las casillas)

En 1834, el matemático alemán Johann Peter Gustav Lejeune Dirichlet (1805-1859), creador del concepto moderno de la función, enunció el siguiente principio, llamado el Principio de la Cámara de palomas:

Si se tiene m palomas y n casilleros los cuales van a ser ocupados por las palomas. Si n> m, entonces un casillero debe ser ocupada por más de una paloma.


A pesar de ser muy intuitivo y sencillo, este teorema se pueden resolver algunos problemas curiosos.

Sólo por curiosidad, vamos a demostrar este resultado por inducción matemática.

Supongamos entonces el resultado válido para un cierto número n de casilleros y consideremos la situación de tener n+1 casilleros y m > n+1 casilleros. Queremos mostrar que el resultado vale también en este caso, por tanto por Inducción Matemática concluir que vale para todo número natural n. Después de acomodar todos las palomas en los n + 1 casilleros, escogemos un casillero al azar. Se en este casillero hay más de una paloma, nuestra afirmacion está aprobada. Si en este casillero no hay palomaalguna, en los n casilleross restantes están acomodados m > n + 1 > n objetos, o que, por la hipótesi inductiva, sucede que un casillero hay más de una paloma. Se en la casiller escogida hay una paloma, luego, en los n casilleros restantes, están distribuídos m - 1 > n palomas, o que, nuevamente, por la hipótesis inductiva, sucederá que en uno de los casilleros hay más de una paloma.


Dejamos algunos problemas para que sean resueltos por el lector:

1 - Hay n personas en una fiesta. Algunos conocidos, otros no. Mostrar que en la fiesta hay dos personas que tienen el mismo número de conocidos, suponiendo que la relación conocida es simétrica: si x es conocido de y, se tiene y es conocido de x, y no reflexivo: ninguno se conoce a sí mismo.

2 - Dentro de los cinco puntos seleccionados dentro de un triángulo equilátero de lado 1 cm, hay dos puntos que distan entre sí menos de 0,5 cm.

3 - Si todos los puntos del plano está pintado de rojo o azul, existe un rectángulo en el plano cuyos vértices son del mismo color.

4 - Existe dos potencias de 3 cuya diferencia es divisible por 2007.