7.3: El principio del encasillamiento
- Page ID
- 113976
La palabra “casillero” puede referirse a un agujero en el que una paloma duerme (es decir, más o menos como suena) o una serie de recesos aproximadamente cuadrados en un escritorio en el que se podría ordenar la correspondencia (ver Figura\(7.3.1\)).
Ya sea que prefieras pensar en aves dormidas o que se ordenen letras, la primera y más fácil versión del principio del encasillamiento es que si tienes más “cosas” de las que tienes “contenedores” debe haber un contenedor conteniendo al menos dos cosas.
Si tenemos\(6\) palomas que están tratando de dormirse en un gallinero con\(5\) casilleros, dos pájaros tendrán que compartir.
Si tenemos\(7\) letras para ordenar y hay\(6\) casilleros en nuestro escritorio, tendremos que poner dos letras en el mismo compartimento.
Las “cosas” y los “contenedores” no necesariamente tienen que interpretarse en el sentido estricto de que las “cosas” van a los “contenedores”. Por ejemplo, una buena aplicación del principio del casillero es que si hay al menos\(13\) personas presentes en una habitación, algún par de personas habrán nacido en el mismo mes. En este ejemplo, las cosas son las personas y los contenedores son los meses del año.
La forma abstracta de expresar el principio del casillero es:
Si f es una función tal que\(|\text{Dom}(f)| > |\text{Rng}(f)|\) entonces no\(f\) es inyectiva.
La prueba de esta afirmación es un ejemplo fácil de prueba por contradicción por lo que la incluiremos aquí.
- Prueba
-
Supongamos al contrario que\(f\) es una función con\(|\text{Dom}(f)| > |\text{Rng}(f)|\) y eso\(f\) es inyectivo. Por supuesto que\(f\) está en su rango, así como estamos presumiendo que\(f\) es inyectivo se deduce que\(f\) es una bijección entre\(\text{Dom}(f)\) y\(\text{Rng}(f)\). Por lo tanto (ya que\(f\) proporciona una correspondencia uno a uno)\(|\text{Dom}(f)| = |\text{Rng}(f)|\). Esto contradice claramente la afirmación de que\(|\text{Dom}(f)| > |\text{Rng}(f)|\).
Q.E.D.
Para una declaración con una prueba casi trivial el principio del casillero es muy poderoso. Podemos usarlo para probar una serie de resultados existenciales —algunos son bastante tontos, otros muy profundos. Aquí hay algunos ejemplos:
Hay dos personas (que no son calvas) en la ciudad de Nueva York que tienen exactamente el mismo número de pelos en la cabeza.
Hay dos libros en (inserta tu biblioteca favorita) que tienen el mismo número de páginas.
Dadas las parejas\(n\) casadas (entonces\(2n\) las personas) si elegimos a\(n + 1\) las personas nos veremos obligados a elegir a ambos miembros de alguna pareja.
Supongamos que seleccionamos\(n + 1\) números del conjunto\(\{1, 2, 3, . . . , 2^n\}\), nos veremos obligados a haber elegido dos números de tal manera que uno sea divisible por el otro.
Podemos llegar a formas más fuertes del principio de los encasillados al considerar los casilleros con capacidades. Supongamos que tenemos\(6\) casilleros en un escritorio, cada uno de los cuales puede contener\(10\) letras. ¿Qué número de letras garantizará que uno de los casilleros esté lleno? El mayor número de letras que podríamos tener sin tener\(10\) en algún casillero es\(9 · 6 = 54\), así que si hay\(55\) letras debemos tener\(10\) letras en algún casillero.
De manera más general, si tenemos\(n\) contenedores, cada uno capaz de contener m objetos, que si hay\(n · (m − 1) + 1\) objetos colocados en los contenedores, estaremos seguros de que uno de los contenedores está a su capacidad.
El principio de casillero ordinario es el caso especial\(m = 2\) de esta versión más fuerte.
Existe una versión aún más fuerte, que normalmente se conoce como la “forma fuerte del principio del encasillamiento”. En la forma fuerte, tenemos casilleros con una variedad de capacidades.
Si hay\(n\) contenedores que tienen capacidades\(m_1, m_2, m_3, . . . , m_n\), y hay\(1 + \sum^{n}_{i=1}(m_i − 1)\) objetos colocados en ellos, entonces para algunos\(i\), el contenedor\(i\) tiene (al menos)\(m_i\) objetos en él.
- Prueba
-
Si ningún contenedor tiene toda su capacidad, entonces el mayor que podría ser el total de los objetos es\(\sum^{n}_{i=1}(m_i − 1)\).
Q.E.D.
Ejercicios:
La afirmación de que hay dos neoyorquinos no calvos con el mismo número de pelos en la cabeza requiere algunas estimaciones cuidadosas para justificarlo. Por favor justifícalo.
Una matemática, que siempre se levanta antes que su cónyuge, ha desarrollado un esquema —utilizando el principio del encasillamiento— para asegurarse de que siempre tenga un par de calcetines a juego. Ella solo guarda calcetines azules, calcetines verdes y calcetines negros en su cajón de calcetines —\(10\) de cada uno. Para no despertar a su marido deberá seleccionar alguna cantidad de calcetines de su cajón en la madrugada oscura y llevarlos con ella al baño adyacente donde se viste. ¿Qué número de calcetines elige?
Si seleccionamos\(1001\) números del conjunto\(\{1, 2, 3, . . . , 2000\}\) es seguro que habrá dos números seleccionados de tal manera que uno divide al otro. Podemos probar este hecho señalando que cada número en el conjunto dado se puede expresar en la forma\(2^k · m\) donde\(m\) es un número impar y usando el principio de casillero. Redacte esta prueba.
Dado cualquier conjunto de\(53\) enteros, mostrar que hay dos de ellos que tienen la propiedad de que ya sea su suma o su diferencia es uniformemente divisible por\(103\).
Demostrar que si los\(10\) puntos se colocan dentro de un cuadrado de longitud lateral\(3\), habrá\(2\) puntos uno dentro\(\sqrt{2}\) del otro.
Demostrar que si los\(10\) puntos se colocan dentro de un triángulo equilátero de longitud lateral\(3\), habrá\(2\) puntos uno dentro\(1\) del otro.
Demostrar que en una gráfica simple (una gráfica no dirigida sin bucles ni aristas paralelas) que tenga\(n\) nodos, debe haber dos nodos que tengan el mismo grado.