10.1: El principio del encasillamiento

El Principio de Pigeonhole es una técnica que puedes aplicar cuando te enfrentas a artículos elegidos de una serie de categorías diferentes de artículos, y quieres saber si algunos de ellos deben o no provenir de la misma categoría, sin mirar todos los artículos.

Ejemplo\(\PageIndex{1}\)

Supongamos que voy a estar impartiendo un curso de estudio independiente en teoría de grafos a dos estudiantes el próximo semestre, y quiero usar el libro de texto “Teoría de gráficos” de Bondy & Murty. Se ha emitido en dos ediciones, y no me importa qué edición usemos, pero quiero que ambos alumnos tengan la misma edición.

Encuentro un sitio web en el que alguien ha publicado que tiene tres copias del texto a la venta, pero no dicen qué ediciones son. Sin más información, sé que si compro estos textos, tendré textos adecuados para mis alumnos.

El razonamiento es sencillo. El primer libro podría ser edición\(1\) o edición\(2\). Si el segundo texto es el mismo que el primero, entonces tengo lo que necesito, así que el único problema posible es si los dos primeros libros constan de una copia de edición\(1\), y una copia de edición\(2\). Pero entonces el tercer libro debe coincidir con uno u otro de los dos primeros, ya que sólo hay dos ediciones, por lo que tendré dos copias de una u otra de las ediciones.

Esta idea se puede generalizar de varias maneras. Primero veremos la generalización más sencilla.

Proposición\(\PageIndex{1}\): Pigeonhole Principle

Si hay\(n\) artículos que caen en\(m\) diferentes categorías y\(n > m\), entonces al menos dos de los artículos deben caer en la misma categoría.

Prueba

Entre los primeros\(m\) artículos, o bien dos de los artículos son de la misma categoría (así que estamos hechos), o hay exactamente un artículo de cada una de las\(m\) categorías. Ya que\(n > m\), hay al menos un artículo más. Este artículo debe caer en la misma categoría que uno de los artículos anteriores ya que cada categoría ya tiene un artículo.

El nombre de este principio proviene de la idea de que se puede afirmar con las categorías siendo una fila de agujeros, y siendo los artículos palomas que se asignan a estos hoyos.

En el Ejemplo 10.1.1, las categorías fueron las ediciones, y los ítems fueron los libros de texto.

El Ejemplo 10.1.1 fue una aplicación muy directa y directa del Principio de Pigeonhole. El Principio también puede aplicarse de formas mucho más sutiles y sorprendentes.

Ejemplo\(\PageIndex{2}\)

María hace una apuesta con Juan. Debe comprarle al menos una barra de chocolate todos los días para los próximos\(60\) días. Si, al final de ese tiempo, no puede señalar un lapso de días consecutivos en el que el número de barras de chocolate que le dio fue precisamente\(19\), entonces ella pagará por todas las barras de chocolate y se las devolverá. Si puede encontrar tal lapso, entonces consigue quedarse con las barras de chocolate. Para limitar el tamaño de la apuesta, acuerdan de antemano que Juan no comprará más que barras de\(100\) chocolate en total.

¿Hay alguna manera de que Juan gane esta apuesta?

Solución

La respuesta es no. Para\(1 ≤ i ≤ 60\), vamos a\(a_i\) representar el número de barras de chocolate que Juan ha comprado para María al final del día\(i\). Entonces\(1 ≤ a_1 < a_2 < . . . < a_{60} ≤ 100\). María espera que para algunos\(i < j\), ella pueda encontrar eso\(a_i + 19 = a_j\). Por lo tanto, también necesitamos considerar los valores\(a_1 + 19 < a_2 + 19 < . . . < a_{60} + 19\). Por los límites en\(a_1\) y\(a_{60}\), tenemos\(a_1 + 19 ≥ 20\), y\(a_{60} + 19 ≤ 119\). Así, los valores\(a_1, . . . , a_{60}, a_1 + 19, . . . , a_{60} + 19\) son\(120\) números todos los cuales se encuentran entre\(1\) y\(119\).

Por el Principio Pigeonhole, al menos dos de estos números deben ser iguales, pero sabemos que las\(a_i\) s están aumentando estrictamente (como son las\(a_i + 19\) s), por lo que debe existir alguna\(i < j\) tal que\(a_i + 19 = a_j\). María debe señalar el lapso de días desde el inicio del día\(i + 1\) hasta el final del día\(j\) ya que en este lapso Juan le regaló barras de\(19\) chocolate.

De hecho, Juan no pudo ganar una apuesta de esta naturaleza que duró más de\(56\) días, pero demostrarlo requiere un análisis más detallado específico de los números involucrados, y no es realmente relevante para este curso.

Aquí hay otro ejemplo que sería difícil de probar si no conocieras el Principio de Pigeonhole.

Ejemplo\(\PageIndex{3}\)

Fije\(n\) y coloree cada punto del plano con uno de los\(n\) colores. Demostrar que existe un rectángulo cuyas cuatro esquinas son del mismo color.

Solución

Toma una cuadrícula de puntos con\(n + 1\) filas y\(n \binom{n+1}{2} + 1\) columnas. Afirmamos que esta cuadrícula contendrá tal rectángulo

Dado que se han utilizado n colores, y hay\(n+1\) puntos en cada columna, según el Principio Pigeonhole cada columna debe contener al menos dos puntos de cuadrícula que sean del mismo color.

En cualquier columna, existen\(\binom{n+1}{2}\) posibles ubicaciones en las que podría aparecer un par de puntos del mismo color. Por lo tanto, hay a lo sumo\(\binom{n+1}{2}\) formas de posicionar dos puntos de color\(1\) en una columna para que los puntos no ocupen las mismas dos ubicaciones en más de una de estas columnas. Lo mismo es cierto para cada uno de los\(n\) colores. Por lo tanto, podemos crear un máximo de\(n \binom{n+1}{2}\) columnas, cada una teniendo dos puntos de algún color, de tal manera que se evite que el mismo color ocupe las mismas dos ubicaciones en más de una de las columnas. Como tenemos\(n \binom{n+1}{2} + 1\) columnas, debe existir algún par de columnas de tal manera que el mismo color sí ocupe las mismas dos ubicaciones en ambas columnas. Estos cuatro puntos forman un rectángulo cuyas esquinas tienen todas el mismo color.

Hasta el momento sólo hemos pensado en garantizar que haya al menos dos artículos en alguna categoría. A veces podríamos querer saber que hay al menos\(k\) artículos en alguna categoría, dónde\(k > 2\). Existe una generalización del Principio de Paloma que se aplica a tales situaciones.

Proposición\(\PageIndex{2}\): Generalised Pigeonhole Principle

\(n\)Dados los ítems que caen en\(m\) diferentes categorías, si\(n > km\) para algún entero positivo\(k\), entonces al menos\(k + 1\) de los ítems deben caer en la misma categoría.

Prueba

Entre los primeros\(km\) artículos, cualquiera\(k + 1\) de los artículos son de la misma categoría (así estamos hechos), o hay exactamente\(k\) artículos de cada una de las\(m\) categorías. Ya que\(n > km\), hay al menos un artículo más. Este artículo debe pertenecer a la misma categoría que uno de los artículos anteriores. Dado que cada categoría ya tiene\(k\) artículos, esto significa que habrá\(k + 1\) artículos en esta categoría.

Observe que el Principio de Paloma es un caso especial del Principio de Agujero Generalizado, obtenido tomando\(k = 1\).

Ejemplo\(\PageIndex{4}\)

La población de West Lethbridge en el\(2014\) censo era\(35\),\(377\). Demuestre que al menos\(97\) residentes de West Lethbridge comparten un cumpleaños. Si vives en West Lethbridge, ¿cuántas personas puedes estar seguro de que tienen el mismo cumpleaños que tú?

Solución

Para la primera parte de esta pregunta, aplicamos el principio de encasillamiento generalizado, con\(m = 366\) (para los\(366\) días del año, contando febrero\(29\) ya que es un cumpleaños tan legítimo como cualquier otro a pesar de ser más infrecuente),\(k = 96\), y\(n = 35, 377\). Tenemos

\(n = 35, 377 > km = 96 · 366 = 35, 136,\)

por lo que el Principio de encasillamiento Generalizado nos dice que al menos la\(k + 1 = 97\) gente debe compartir un cumpleaños.

Para la segunda parte de la pregunta, la respuesta es\(0\). No hay razón por la que cada otra persona en West Lethbridge pueda no tener su cumpleaños el día siguiente al suyo (aunque esa posibilidad particular es bastante poco probable). Ciertamente no hay garantía de que ninguno de ellos tenga el mismo cumpleaños que el suyo.

Observe que aunque hemos encontrado en el ejemplo anterior que algún grupo de al menos\(97\) personas en West Lethbridge debe tener el mismo cumpleaños, no tenemos idea de qué\(97\) personas están involucradas, o de cuál es el cumpleaños conjunto. Esto es bastante notable, pero es un ejemplo de un tipo de prueba que es bastante común en las matemáticas avanzadas. Tales pruebas son referidas como “no constructivas”, ya que prueban que algo existe, sin darle idea alguna de cómo encontrar (o construir) tal cosa.

La prueba del siguiente teorema implica una aplicación más sutil del Principio de Paloma Generalizado.

Teorema\(\PageIndex{1}\): Erdös-Szekeres Theorem

Por cada par de números enteros\(a\),\(b ≥ 1\), si\(S\) es una secuencia de números reales\(ab + 1\) distintos, entonces hay una subsecuencia creciente de longitud\(a + 1\) o una subsecuencia decreciente de longitud\(b + 1\) en\(S\).

Prueba

Define una función f que mapee cada elemento de\(S\) a la longitud de la subsecuencia creciente más larga que comienza con ese elemento.

Si existe alguna\(s ∈ S\) tal que\(f(s) ≥ a + 1\), entonces ya terminamos. Entonces podemos suponer que\(f(s) ≤ a\) para cada uno\(s ∈ S\). Dado que siempre hay una secuencia creciente de longitud al menos\(1\) comenzando en cualquier elemento de\(S\), de hecho tenemos\(1 ≤ f(s) ≤ a\) para cada\(s ∈ S\), por lo que hay unos valores posibles para las salidas de\(f\). Desde\(|S| = ab + 1\), y\(ab + 1 > ab\), el Principio de Agujero Generalizado nos dice que al menos\(b+ 1\) los elementos de\(S\) deben tener la misma salida bajo la función\(f\).

Afirmamos que si\(x\) es antes\(y\) en\(S\) y\(f(x) = f(y)\), entonces\(x > y\). Por suposición,\(x \neq y\) (todos los valores de\(S\) son distintos), por lo que la única otra posibilidad es\(x < y\). Si\(x < y\), entonces tomando\(x\) seguido de una subsecuencia creciente de longitud\(f(y)\) que comienza en\(y\), daría una subsecuencia creciente de longitud\(f(y) + 1\) que comienza en\(x\), contradicción\(f(x) = f(y)\). Esta contradicción demuestra que no\(x < y\) es posible, así\(x > y\), como se afirma.

Dejar\(s_1, s_2, . . . , s_{b+1}\) que los elementos de\(S\) eso tengan la misma salida bajo\(f\), y aparezcan en este orden. Entonces por la afirmación probamos en el párrafo anterior,\(s_1 > s_2 > . . . > s_{n+1}\), que es una subsecuencia decreciente de longitud\(b + 1\).

De hecho,\(ab + 1\) es la menor longitud posible para\(S\) eso garantiza esta propiedad. Para cualquiera\(a\),\(b\), existe una secuencia de longitud\(ab\) en la que la secuencia creciente más larga tiene longitud\(a\) y la subsecuencia decreciente más larga tiene longitud\(b\). Una de esas secuencias es

\[b, b − 1, . . . , 1; 2b, 2b − 1, . . . , b + 1; . . . ; ab, ab − 1, . . . ,(a − 1)b + 1\]

Cualquier subsecuencia creciente solo puede tener una entrada de cada una de las\(a\) subsecuencias de longitud\(b\) que están separadas por punto y coma, por lo que solo puede tener longitud\(a\). Cualquier subsecuencia decreciente debe estar completamente contenida dentro de una de las subsecuencias de longitud\(b\) que están separadas por punto y coma, por lo que solo puede tener longitud\(b\).

Proposición\(\PageIndex{3}\): Even More Generalised Pigeonhole Theorem

Dejar\(n_1, n_2, . . . , n_m\) ser enteros positivos. Dado al menos

\[n_1 + n_2 + . . . + n_m − m + 1\]

artículos que entran en\(m\) categorías, debe haber algunos de\(1 ≤ i ≤ m\) tal manera que al menos\(n_i\) los artículos caigan dentro de la\(i^{\text{th}}\) categoría.

Prueba

Entre los primeros

\(n_1 + n_2 + . . . + n_m − m\)

artículos, o bien hay algunos\(1 ≤ i ≤ m\) tales que al menos ni de los artículos entran en la\(i^{\text{th}}\) categoría, o hay precisamente\(n_i − 1\) objetos en la i-ésima categoría, para cada uno\(1 ≤ i ≤ m\). Dado que hay al menos un artículo más, este artículo debe caer en la\(i^{\text{th}}\) categoría para algunos\(1 ≤ i ≤ m\), lo que significa que habrá\(n_i\) artículos en esta categoría.

Observe que el principio de encasillamiento generalizado es un caso especial del “principio de encasillamiento aún más generalizado”, obtenido tomando

\[n_1 = n_2 = . . . = n_m = k.\]

Ejemplo\(\PageIndex{5}\)

Supongamos que Ali le debe a Tomas\($10\), y quiere darle una serie de monedas idénticas para pagar su deuda. Su banco solo da moneda en loonies, twonies, billetes de cinco dólares o billetes de diez dólares, y no acepta solicitudes de tipos específicos de moneda. ¿Cuánto dinero debe pedir Ali al cajero, si quiere estar segura de tener\($10\) en piezas idénticas de moneda con las que pagar a Tomás?

Solución

Si Ali recibe alguna\($10\) factura le puede dar una de esas a Tomas y ya está. Si recibe al menos dos\($5\) facturas, ya está. Si obtiene al menos cinco twonies, ya está, y si consigue al menos\(10\) loonies ya está. Entonces, la mayor cantidad de dinero que puede obtener sin poder darle el suyo a Tomás\($10\) en un solo tipo de moneda, son\(9\) loonies,\(4\) twonies, y una\($5\) factura, por un total de\($22\). Por lo tanto, si Ali pide\($23\), se le garantiza que podrá pagar a Tomas en un solo tipo de moneda.

Si bien el ejemplo anterior no utiliza directamente el “principio de encasillamiento aún más generalizado” porque pide el valor de la moneda que Ali necesita solicitar en lugar del número de artículos que debe solicitar, utiliza las mismas ideas y debería ser útil para entender el concepto.

Ejercicio\(\PageIndex{1}\)

1) Demostrar que en cualquier posicionamiento de\(17\) gradas en un\(8\) tablero de ajedrez\(8\) -by-, debe haber al menos tres gradas ninguna de las cuales se amenace entre sí (es decir, no hay dos de las cuales se encuentran en la misma fila o columna).

2) Dieciséis personas deben sentarse en fila de dieciocho sillas. Demostrar que en algún lugar de la fila debe haber seis sillas adyacentes todas ocupadas.

3) Un artista ha producido una gran obra de arte para ser llevada en un desfile. Parte del concepto es que debe ser llevado por personas de aproximadamente el mismo tamaño (es decir, ya sea todos los adultos, o todos los niños). El artista lo ha dejado hasta el último minuto para encontrar gente para llevar esto, y está en un poco de pánico. No sabe si podrá reunir suficientes ya sea de adultos o niños para llevar la pieza, por lo que decide preguntar a todos los que ve, hasta que tenga suficientes voluntarios. Se necesitan\(15\) adultos para llevar la pieza, o\(23\) niños. Si todos se acercaron están de acuerdo en ayudar, ¿a cuántas personas necesita acercarse el artista antes de que esté seguro de tener suficientes personas para llevar su arte en el desfile?

4) Let\(n\) be odd, let\(a\) be even, y let\(\pi\):\(\{1, . . . , n\} → \{1, . . . , n\}\) be a permutación. Demostrar que el producto

\((a + 1 − \pi (1))(a + 2 − \pi (2))· · ·(a + n − \pi (n))\)

es parejo. ¿La misma conclusión es necesariamente cierta si\(n\) es par o si\(a\) es impar? Dar una prueba o un contraejemplo en cada caso.

5) Dejar\(n ≥ 1\), dejar\(x\) ser un entero positivo, y dejar\(S\) ser un subconjunto de cardinalidad\(n + 1\) de\(\{x, x^2 , . . . , x^{2n}\}\). Demostrar que existen dos números en\(S\) cuyo producto se encuentre\(x^{2n+1}\).

6) Mostrar que en cada conjunto de enteros\(n + 1\) distintos, existen dos elementos\(a\) y\(b\) tal que\(a − b\) es divisible por\(n\).

7) Un cajón contiene calcetines de\(8\) diferentes colores. ¿Cuántos calcetines debes sacar del cajón para estar seguro de que tienes dos del mismo color?

8) Hay\(15\) alumnos en una clase de Combinatoria. Explica cómo sabes que dos de ellos cumplen su cumpleaños en el mismo mes.

9) Un pizzería tiene\(8\) diferentes coberturas. Todos los días de octubre pondrán a la venta una pizza\(2\) -topping. Demostrar que la misma pizza estará a la venta en dos días diferentes.

10) Supongamos que\(A\) es un conjunto de números\(10\) naturales entre\(1\) y\(100\) (inclusive). Mostrar que dos subconjuntos diferentes de\(A\) tienen la misma suma. Por ejemplo, si

\(A = \{2, 6, 13, 30, 45, 59, 65, 82, 88, 97\}\),

luego los subconjuntos\(\{6, 13, 45, 65\}\) y\(\{2, 30, 97\}\) ambos suman\(129\).

[Pista: Compara las respuestas a dos preguntas: ¿Cuántos subconjuntos de\(A\) hay? Ya que solo hay\(10\) elementos de\(A\), y cada uno de ellos es como mucho\(100\), ¿cuántas sumas posibles diferentes hay?]

11) Considere cualquier conjunto de\(5\) puntos en el plano que tengan coordenadas enteras. Demostrar que hay algún par a partir de estos\(5\) puntos tal que el punto medio del segmento de línea que une este par de puntos también tenga coordenadas enteras. Dé un ejemplo de\(4\) puntos en el plano que no tienen esta propiedad, y enumere todos los puntos medios como evidencia