¿501 enteros coprimos distintos entre 1 y 1000?

Question

Este es el ejercicio 1.6.1 de Guichard

Supongamos que 501 distintos números enteros son seleccionados a partir de 1 . . . 1000. Muestran que los hay de distintos seleccionado enteros $a$ $b$ tal que $a | b$. Mostrar que esto no es siempre cierto si 500 enteros son seleccionados.

Este parece que debería ser simple, pero la ha estado visitando a mí por un par de días.

Esta es mi idea para una prueba:

Deje $S$ ser un conjunto de 500 distintos números enteros entre 1 y 1000 que no se separen el uno del otro. Deje $S_{1-500}$ $S_{501-1000}$ partición $S$ en conjuntos que contienen los elementos ≤ y > de 500, respectivamente. A continuación, considere la posibilidad de $2 S_{1-500}$$\frac{1}{2}S_{501-1000}$, el resultado de multiplicar los elementos de estos conjuntos de 2 y 1/2, respectivamente. Debido a que los elementos de S son coprime, $S_{1-500}$, $S_{501-1000}$, $2 S_{1-500}$, y $\frac{1}{2}S_{501-1000}$, son disjuntas. También tenga en cuenta que cada uno de estos conjuntos es un subconjunto de los enteros de 1 a 1000. Uno puede deducir que la cardinalidad de la unión de estos conjuntos es de 1000, y por lo tanto forman una partición de los enteros de 1 a 1000.

Ahora, sé que esto demuestra que no se puede agregar otro número de $S$ que es coprime con todos los elementos en $S$, lo que significa que un coprime subconjunto de los enteros de 1 a 1000 puede tener a más de 500 elementos. Alguien puede expresar por qué esto es cierto para mí? También, esto fue en una sección sobre el principio del Palomar, ¿puede alguien de renovación de la prueba a utilizar, y, posiblemente, hacer que sea más sencillo? Gracias.

Answer 1

$[1,1000]$ se puede repartir a través de los siguientes conjuntos: $$ S_1=\{1,2,4,8,\ldots,512\}, $ $ $$ S_3=\{3,6,12,24,\ldots,768\}, $ $ $$ S_5=\{5,10,20,40,\ldots,640\}, $ $ $$ \ldots $ $ $$ S_{499}=\{499,998\} $ $ más el % de singletons $S_{501},S_{503},\ldots,S_{999}$. Para abreviar, $n\in[1,1000]$ pertenece a $S_{n/2^{\nu_2(n)}}$.

Estos son conjuntos de $500$: si se recogen elementos de $501$ $[1,1000]$, por lo menos dos elementos deben recaer en el mismo $S_m$. Pero cada $S_m$ es una cadena en el POset dado en $a"\leq"b\;\Leftrightarrow a\mid b$, por lo que la reclamación es sencilla.

Answer 2

Sé que ya hay dos respuestas, pero se me ocurrió esta pasada noche y pensé en compartir como yo estaba muy contento con la solución:

Supongamos que la proposición es falsa, es decir, hay conjuntos de tamaño 501, donde para todo a y b en el set, a y b, no la igualdad implica un no divide a b.

Para cada conjunto de satisfacciones esta propiedad (de la que es claro que hay una cantidad finita), podemos encontrar el elemento más pequeño en el conjunto. Elegir un conjunto donde este último elemento es máxima (es decir, no hay conjuntos con esta propiedad, donde el elemento más pequeño si es más grande que el elemento más pequeño en nuestro set elegido). Llamar a este conjunto S, y el elemento más pequeño de x.

Ahora tenemos x = 500, x = 2, o 2 < x < 500 (como si x > 500, no hay suficientes elementos de más de 500 entre x y 1000 para encontrar 501 números). Si x = 500, entonces el conjunto debe ser de 500,...,1000, pero claramente 500 divide 1000, una contradicción. Si x = 2, entonces no podemos tener cualquiera de los números en nuestra serie, por lo que el sólo 500 números restantes son de todos los impares, pero, a continuación, el grupo de contener el 3 y el 9, una contradicción.

Por lo tanto 2 < x < 500. Ahora hace 2*x pertenecen a nuestro grupo? Claramente no, como nuestro conjunto se satisface el supuesto de la propiedad (como x divide a 2*x y suponemos que no hay a, b, distintos tales que divide a b). Pero como x < 500, 2*x < 1000. Además, 2*x no divide a alguno de los elementos de nuestro conjunto como si lo hiciera, x dividiría también ese elemento. Por último, ningún elemento en nuestro conjunto se divide 2*x además de x, como x es el elemento más pequeño en el conjunto y lo que si digo y divide 2*x, es decir, n*y = 2*x, implica que n es menor que 2 y, entonces, no es un entero.

Esto significa que podemos sustituir x por 2*x y nuestras todavía tiene todas las propiedades necesarias. Pero entonces tenemos un conjunto con un mayor elemento más pequeño y elegimos nuestro conjunto de máximas, la cual es una contradicción.

Por lo tanto no se establezca con esto existe la propiedad, y hemos terminado.

Answer 3

Para más claridad en el general caso (es decir, podemos demostrar que existen dos números, uno de los cuales divide el otro en un subconjunto de $(n+1)-$ $[2n]= \{1,2,\ldots 2n\}$) considere lo siguiente:

Sea el subconjunto de $(n+1)-$ $\{a_i\}_{i=1}^{n+1}$ y escriba $a_i = 2^{k}b_i$ $k$ Dónde está el más grande poder de $2$ que divide $a_i$ por lo que es extraño que $b_i$. Entonces $1\leq i \leq n+1, b_i \in [2n-1].$ por el principio del casillero, existe distinto $p ,q \in [2n-1]$ tal que $b_p = b_q.$ entonces está claro que uno de $a_p, a_q$ divide el otro.