¿Cuál es su aplicación preferida del Principio de Encasillamiento?

Question

El principio de encasillamiento establece que si $n$ los artículos se colocan en $m$ "casillas" con $n > m$ entonces al menos un casillero debe contener más de un artículo.

Me gustaría ver tu aplicación favorita del principio de encasillamiento, para demostrar algún teorema sorprendente, o algún resultado interesante/divertido que uno pueda mostrar a los estudiantes en una clase de pregrado. Las aplicaciones a nivel de posgrado también estarían bien, pero me interesan sobre todo los ejemplos que pueda utilizar en mis clases de grado.

Hay algunos ejemplos en la página de Wikipedia del principio de encasillamiento . El ejemplo de contar el pelo es uno que me gusta... ¡vamos a ver otros buenos!

Gracias.

Answer 1

Como describe el artículo de la wikipedia, Teorema de aproximación de Dirichlet es un resultado fundacional en la aproximación diofantina. Para un número real $x$ , dejemos que $\|x\|$ denotan la distancia desde $x$ a su número entero más cercano. Entonces el teorema afirma que para cualquier irracional número $\alpha$ existe un número infinito de $q \gt 0$ tal que $$ \| q\alpha \| \leqslant \frac{1}{q}. $$ Este teorema es una simple consecuencia del principio de encasillamiento, y me sorprendió mucho al ver la demostración. Puedes encontrar la prueba en la respuesta de robjohn a la pregunta: Aproximación de irracionales por fracciones .

En palabras, este teorema dice que podemos aproximar los irracionales tanto como queramos (en el sentido de $\| q \alpha \|$ ) si se nos permite elegir un tamaño lo suficientemente grande $q$ . Esto puede no parecer tan sorprendente al principio, pero se vuelve llamativo cuando se compara con el caso racional.

Supongamos que $\alpha = a/b$ donde $a$ y $b$ son números enteros y $b \geqslant 1$ . Queremos saber qué tan bien $\alpha$ se puede aproximar utilizando otros racionales, ya que de lo contrario el problema es trivial. Por lo tanto, arreglar $p/q \neq \alpha = a/b$ . Reacomodando, $qa - pb$ es distinto de cero, ya que también es un número entero, $|qa - pb|$ debe ser como mínimo $1$ . Así, $$ |q\alpha - p| = \frac{|qa - pb|}{b} \geqslant \frac{1}{b}. $$ En particular, si $q \alpha$ no es un número entero, entonces $\| q \alpha \| \geqslant \frac{1}{b}$ que está acotado lejos de cero, independientemente de $q$ .

Así, en un sentido preciso, los números irracionales pueden aproximarse mejor utilizando los racionales que los propios números racionales. (Por supuesto, como se ha dicho anteriormente, en el caso racional, no contamos "aproximar" el número por sí mismo).

Answer 2

Dados cinco puntos de una esfera, existe una semiesfera cerrada que contiene al menos cuatro de ellos.

Answer 3

Un resultado bastante interesante es que es imposible crear un algoritmo de compresión de datos sin pérdidas que acorte cada archivo de entrada. Si es sin pérdidas, debe alargar algunos archivos. La prueba de esto se describe muy bien en wikipedia .

Answer 4

Esta es una bonita aplicación del encasillamiento.

Encontrar el tamaño del mayor subconjunto $A$ de $\{ 1,2 ,\ldots, 2n \}$ cumpliendo la siguiente condición: si $a$ y $b$ son elementos distintos de $A$ entonces $a$ no divide $b$ .

Después de pensar un poco, se puede llegar al ejemplo $A = \{ n+1, n+2, \ldots, 2n \}$ que contiene $n$ elementos. Pero, ¿es esto lo mejor posible? Sorprendentemente, sí.

Hacia una contradicción, suponga $|A| \geqslant n+1$ . Escriba cada $a \in A$ como producto de un número impar ("la parte impar de $a$ ") y un poder de $2$ . Contenga los elementos $a \in A$ ("las palomas") en agujeros, de manera que dos palomas entran en el mismo agujero si sus partes Impares son iguales. Ahora el número de agujeros es $n$ (¿por qué?), y el número de palomas es $\geqslant n+1$ por suposición. Por lo tanto, está garantizado que encontraremos un par $a,b \in A$ cuyas partes de impar son idénticas.

¿Ves por qué hemos terminado?

Editar: Ok, este es oficialmente de EL LIBRO ¡! Gracias a t.b. por señalarlo.

Answer 5

Todo gráfico con dos o más vértices tiene dos vértices con el mismo grado.