En esta entrada vemos algunos ejemplos más en donde se aplica el Principio de las Casillas.

Problema 5. Sean $a_1, a_2, … , a_n$ números enteros, no necesariamente todos diferentes. Prueba que existe un subconjunto de estos números, tal que su suma es divisible por $n$.

Solución. Consideremos los números $s_1, s_2,…, s_n$ los cuales definimos como sigue

\begin{align*}
s_1&=a_1\\
s_2&=a_1+a_2\\
s_3&=a_1+a_2+a_3\\
&\vdots\\
s_n&=a_1+a_2+ … +a_n.
\end{align*}

Tenemos que al dividir cada $s_i$ entre $n$ tenemos que el residuo varía de $0$ a $n-1$. Si el residuo es $0$ ya acabamos. Por otro lado, si ninguno de los residuos es cero, por el principio de las casillas tenemos que deben de existir al menos dos de los $s_i$´s que tengan el mismo residuo. Supongamos que son $s_j$ y $s_k$ con $j<k$.

Como $s_j$ y $s_k$ tienen el mismo residuo, tenemos que $s_k-s_j$ es divisible por $n$. Así el conjunto $S=\{s_{j+1}, s_{j+2}, \ldots , s_k \}$ es el conjunto tal que la suma de sus elementos es divisible por $n$.

$\square$

Problema 6.  Cada cuadrito de un tablero de ajedrez de $4\times 7$ es coloreado de blanco o negro. Prueba que en cualquier coloración siempre hay un rectángulo del tablero que tiene los cuatro cuadritos de las esquinas coloreadas del mismo color.

Solución. Podemos reducir el problema a un tablero de $3\times 7$, dado que cualquier rectángulo que se pueda crear en un tablero de $3\times 7$, también será un rectángulo en el tablero original. Ahora bien, pensemos en las posibles coloraciones que puede tener una columna en el tablero de $3\times 7$. Son dos colores acomodados en 3 lugares, así que tenemos 8 acomodos diferentes de coloración: $BBB, BBN, BNB, NBB, BNN, NBN, NNB, NNN$.

Notemos que si dos columnas tienen el mismo acomodo de colores, entonces acabamos (por ejemplo, dos columnas $BNB$ hacen un rectángulo de cuatro esquinas blancas).

Supongamos que usamos la coloración $BBB$ en una columna. Si en otra columna pintamos con alguno de $BBB, BBN, BNB, NBB$, entonces acabamos (usando dos de la $BBB$ y dos de esa otra). Si no, es que en las seis columnas restantes pintamos sólo con acomodos $BNN, NBN, NNB, NNN$. Por principio de las casillas, hay dos columnas pintadas con el mismo acomodo, y terminamos. Por simetría, si usamos la coloración $NNN$ entonces podemos hacer un argumento análogo.

Ya sólo nos quedan los casos en los que ninguna columna queda pintada ni con $BBB$ ni con $NNN$. Pero entonces tenemos que pintar las $7$ columnas con $6$ acomodos posibles. Por principio de las casillas, hay dos columnas que quedan pintadas con el mismo acomodo, y como ya vimos, esto crea el rectángulo con esquinas del mismo color.

$\square$

Problema 7. Si seleccionamos $n + 1$ enteros del conjunto $\{1, 2, \ldots 2n\}$, siempre hay dos de ellos tales que su máximo común divisor es $1$.

Solución. Tomemos al conjunto $\{1, 2, \ldots, 2n\}$. Si al tomar $n+1$ de ellos siempre logramos encontrar dos consecutivos, entonces el problema estará resuelto, ya que cualesquiera dos consecutivos son primos relativos. A la hora que seleccionamos $n+1$ enteros del conjunto dado, tenemos por el principio de casillas que al menos dos de ellos serán consecutivos. En efecto, dividamos a los números en las parejas $\{1,2\}$, $\{3,4\}$, $\ldots$, $\{2n-1,2n\}$. Estas son $n$ parejas, así que por casillas hubo una pareja de la que elegimos dos números. Estos son dos números consecutivos, así que que su máximo común divisor es $1$.

$\square$

Problema 8. En una grafo con un número finito de vértices, hay dos vértices con el mismo grado.

Solución. Sea $n$ el número de vértices de la gráfica, dado que el grado del vértice de un grafo es el número de aristas que concurren en dicho vértice. Tenemos que el grado de cada vértice varía de $0$ a $n-1$. Sin embargo si un vértice tiene grado cero, no existirá algún vértice con grado $n-1$. Por el principio de las casillas teniendo en cuenta que tenemos que distribuir $n-1$ valores en $n$ lugares, concluimos que al menos dos de los vértices deben de tener el mismo grado.

$\square$