Principio de las casillas#

Introducción#

El principio de las casillas es una idea sencilla. A grandes rasgos, nos dice que si hay muchos elementos que se deben repartir en pocas casillas, entonces debe haber una casilla con muchos objetos. Un ejemplo muy sencillo es que si tenemos 13 personas, entonces debe haber por lo menos dos que compartan el mismo mes de cumpleaños. Aunque la idea de principio de las casillas sea simple, se presta a muchas aplicaciones y generalizaciones.

Principio de las casillas, versión básica#

El principio de las casillas, en su versión más básica, dice lo siguiente:

Proposición. Si se tienen \(n+1\) objetos que se deben repartir en \(n\) casillas, entonces debe haber al menos una casilla en donde se colocaron al menos dos objetos.

Veamos algunos problemas en donde podemos aplicar este principio para resolverlos.

Problema. Encuentra la máxima cantidad de reyes de ajedrez que puedes poner en un tablero de \(5\times 5\) sin que se ataquen entre sí.

Solución. Hay una forma sencilla de poner \(9\) reyes sin que se ataquen entre sí.

../_images/reyes-acomodo.svg

¿Cómo podemos estar totalmente seguros de que no hay ninguna forma de poner \(10\) o más reyes? Dividamos el tablero como sigue:

../_images/reyes-casillas.svg

Aquí hemos creado \(9\) regiones. Si pusiéramos \(10\) reyes, entonces habría dos que caen en la misma región. Dos reyes en una misma región claramente se atacarían entre sí. Así, es imposible poner \(10\) reyes o más, y por lo tanto lo máximo que podemos poner son \(9\). \(\square\)

En el problema anterior las casillas son las regiones que creamos. Las casillas no necesariamente son algo geométrico, y pueden referirse a ideas más abstractas.

Problema. Muestra que para cualquier entero positivo \(n\), existe un múltiplo de \(n\) que consiste de puros dígidos cero y uno.

Solución. Consideremos el conjunto de \(n+1\) números \(S=\{1,11,111,\ldots,11\cdots 1\}\), en donde el último número tiene \(n+1\) unos. Cuando dividimos cualquier entero entre \(n\), sólo hay \(n\) posibilidades para el residuo que pueden dejar: \(0,1,\ldots,n-1\). Como hay \(n+1\) números en \(S\) y \(n\) posibles residuos, por el principio de las casillas hay dos elementos en \(S\) que dejan el mismo residuo al dividirlos entre \(n\), digamos \(a\) y \(b\) con \(a\lt b\). De esta manera, \(b-a\) es un número que es múltiplo de \(n\) y que consiste únicamente de ceros y unos. \(\square\)

Principio de las casillas, versión con más objetos#

Si aumentamos la cantidad de objetos que debemos repartir, pero dejamos fija la cantidad de casillas, entonces es posible garantizar todavía más: que hay una casilla con muchos objetos. Por ejemplo, si tenemos \(25\) personas, ahora podemos garantizar que hay \(3\) que tienen el mismo mes de cumpleaños. La versión precisa está dada por el siguiente resultado:

Proposición. Si se tienen \(kn+1\) objetos o más que se deben repartir en \(n\) casillas, entonces debe haber al menos una casilla en donde se colocaron al menos \(k+1\) objetos.

La justificación es sencilla argumentando al revés: si en cada casilla hubiera a lo mucho \(k\) objetos, entonces en total tendríamos a lo mucho \(kn\) objetos.

Problema. Demuestra que si se colocan \(9\) puntos dentro de un cuadrado de lado \(4\), entonces habrá tres de ellos que hagan un triángulo con área menor o igual a \(2\).

Solución. Dividamos al cuadrado en \(4\) cuadraditos de lado \(2\). Como tenemos \(9=2\cdot 4 +1\) puntos, entonces hay uno de estos cuadraditos que tiene a tres de los puntos que colocamos.

../_images/cuadrado22.svg

Afirmamos que el área de un triángulo \(ABC\) dentro de un cuadrado de lado \(2\) es como mucho \(2\).

Lo primero que observamos es que podemos suponer que los vértices están sobre los lados del cuadrado. Si, por ejemplo, el vértice \(A\) no está en uno de los lados del cuadrado, entonces podemos prolongar el rayo \(BA\) para intersectar a un lado del cuadrado en un punto \(A'\). El triángulo \(A'BC\) tiene mayor área que el \(ABC\) por contenerlo, y por lo tanto basta con ver que \(A'BC\) tiene área menor o igual a \(2\).

../_images/hacia-lado.svg

Lo siguiente es argumentar por qué podemos suponer que cada vértice está sobre un vértice del cuadrado. Supongamos que no. Si \(A\) está en el lado \(PQ\) del cuadrado, pero no en el vértice \(P\) ó \(Q\), entonces podemos mover a \(A\) hacia \(P\) o hacia \(Q\) y preservar el área o aumentarla.

../_images/hacia-vertice.svg

De este modo, podemos llevar cualquier triángulo a un triángulo \(ABC\) de área mayor y con vértices sobre los vértices del cuadrado. Cualquier triángulo así o bien es degenerado, o bien es de área \(\frac{2\cdot 2}{2}=2\). \(\square\)

Una versión equivalente es la siguiente.

Proposición. Si se tienen \(m\) objetos o más que se deben repartir en \(n\) casillas, entonces debe haber al menos una casilla en donde se colocaron al menos \(\lceil \frac{m}{n}\rceil\) objetos.

Como ejemplo sencillo, si tenemos \(100\) personas, entonces hay \(\lceil\frac{100}{12}\rceil=9\) de ellas que tienen el mismo mes de cumpleaños. Veamos un problema un poco más elaborado.

Problema. Se tienen \(601\) caballos en un tablero de ajedrez de \(30\times 30\). Demuestra que hay dos de ellos que se atacan entre sí.

Solución. Tracemos rayas cada 3 filas y cada 3 columnas para dividir a todo el tablero en \(100\) regiones de \(3\times 3\) cada una. Como hay \(501\) caballos, entonces hay una de ellas en donde colocamos por lo menos \(\lceil\frac{501}{100}\rceil=6\) caballos. Veremos que en esta región hay dos caballos que se atacan entre sí. Esto lo hacemos argumentando mediante otro principio de las casillas como sigue. Nombremos las casillas del tablero de \(3\times 3\) de la siguiente manera:

../_images/caballos-3.svg

Tenemos \(5\) regiones: las de la letra \(A\), la letra \(B\), la letra \(C\), la letra \(D\) y la letra \(E\). Por el principio de las casillas básico, como hay \(6\) caballos en este tablero de \(3\times 3\), hay por lo menos dos en una misma región. No puede ser la región \(E\) pues esa consiste de una sola casilla. Con esto terminamos pues cualquiera de las otras regiones consiste de dos casillas en donde los caballos se pueden atacar entre sí. \(\square\)

Principio de las casillas, versión infinita#

Una última versión del principio de las casillas que veremos ahora es la versión infinita. Dice lo siguiente.

Proposición. Si se tiene una infinidad de objetos que se deban repartir en una cantidad finita de casillas, entonces debe haber al menos una casilla con una infinidad de objetos.

Veamos un ejemplo sencillo. Tomemos \(\pi\) en su expresión decimal:

\[\pi=3.1415926535\ldots\]

Notemos que el \(5\) aparece tres veces hasta aquí. ¿Será que aparece una infinidad de veces en la expresión decimal de \(\pi\)? Nadie lo sabe, es una pregunta abierta. Y el \(5\) no tiene nada de particular. Para ninguno de los dígitos se sabe si aparece una infinidad de veces en la expresión decimal de \(\pi\) o no. Sin embargo, sí hay algo que podemos decir. Como hay una infinidad de dígitos y únicamente existen los dígitos de \(0\) a \(9\), entonces por el principio de las casillas debe existir uno de ellos que se repite una infinidad de veces dentro de \(\pi\). ¿Cuál? Quién sabe.

Terminemos con un problema más que usa el principio de las casillas en su versión infinita.

Problema. Se tiene un tablero de \(n\) casillas colocadas horizontalmente. En cada casilla se ha colocado una flecha, ya sea apuntando hacia la izquierda, o hacia la derecha. Una hormiga comienza en la casilla de hasta la izquierda. Se va a mover de acuerdo a las siguientes reglas:

  • Si está en la casilla de hasta la izquierda, y la flecha apunta a la izquierda, la hormiga no hace nada y la flecha apunta ahora a la derecha.

  • Si está en la casilla de hasta la derecha, y la flecha apunta a la derecha, entonces la hormiga gana el juego y sale del tablero.

  • En cualquier otro caso, la hormiga se mueve a la dirección que indica la flecha, y ya que pasó esto, la flecha apunta hacia el otro lado.

Muestra que sin importar cómo están colocadas las flechas inicialmente, la hormiga gana.

Quizás quieras jugar un poco con el problema antes de ver la solución. La siguiente función recibe como argumentos la variable n que da el tamaño del tablero, la variable flechas a la que se le puede poner la configuración inicial que se desee y la variable pasos que indica cuántos pasos se quieren dar como máximo. Va mostrando el tablero, en donde la x indica a la hormiga y avisa cuando haya salido.

def hormiga(n,tablero,maxpasos):
    posicion=0
    tablero=list(tablero)
    for j in range(maxpasos):
        if posicion==0 and tablero[posicion]=="<":
            tablero[posicion]=">"
        elif posicion==n-1 and tablero[posicion]==">":
            print("La hormiga salió")
            return
        else:
            if tablero[posicion]==">":
                tablero[posicion]="<"
                posicion+=1
            elif tablero[posicion]=="<":
                tablero[posicion]=">"
                posicion-=1
        print(posicion*' '+'x'+(n-posicion-1)*" "+'\n'+"".join(tablero))

hormiga(4,'<<>>',10)

x   
><>>
 x  
<<>>
x   
<>>>
x   
>>>>
 x  
<>>>
  x 
<<>>
   x
<<<>
La hormiga salió

Solución. Vamos a demostrar que la hormiga siempre sale. Para ello, procederemos por contradicción. Supongamos que la hormiga nunca sale. Entonces, se queda siempre dentro del tablero, dando una infinidad de pasos. Como sólo hay una cantidad finita \(n\) de casillas dentro del tablero, entonces hay alguna casilla \(C\) que la hormiga visita una infinidad de veces.

Pero como en cada visita las flechas de \(C\) alternan dirección, entonces también se visita una infinidad de veces las casillas adyacentes a \(C\). Pero este argumento aplica también para las adyacentes a ellas, y en general, para todas las casillas. De este modo, todas las casillas son visitadas una infinidad de veces. En partícular, la casilla de hasta la derecha es visitada una infinidad de veces. Así, como mucho tras dos veces de visitarla la hormiga saldría del tablero. Esto da la contradicción buscada. \(\square\)

Tarea moral#

Los siguientes problemas te ayudarán a practicar lo visto en esta entrada. Para resolverlos, necesitarás usar herramientas matemáticas, computacionales o ambas.

  1. Investiga aproximadamente cuántos pelos tiene una persona en el cabello. Usa esto y el principio de las casillas para mostrar que en México hay dos personas con el mismo número de pelos en el cabello. ¿Habrá \(100\) personas con la misma cantidad de pelos en el cabello? Explica tus suposiciones.

  2. ¿Cuál es la máxima cantidad de alfiles que se pueden colocar en un tablero de ajedrez sin que se ataquen entre sí?

  3. Demuestra que si se tienen \(9\) puntos con coordenadas enteras en \(\mathbb{R}^3\), entonces hay dos de ellos cuyo punto medio también tiene coordenadas enteras.

  4. Demuestra que para cualquier entero positivo \(k\) se tiene que la sucesión de Fibonacci tiene una infinidad de múltiplos de \(k\).

  5. Sea \(k\) un entero positivo. Se pintan todos los puntos con coordenadas enteras del plano con \(k\) colores. Muestra que sin importar cómo sea la coloración, siempre existe un rectángulo con lados paralelos a los ejes y cuyos vértices son cuatro puntos de coordenadas enteras pintados del mismo color.