Ejemplos del principio de encasillamiento

Question

Como la mayoría de ustedes sabrán, el principio de encasillamiento básicamente afirma que

Si $n$ los artículos se colocan en $m$ contenedores, con $n>m$ entonces al menos un contenedor debe contener más de un artículo

Siempre me sorprende cómo esta idea trivial -y al mismo tiempo poderosa- puede ser la clave para resolver problemas de olimpiadas matemáticas extremadamente complicados...

Las soluciones rápidas y bonitas son características de los problemas de encasillamiento, que suelen ser un proceso de tres partes

• Reconocer que el problema requiere el principio de encasillamiento
• Averiguar cuáles son las palomas y los casilleros
• Después de aplicar el principio de encasillamiento, suele haber más trabajo por hacer

Lo ilustraré con un ejemplo que siempre me ha gustado...

(Ejemplo-)Problema : Dado un $n\times n$ cuadrado, demuestre que si $5$ puntos se colocan al azar dentro del cuadrado, entonces dos de ellos son como máximo $\frac{n}{\sqrt2}$ unidades separadas.

Paso 1: Este problema puede ser resuelto con el Principio de la Colocación

Paso 2: Dividimos el $n\times n$ cuadrado en cuatro $\frac{n}{2}\times\frac{n}{2}$ cuadrados (casillas). Por lo tanto, al menos dos puntos (palomas) están dentro del mismo $\frac{n}{2}\times\frac{n}{2}$ cuadrado.

Paso 3: La distancia máxima entre dos puntos en un $\frac{n}{2}\times\frac{n}{2}$ cuadrado es la diagonal, que tiene la longitud $\frac{n}{\sqrt2}\qquad\square$

Otro problema que se puede resolver con el principio de la paloma es el siguiente:

OMI $1972/1$

Demuestra que de un conjunto de diez números distintos de dos cifras (en el sistema decimal), es posible seleccionar dos subconjuntos disjuntos cuyos miembros tienen la misma suma.

Llegados a este punto, ya te habrás dado cuenta de lo útil que puede ser el principio de encasillamiento, si sabes reconocerlo y utilizarlo.

Pregunta : Me gustaría trabajar en este increíble principio con mis alumnos durante una semana y, por lo tanto, estaba reuniendo problemas relacionados con el Principio de la Colocación con hermosas soluciones.
¿Podría sugerir algunas más?

Answer 1

Esta es una lista de problemas que conozco (no conozco referencias en absoluto)

• Elija 51 números de $\{1, 2, 3, \dots, 100\}$ , entonces al menos dos de ellos son coprimos.

• Elija 51 números de $\{1, 2, 3, \dots, 100\}$ entonces uno de ellos divide al otro.

• Para cualquier irracional $x$ existe un número infinito de enteros $p, q$ tal que $|x-p/q| < 1/q^{2}$ . (Teorema de aproximación de Dirichlet)

Puede encontrar otros ejemplos aquí.

Answer 2

He aquí algunos de mis favoritos:

1. El Teorema de Erdos-Szekeres es, por supuesto, un ejemplo clásico

2. Llame a $S = \{a_1,...,a_{|S|}\} \subset \{1,2,...,n\}$ un conjunto de Sidón si todas las sumas por pares $a_i+ a_j, i \leq j$ son distintos. Entonces $|S| = O(n^{1/2})$

La prueba es muy sencilla. $S$ es, de manera equivalente, un conjunto de Sidón si el ${|S| \choose 2}$ las diferencias entre pares son distintas. Éstas sólo pueden tomar valores de $1$ a $n-1$ . Así que por el principio de encasillamiento, ${|S| \choose 2} \leq n-1 \implies |S| = O(n^{1/2})$ . (La misma prueba puede repetirse para las sumas por pares, pero las diferencias dan una constante mejor).

Lo bonito de esta prueba es que el límite superior está muy cerca de ser ajustado - existen conjuntos de Sidon con un tamaño cercano a $n^{1/2}$ .

3. Cualquier primo $p$ no es igual a $2$ o $5$ divide infinitamente muchos de los enteros, $11, 111, 1111, ...$

Por el principio de encasillamiento, infinitamente muchos de ellos están en la misma clase de residuo mod $p$ y sus diferencias por pares son de la forma $11...10..0$ Desde $p$ es coprima de $10$ , $p$ debe dividir la cadena inicial de $1$ 's.

Answer 3

Aquí hay algunos problemas relativamente desafiantes, en los que la "parte del encasillamiento" no siempre es inmediatamente obvia.

Demuestre que para cualquier $x\in\mathbb{Z}^+ $ existe un número de Fibonacci que es divisible por $x$ . (Puede ser útil considerar primero algunos casos, como $10^{10}$ y luego generalizar la prueba. Esto es también una generalización del tercer problema de Sim000).

Hay $n$ enteros positivos distintos $a_1,a_2,\dots, a_n$ Para cualquier secuencia $b_1,b_2,\dots, b_n$ , donde $b_i\in \{-1,0,1\}$ para $1\leq i\leq n$ y los términos no son todos cero, $n^3\nmid a_1b_1+a_2b_2+\dots + a_nb_n$ . Encuentre el máximo valor posible de $n$ .

Un estudiante, que ha $11$ semanas para preparar una olimpiada, decide hacer un examen de práctica cada día. Sin embargo, debido a las limitaciones de tiempo, el estudiante no puede hacer más de $12$ exámenes de práctica en cualquier $7$ -período de días. Demostrar que hay días consecutivos en los que el alumno realiza exactamente 21 exámenes de prácticas.

Las factorizaciones primarias de $n+1$ números enteros positivos $x_1,x_2,\dots, x_{n+1}$ sólo implican $n$ primos $p_1,\dots, p_n$ . Demuestre que existe un subconjunto no vacío de $\{x_1,\dots, x_{n+1}\}$ cuyos elementos se multiplican a un cuadrado perfecto.

Supongamos que los números reales $x_1,\dots, x_n$ satisfacer $\sum x_i^2=1$ . Demostrar para los enteros $k\geq 2$ existe un número entero $y_1,\dots, y_n$ no todos cero tal que $|y_i|\leq k-1$ para $1\leq i\leq n$ y $$\Biggl |\sum x_iy_i\Biggl| \leq \frac{\sqrt{n}(k-1)}{k^n-1}$$

Answer 4

¿Qué tal el problema de la división?

dejar $A \subseteq$ $\{1,2,...,2n\}, |A|=n+1$

muestran que debe haber dos elementos $x, y$ $\in A$ s.t $ x\neq y $ y $x$ divide $y$ .

Prueba:

Cualquier número natural puede ser denotado como: $N=2^k * m$ , donde $m$ es algún número impar.

Dado que sólo hay $n$ Los números de impar como máximo en $A$ debe haber al menos dos números $a, b$ para el que el mayor divisor impar $m$ es el mismo a través de PHP, por lo que uno de ellos debe dividir al otro.

Espero que te sirva de ayuda.

Answer 5

Hay grandes aplicaciones del principio de encasillamiento (PHP) en algunos problemas de olimpiadas y algunos teoremas, tanto en estructuras finitas como infinitas. Aquí mencionaré tres de ellos y algunas pistas sobre las soluciones. Espero que te resulten útiles:

1-Dados cinco puntos de celosía en el plano, conectamos dos cualesquiera de ellos trazando una línea entre ellos. así que trazamos 10 líneas, entre estos puntos. Demostrar que existe otro punto de celosía en al menos una de estas líneas.(Por "punto de celosía" me refiero a puntos del plano con coordenadas enteras)

(Sugerencia: las coordenadas enteras pueden ser Impares o pares, y te dan 5 puntos! ahora mira el medio de las líneas).

2- para cualquier entero positivo n, demostrar que existe un múltiplo de n cuya presentación en base 10 sólo tiene 0 y 1.

(Pista : considere una secuencia 1,11,111,1111,.... . mira esta secuencia modulo n y por PHP encuentra la solución en forma de x-y donde x e y están en esta secuencia).

3- para cualquier número entero positivo n, demostrar que existe un número de Fibonacci divisible por $10^n$ .

(Sugerencia: vuelve a mirar la secuencia de números de fibonacci módulo $10^n$ y tratar de demostrar que esta secuencia es una secuencia periódica).