8 Principio de las casillas

El principio de las casillas es también conocido como el principio del Palomar se enuncia como sigue:

(Principio de las casillas)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.

Este principio puede parecer tan obvio a simple vista que parecería un poco extraño estudiarle en un capitulo aparte. Pero como veremos, una gran variedad de problemas combinatorios pueden atacarse con este principio, especialmente aquellos en los que se desea demostrar la existencia de alguna situación. Veamos unos ejemplo muy sencillos.

Ejemplo. En cualquier grupo de seis personas, hay tres personas que se conocen todas entre sí o tres personas que no se conocen ninguna a la otra (asumiendo que si x conoce a Y entonces Y también conoce a X).
Consideremos una persona de las seis, digamos a A. Las restantes cinco personas caen en dos clases: conocen a A o no conocen A. Por principio de las casillas, una de esas clases debe tener al menos tres personas.
Supongamos que hay al menos tres personas que no conocen a A, si algún par de ellas no se conocen, junto con A ya son personas que no se conocen entre sí, y en el caso restante las tres personas se conocen todas entre sí. Un argumento similar se ocupa en el caso cuando las tres personas conocen a A.

Ejemplo. Algunos de los cuadritos de una cuadricula de 3 × 7 se pintan de negro y los otros se dejan en blanco. Probar que forzosamente las líneas de la cuadrícula forman un rectángulo en cuyas cuatro esquinas los cuadraditos tienen el mismo color (los cuatro blancos o los cuatro negros).
Solución. Supongamos que tenemos una cuadricula pintada de manera tal que no se forma el rectángulo con las esquinas del mimo color.Simbolicemos por N al color negro y por B al blanco, y observemos que los cuadritos de una columna pueden haber quedado pintados según las siguientes8 posibilidades :p₁=NNN,p₂=NNB,p₃,p₄=BNN,p₅=NBB,P₆=BNB,p₇=BBN,p₈=BBB.

Supongamos que una de las columnas esta pintada según la posibilidad p ₁; entonces con cualquiera de las posibilidades en que la columna tiene dos N`s se formara un rectángulo con las esquinas negras, así que ninguna columna está pintada así; pero entonces las columnas están solo pintadas según las según las posibilidades p ₁, p ₅,p ₆,p ₇,p ₈; como el número de columnas es 7, entonces el principio de las casillas nos dice que debe haber dos columnas iguales, pero aquí también, por el principio de las casillas, como son tres cuadritos en cada columna y sólo dos colores hay un color que se repite, y entonces es obvio que se forma un rectángulo con las esquinas del mismo color. Concluimos entonces que la posibilidad p ₁ no aparece. Lo mismo ocurre al considerar la posibilidad p ₈. Entonces ninguna de las posibilidades p ₁ y p ₈ aparece; pero así sobran sólo 6 posibilidades, con lo cual , otra vez aplicando el principio de las casillas, tenemos dos columnas iguales, y de ahí una contradicción.