Principio de las casillas

El principio de las casillas, también llamado principio del palomar, principio de Dirichlet o principio de las cajas dice lo siguiente básicamente:

Si se dispone de n casillas para colocar m objetos y m>n, entonces en alguna casilla deberán colocarse por lo menos dos objetos.

Una forma más general de enunciarlo:

Sean mn y p tres números naturales. Si se desean colocar np+m objetos en n casillas, alguna casilla debe contener al menos p+1 objetos.

Este principio puede parecer muy trivial, pero cuando se usa correctamente puede simplificar en gran medida los problemas que a simple vista parecen ser de combinatoria.

Ejemplo

Un costal está lleno de canicas de 20 colores distintos, hay el mismo número de canicas de cada color. Al azar se van sacando canicas del costal. ¿Cuál es el mínimo número de canicas que deben sacarse para poder garantizar que en la collección obtenida habrá al menos 100 canicas del mismo color?

Por el principio de las casillas, si sacas 21 canicas, al menos hay 2 del mismo color.

Si usamos la definición más general, cuando sacamos 41 canicas, hay al menos 3 del mismo color. Si sacamos 61, hay 4 canicas del mismo color, etc.

Tenemos que por cada múltiplo de 20 más 1, aseguramos cada vez más canicas.

Hagamos una tabla usando la definición general para visualizarlo mejor, sabiendo que tenemos 20 casillas (n = 20) y que necesitamos 1 canica de más en cada múltiplo de 20 para asegurar cierto número de canicas del mismo color (m=1).

número de canicas obtenidas\mathbf{np+m}Canicas del mismo color aseguradas
21(20\cdot 1)+12
41(20\cdot 2)+13
61(20\cdot 3)+14
\cdots
x(20\cdot p)+1p+1

Queremos saber a qué número de x canicas obtenidas tenemos aseguradas 100 canicas del mismo color, entonces p+1 = 100, despejamos: p=99. Lo reemplazamos en la fórmula (20\cdot p)+1:

x = (20\cdot 99)+1 = 1980+1 = 1981

Eso quiere decir que al sacar 1981 canicas, tenemos aseguradas 100 del mismo color, y tiene mucho sentido, porque en el peor de los casos, cada que sacamos 20, obtendríamos una de cada color, eso una y otra vez hasta hacerlo 99 veces, es decir, sacar 1980 canicas, después forzosamente la que se saque caerá en algún color y tendrá las 100 canicas.

Leave a Comment

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