Demuestra que dos números de un conjunto dividen por igual al otro

Question

Tenemos un conjunto A de números 1, 2, 3... hasta 200

La pregunta me pide que demuestre que si elijo 101 números del conjunto, habrá dos tales que uno divida al otro por igual.

Sé que ésta podría ser la pregunta del principio de encasillamiento. Podría demostrar por contradicción que no hay dos números que se dividan por igual. Supongamos que tomo 101 números, no puedo tomar todos los números Impares porque sólo hay 100 de ellos, por lo que habrá un número par. Creo que esto no va a ninguna parte.

Utilizando una prueba directa si elijo 101 números, obtendré o bien 100 pares + 1 impar o bien 100 impar + 1 par. Para que dos números se dividan equitativamente yo elegiría los 100 pares, y hay una gran probabilidad de que dos sean pares, pero si tengo 100 impar + 1 par, sólo habrá 1 par... Así que no estoy seguro de cómo resolver esto...

Answer 1

Una pista: Las cajas tendrán etiquetas $1$ , $3$ , $5$ y así sucesivamente hasta $199$ . ¡Etiquetas Impares! Tenga en cuenta que hay $100$ cajas.

Caja 1: Contiene $1,2,4,8,16, 32,\dots$

Caja 3: Contiene $3,6,12,24, 48, \dots$

Caja 5: Contiene $5,10,20, 40,\dots$ .

Y así sucesivamente.

Caja 99: Contiene $99,198$

Las casillas 101, 103 y demás son bastante aburridas. La casilla 101 sólo contiene el número $101$ La caja 103 sólo contiene $103$ y así sucesivamente.

Answer 2

Escoge $101$ elementos de $A$ , etiquételos $a_1,\ldots, a_{101}$ . Podemos suponer que $a_1 < \ldots < a_{100} < a_{101}$ . Ya que tenemos $101$ elementos distintos, $a_1 \leq 99$ .

Consideremos el conjunto de restos de la división por $a_1$ . Desde $a_1 \leq 99$ hay a lo sumo $98$ estos restos. Sea $r_2$ sea el resto al dividir $a_2$ por $a_1$ , $r_3$ el resto al dividir $a_3$ por $a_1, \ldots, r_{101}$ el resto al dividir $a_{101}$ por $a_1$ .

Tenemos $101$ restos $r_1,\ldots ,r_{101}$ (palomas), y como máximo $98$ posibles restos (casillas) al dividir por $a_1$ . Así, por el principio de encasillamiento, $r_i = r_j$ para algunos $1\leq i < j \leq 101$ . Ahora bien, ¿qué se puede decir del número $a_j - a_i$ ?