Download Principio de Dirichlet o principio del palomar

Principio de Dirichlet o principio del palomar
¿Hay dos iguales?
60 personas están comparando sus móviles (cada persona tiene exactamente un móvil). Hay móviles de 4
fabricantes distintos, y cada fabricante produce 5 modelos distintos. Además, cada modelo puede tener
cámara y bluetooth, tener sólo bluetooth, o no tener ni bluetooth ni cámara. ¿Podemos garantizar que hay
dos móviles iguales? ¿Y si en vez de 60 personas son 61?
Hay 4 posibilidades para fabricante, 5 para modelo, y 3 para complementos, para un total de 60 posibles
tipos distintos de móviles. Si hay exactamente 60 móviles, pueden ser cada uno de un tipo, y no podemos
garantizar que hay dos iguales. Si hay 61 móviles, tiene que haber necesariamente dos iguales, pues si
fueran todos distintos, habría 61 tipos de móvil, pero sólo hay 60.
¿Cuántos iguales hay?
Supongamos ahora que, con los mismos tipos de móviles que en el caso anterior, hay 2009 personas.
Buscamos el tipo del que más móviles hay iguales. ¿Cuál es el máximo número de móviles de dicho tipo
que podemos garantizar que haya?
Conseguiremos que haya un número mínimo de móviles en cada tipo cuando distribuyamos los móviles
de la forma más equilibrada posible entre los 60 tipos distintos. Así, como 2009=60×33+29, podemos en
principio tomar 33 móviles de un mismo tipo, para 30 tipos distintos, y 34 móviles de un mismo tipo, para
otros 30 tipos distintos, para un total de
34 × 29 + 33 × 31 = 986 + 1023 = 2009 móviles.
No podemos entonces garantizar que haya más de 34 móviles iguales de cualquier tipo. Sí podemos
garantizar que va a haber más de 33 móviles de cada tipo, pues como 60×33=1980, en cuanto tengamos
más de 1980 móviles, tiene que haber al menos un tipo del que haya más de 33 móviles, pues si no habría
más de 60 tipos.
El principio del palomar
El principio del palomar, también llamado principio de Dirichlet, dice que, “si hay n huecos en un
palomar, y n+1 palomas, entonces hay al menos un hueco en el que viven al menos dos palomas”. Este
resultado se puede generalizar de la siguiente forma: si hay k conjuntos, y N elementos distribuidos en
dichos conjuntos, donde podemos escribir N=a×k+b, siendo a un entero no negativo y b uno de los
números (1,2,3,...,k), entonces hay al menos un conjunto que tiene al menos a+1 elementos. En el caso
anterior, teníamos 60 conjuntos (tipos de móviles), 2010 elementos (móviles), con lo que a=33 y b=30, y
tenemos al menos un tipo del que hay al menos a+1=34 móviles. Vemos ahora otro par de ejemplos, en
los que hay que “preparar el terreno” antes de aplicar el principio del palomar. Normalmente, esto suele
requerir, bien calcular el número de conjuntos, bien calcular el número de elementos que necesitamos en
cada conjunto, bien el número total de elementos, bien una combinación de estos cálculos.
Ejemplo 1: ¿Cuántos números que sean cuadrados perfectos (es decir, que sean el resultado de elevar al
cuadrado un entero) necesito como mínimo, para garantizar que hay al menos dos de ellos cuya diferencia
es múltiplo de 5?
Solución: si divido un número entero cualquiera entre 5, puedo obtener un cociente entero c, y un resto r
que puede tomar valores 0, 1, 2, 3 o 4, pudiendo escribir el número como 5c+r. Si elevo al cuadrado,
obtengo 5(5c2+2cr)+r2. Como r2 puede tomar valores 0, 1, 4, 9, o 16, el resto al dividir (5c+r)2 entre 5
sólo puede ser igual a 0 (si r=0), 1 (si r=1 o 4) o 4 (si r=2 o 3). La diferencia entre dos números es
múltiplo de 5, si y sólo si tienen el mismo resto al dividir entre 5, es decir, lo que me piden es que
garantice que hay al menos dos elementos en un mismo conjunto, de entre tres conjuntos posibles de
restos al dividir por 5 que puede tener un cuadrado perfecto. El principio del palomar me garantiza que
eso es cierto en cuanto hay 4 elementos distintos, y si tengo como máximo 3 elementos, puedo
distribuirlos hasta tener como mucho uno en cada conjunto (por ejemplo 1, 4 y 25). Luego tomando 4
cuadrados perfectos, puedo garantizar que la diferencia entre dos de ellos va a ser múltiplo de 5, pero no
con menos.
Ejemplo 2: dibujamos en el plano un hexágono regular de lado 3 metros, y pintamos en su interior o en su
frontera 2009 puntos rojos distintos. Demuestra que hay un triángulo equilátero de lado 1 metro, incluido
en el interior o la frontera del anterior, en cuyo interior o frontera hay al menos 38 puntos rojos distintos.
Solución: podemos dividir el hexágono regular en tres triángulos equiláteros de lado 3 metros, dibujando
sus diagonales mayores. Cada uno de estos triángulos puede ser a su vez dividido en 9 triángulos
equiláteros de lado 1 metro, dividiendo primero cada lado en tres segmentos iguales, y luego dibujando
por cada uno de los puntos de división líneas paralelas a los lados del triángulo (¡prueba tú mismo a hacer
el dibujo!). Tenemos así el hexágono dividido en 54 triángulos equiláteros de lado 1 metro, de forma que
los interiores y las fronteras de estos triángulos cubren completamente el interior y la frontera del
hexágono. Como 2009=54×37+11, y cada punto rojo, al estar en el hexágono, está en uno de los 54
triángulos, entonces por el principio del palomar hay al menos uno de los triángulos que contiene al
menos 38 puntos.
Ejercicios propuestos
En un país imaginario juegan a la quiniela de forma extraña: hay 14 partidos de los que hay que adivinar
el resultado, que puede ser 1, X o 2, y para ganar basta con acertar 5 resultados. ¿Cuántas quinielas hace
falta rellenar como mínimo para garantizar que con al menos una de ellas se gana? ¡No te conformes con
ver que con un número de quinielas está garantizado ganar, demuestra también que con menos no basta!
Pintamos los lados y las diagonales de un hexágono regular de rojo, o de azul (cada lado o cada diagonal
de un color, y sólo de uno, de forma independiente a como pintemos el resto de lados o diagonales).
Demostrar que siempre hay un triángulo cuyos vértices son vértices del hexágono, y cuyos lados son del
mismo color. ¿Puedo garantizar lo mismo si en vez de con un hexágono repito el proceso con un
pentágono?
Hay un conjunto de 17 números enteros distintos, ninguno de los cuáles es divisible por ningún número
primo mayor que 10. Demostrar que hay dos de ellos cuyo producto es un cuadrado perfecto.
Dividimos cada lado de un cuadrado en cuatro partes iguales, y se trazan las líneas paralelas a los lados
que pasan por las divisiones, de forma que el cuadrado queda dividido en 16 cuadraditos iguales. Cada
uno de los 25 puntos que son vértice de alguno de estos cuadraditos, se pinta de azul o de rojo
independientemente del color de los demás. Demuestra que entre estos 25 puntos, hay cuatro del mismo
color que son vértices de un rectángulo. ¿Qué pasaría si repitiéramos el problema pero dividiendo los
lados del cuadrado en tres partes iguales y considerando los 16 puntos resultantes?