9.2: El principio del encasillamiento

Si un cartero tiene m letras para distribuir entre n buzones (o “encasillados”)\(m > n\), y, entonces es claro que al menos uno de los buzones tendrá que obtener más de una letra. Esta importante observación se conoce como el “Principio de encasillamiento”. (Ver Ejercicio\(9.3.6\) para la prueba.) En el lenguaje de los conjuntos, se puede afirmar de la siguiente manera.

Proposición\(9.2.1\) (Pigeonhole Principle).

Dejar\(B\) y\(A_{1}, A_{2}, \ldots, A_{n}\) ser conjuntos finitos. Si\[B \subset A_{1} \cup A_{2} \cup \ldots \cup A_{n} ,\]

y\(\# B > n\), entonces\(\# A_{i} \geq 2\), para algunos\(i\).

Estas son algunas de las muchas aplicaciones del Principio Pigeonhole. En estos ejemplos del mundo real, nuestras explicaciones serán un poco informales.

Ejemplo\(9.2.2\).

El cajón de calcetines de Bob tiene muchos, muchos calcetines en él, y vienen en 4 colores. Desafortunadamente, la luz de su habitación se ha quemado, por lo que no puede ver nada. ¿Cuántos calcetines debe agarrar del cajón, para que pueda estar seguro de que al menos dos de ellos son del mismo color?

Solución

Bob debe agarrar 5 (o más) calcetines.

Para ver esto, tenga en cuenta, primero, que tomar 4 calcetines puede no ser suficiente: Si Bob agarra solo 4 calcetines, es posible que tenga un calcetín de cada uno de los 4 colores diferentes. Entonces no tendría dos calcetines del mismo color.

Ahora supongamos que Bob agarra (al menos) 5 calcetines. Puede ordenarlos en 4 pilas, por color. Desde 5 > 4, una de las pilas debe tener más de un calcetín. Entonces hay (al menos) 2 calcetines del mismo color.

Ejemplo\(9.2.3\).

Si eliges 50 números del 1 al 98, entonces se garantiza que dos de ellos sumarán exactamente 99.

Solución

Los números del 1 al 98 se pueden dividir en 49 casilleros:\[\{1,98\},\{2,97\},\{3,96\}, \ldots,\{49,50\} .\]

(Entonces dos números diferentes\(x\) y\(y\) están en el mismo pigeonhole iff\(x+y = 99\).) Desde 50 > 49, dos de los números que elegimos deben estar en el mismo casillero. Entonces la suma de estos dos números es exactamente 99.

Ejemplo\(9.2.4\).

Si eliges 5 puntos en la superficie de una naranja (esférica), entonces siempre hay una manera de cortar la naranja exactamente por la mitad, de tal manera que al menos 4 de tus puntos estén en la misma mitad. (Asumimos que cualquier punto que esté exactamente en el corte se considera que pertenece a ambas mitades).

Solución

Dos de los puntos cualesquiera quedarán sobre un gran círculo de la esfera, así podremos cortar la naranja para que 2 de los puntos queden exactamente en el corte. Los otros 3 puntos se distribuyen de alguna manera entre las dos mitades de la naranja. Por el Principio Pigeonhole, al menos dos de esos tres puntos están en la misma mitad. Entonces esa mitad contiene los 2 puntos del corte, más estos 2 puntos adicionales, para un total de (al menos) 4 de los puntos que escogiste.

Ejercicio\(9.2.5\).

1. Hay diez personas en una pista de patinaje, jugando hockey. Explica cómo sabes que dos de ellos nacieron el mismo día de la semana.
2. Si hay 400 alumnos en una escuela primaria, explica cómo sabes que (al menos) dos de ellos tienen el mismo cumpleaños.
3. Si hay 700 empleados en una empresa, explique cómo sabe que hay dos de ellos con las mismas iniciales. (Es decir, sus nombres comienzan con la misma letra, y sus apellidos comienzan con la misma letra).
4. Se sabe que:
   • Nadie tiene más de 300, 000 pelos en la cabeza.
   • Más de un millón de personas viven en Calgary.
     Demuestre que hay dos personas en Calgary que tienen exactamente el mismo número de pelos en la cabeza.

Además de los ejemplos anteriores del mundo real, el Principio Pigeonhole tiene importantes aplicaciones en matemáticas teóricas.

Corolario\(9.2.6\).

Supongamos\(A\) y\(B\) son conjuntos finitos.

1. Si existe una función uno a uno\(f: A \rightarrow B\), entonces\(\# A \leq \# B\).
2. Si existe una función onto\(f: A \rightarrow B\), entonces\(\# A \geq \# B\).

Prueba

Dejar\(m = \# A\) y\(n = \# B\).

1. Supongamos que\(f: A \rightarrow B\) es uno a uno, y\(m > n\). Asumir sin pérdida de generalidad eso\(B=\{1,2, \ldots, n\}\), así podremos dejar\[A_{i}=f^{-1}(i) \quad \text { for } i=1,2, \ldots, n .\]
   Para cualquiera\(a \in A\), tenemos\(a \in f^{-1}(f(a))=A_{f(a)}\), así\(a \in A_{1} \cup A_{2} \cup \cdots \cup A_{n}\). Ya que\(a\) es un elemento arbitrario de\(A\), esto implica\(A \subset A_{1} \cup A_{2} \cup \ldots \cup A_{n}\). Porque\(\# A = m > n\), concluimos que\(\# A_{i} \geq 2\) para algunos\(i\). Esto significa\(\# f^{-1}(i)>1\), lo que contradice el hecho de que\(f\) es uno a uno.
2. Supongamos que\(f: A \rightarrow B\) está encendido, y\(m < n\). No hay daño en asumir\(A=\{1,2, \ldots, m\}\), y entonces podemos dejar que\[B_{i}=\{f(i)\}\]
   \(i=1,2, \ldots, m\). Ya que\(f\) está en, sabemos, para cualquiera\(b \in B\), hay algunos\(i \in A\), tal que\(f(i) = b\). Esto significa\(b \in B_{i}\); de ahí,\(b \in B_{1} \cup B_{2} \cup \cdots \cup B_{m}\). Ya que\(b\) es un elemento arbitrario de\(B\), esto implica\(B \subset B_{1} \cup B_{2} \cup \ldots \cup B_{m}\). Porque\(\# B = n > m\), concluimos que\(\# B_{i} \geq 2\) para algunos\(i\). Esto contradice el hecho de que\(\# B_{i} = 1\) (porque\(B_{i}=\{f(i)\}\) tiene un solo elemento).

Observación\(9.2.7\).

En lugar de Proposición\(9.2.1\), muchos matemáticos consideran que lo contrapositivo del Corolario\(9.2.6(1)\) es el Principio de Casillero:

Si\(\# A > \# B\), entonces no existe una función uno a uno de\(A\) a\(B\).

Ejercicio\(9.2.8\).

1. Supongamos que\(A\) es un conjunto de 10 números 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\} ,\]
   entonces los subconjuntos\(\{6, 13, 45, 65\}\) y\(\{2, 30, 97\}\) ambos suman 129. [Sugerencia: Compara las respuestas a dos preguntas: ¿Cuántos subconjuntos de\(A\) hay? Ya que solo hay 10 elementos de\(A\), y todos ellos lo son\(\leq 100\), ¿cuántas sumas posibles diferentes hay?]
2. Demuestra que si pones 5 puntos en un triángulo equilátero de longitud lateral 2 cm, entonces hay dos de los puntos que no están separados más de 1 cm. [Sugerencia: Divide el triángulo en 4 triángulos equiláteros de longitud lateral 1 cm.]
3. A los números 1, 11, 111, 1111, etc. se les llama repuntas. (Su representación decimal consiste enteramente en 1's.) Demostrar que alguna repunit es divisible para 2017. [Pista: Si\(n \times 10^{k}\) es divisible para 2017, para algunos\(k \in N\), entonces\(n\) es divisible para 2017. ¿Por qué? ]
4. Demostrar que\(\# A\) está bien definido. Es decir, si\(\# A = m\) y\(\# A = n\), para algunos\(m, n \in N\), entonces\(m = n\). [Pista: Aplicar Corolario\(9.2.6\) con\(B = A\).]
5. \(\mathbb{N}\)El espectáculo es infinito. [Pista: Prueba por contradicción. Aplicar Corolario\(9.2.6(1)\).]

Observación\(9.2.9\).

Aquí hay dos generalizaciones del Principio Pigeonhole que a menudo son útiles.

1. Si un cartero tiene\(m\) cartas para distribuir entre\(n\) buzones, y\(m > kn\), entonces al menos uno de los buzones tiene que obtener más que\(k\) cartas.
2. Supongamos que un cartero tiene\(m\) cartas para distribuir entre los\(n\) buzones. Si\[k_{1}, k_{2}, \ldots, k_{n} \in \mathbb{N} \text { and } m>k_{1}+k_{2}+\cdots+k_{n} ,\]
   entonces debe haber algunos\(i\), de tal manera que el buzón\(i\) th obtenga más que\(k_{i}\) letras.

Ejercicio\(9.2.10\).

Estado (1) y (2) de Observación\(9.2.9\) análogamente a:

1. Proposición\(9.2.1\) (es decir, en términos de un conjunto\(B\) contenido en\(A_{1} \cup A_{2} \cup \cdots \cup A_{n}\)), y
2. Corolario\(9.2.6(1)\) (es decir, en términos de una función\(f : A \rightarrow B\)).

Ejercicio\(9.2.11\).

1. Fortalecer la conclusión de Ejercicio\(9.2.5(4)\): muestra que hay una colección de 4 personas en Calgary que todas tienen exactamente la misma cantidad de pelos en la cabeza.
2. Al igual que en Ejemplo\(9.2.2\), el cajón de calcetines de Bob tiene muchos, muchos calcetines en él, y vienen en 4 colores. ¿Cuántos calcetines debe agarrar del cajón, para que pueda estar seguro de que al menos 12 de ellos son del mismo color?
3. El cajón de calcetines de Betty tiene 6 calcetines azules, 10 calcetines rojos, 14 calcetines blancos y 18 calcetines negros. ¿Cuántos calcetines debe agarrar del cajón, para que pueda estar segura de que al menos 12 de ellos son del mismo color?