Seminario de Resolución de Problemas: Principio de las Casillas, Parte 2

Continuamos con ejemplos de aplicación del 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

s_1=a_1
s_2=a_1+a_2
s_3=a_1+a_2+a_3

s_n=a_1+a_2+ ... +a_n

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×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×7, dado que cualquier rectángulo que se pueda crear en un tablero de 3×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×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

Deja una respuesta

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

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.