Principio De Casillas

Principio del Palomar

1

El Principio del Palomar
(Principio de las Casillas) El objetivo de este tema es familiarizarse con un principio elemental llamado “Principio del Palomar”, “Principio de los Casilleros”, o bien, “Principio de Dirichlet”, en honor a Peter Dirichlet, quien lo postuló originalmente. Antes de enunciar el principio veamos un ejemplo simple para fijar ideas: Ejemplo 1. Sien una sala hay 13 o más personas, entonces existe un par (quizá más) de personas cuyo cumpleaños cae el mismo mes. Es relativamente simple darse cuenta que lo anterior es cierto, pues como un año tiene 12 meses y hay más personas que meses, por obligación en algún mes estarán de cumpleaños 2 o más personas. Pongamos ahora en claro el principio, en su versión más simple (y más “literaria”).Principio del Palomar, de los Casilleros o de Dirichlet (primera versión) Si tenemos m palomares, y en ellos duermen m + 1 palomas, entonces hay al menos un palomar donde duerme más de una paloma. Este principio lo podemos extender no sólo a m + 1 “palomas” sino a cualquier número mayor que m. Para irnos familiarizando con el principio, en vez de usar “palomas” y “palomares” comenzaremos a usar“objetos” y “casilleros” que es como habitualmente se usa este principio. Principio del Palomar, de los Casilleros o de Dirichlet (segunda versión) Si se tiene un conjunto de n objetos, repartidos en m casilleros y n > m (hay más objetos que casilleros) entonces hay al menos un casillero donde hay 2 o más objetos. Si bien es cierto esta versión es bastante más general, aún podemos generalizarla un pocomás, de la siguiente manera: Principio del Palomar, de los Casilleros o de Dirichlet (versión general) Si se tiene un conjunto de n objetos, repartidos en m casilleros y n > km, con k un número natural, entonces hay al menos un casillero donde hay (k + 1) o más objetos.

Principio del Palomar

2

Esta última generalización pudiera, a primera vista no ser tan obvia, sin embargo después de unmomento es fácil convencerse de que es así. Pero en matemáticas, las afirmaciones no se asumen convenciéndose, es necesario dar una demostración a todo lo que se afirma. Por esa razón, a continuación demostraremos el principio: Demostración del Principio del Palomar. Supongamos que tenemos n objetos repartidos en m casilleros con n > km, y supongamos por contradicción que el principio es falso, esdecir, que no hay casilleros con (k + 1) o más objetos. Esto quiere decir que todos los casilleros tienen a lo más k objetos (k o menos objetos). Entonces el número de objetos que hay en los casilleros será igual a N1 + N2 +…+ Nm, siendo Ni el número de objetos del casillero i. Pero ya sabemos que en cada casillero hay k objetos o menos, luego: N1 ≤ k, N2 ≤ k,…, Nm ≤ k. Sumando las ecuacionesanteriores obtenemos que: N1 + N2 +…+ Nm ≤ km, es decir, el número total de objetos en los casilleros es menor o igual a km (n ≤ km). Pero esto es una contradicción ya que n > km. Luego, nuestra suposición de que el principio era falso es incorrecta. Por lo tanto, el Principio del Palomar es cierto. Ahora nos concentraremos en resolver algunos problemas que, a priori, pudieran ser muy difíciles deresolver sin esta nueva herramienta que acabamos de introducir. Problema 1. En un estadio hay 10, 000 personas. Demostrar que hay al menos un grupo de 28 personas que está de cumpleaños el mismo día. Solución. Bastaría considerar a las personas del estadio como nuestros “objetos” y a los días del año como nuestros “casilleros” (podemos “clasificar” a las personas según su día de cumpleaños). Así,tenemos que el número de personas es n = 10000 y el número de días del año es k = 366 (consideramos el caso fortuito de que haya personas nacidas en días 29 de febrero). Podemos notar, además, que 366 × 27 = 9882, entonces 10000 > 27 × 366 (es decir, k = 27), luego, el Principio del Palomar nos asegura que en alguno de los días del año hay 28 o más personas de cumpleaños. Problema 2. Sea un...