Demostrar que en cualquier sistema de $n+1$ positivo números no superior a %#% debe ser #% hay dos que son relativamente privilegiada.
Respuestas
¿Demasiados anuncios?
Bryan Roth
Puntos
3592
En algunos círculos al menos esto es tan famoso como la pregunta de ¿cuál es la suma de los primeros a $n$ enteros positivos. Es a menudo llamado el Posa Problema, porque el problema era que Erdos pedido de la (entonces) de 12 años de Lajos Posa en su primer encuentro con él. De acuerdo a Erdos, Posa resuelto en $30$ segundos, todo el tiempo de comer un plato de sopa. Un relato de esta historia está aquí; no debe ser una fuente más primaria en algún lugar.
P. S.: tengo algunos colegas que trabajan en la rama de las matemáticas -- aditivo combinatoria -- para que este resultado es, básicamente, página 1. Cuando tuve la oportunidad menciona este problema a uno de ellos, ella respondió, "Sí, y también hay un número que divide a otro." Trate de que uno también!
Josh
Puntos
38
Tirar el 1, ya que si está en la lista, a continuación,$gcd(a,1)=1$, y listo. Si no, que necesariamente va a tener que elegir entre dos números en la lista que son una unidad appart, por el principio del palomar. Ahora demuestran que si se tienen dos números consecutivos a,a+1, con a>1, los números deben ser relativamente primos. (Sugerencia: su combinación lineal está todo listo para usted.)
{2k-1,2 k}
EDITAR: Se desprende también que la secuencia que contiene un par de $(a,b)$ tal que $a|b$; elegimos los términos para tratar de evitar un par (a,b), eligiendo $\{ n,n+2,n+4,...,2n-2\}$ WOLG las condiciones (es decir, suponemos que n es impar), y $\{n+1,n+3,...,2n-1\}$ como el impar de términos , para que los más pequeños múltiples (es decir, por 2) de cualquiera de los elementos elegidos es estrictamente mayor que $2n$ (esto muestra que n+1 es el mejor de los posibles enlazado). Pero esto sólo se utiliza hasta el n de los términos de la secuencia. Así que debemos elegir algún término 'b' estrictamente menor que $n= \frac {2n}{2}$. Pero , puesto que el $b<n$, debe ser un múltiplo 'c' de b en el set de $\{n,n+1,....,2n-1\}$. Entonces b|c.
Tratando de hacer el argumento más precisos: básicamente, dado 2n, sostenemos que si n-k es el número más grande en la colección de $\{a_1,..,a_n\}$ de n+1 elementos de $\{1,2.,...,2n\}$, entonces debemos eliminar algunos de los elementos para evitar tener un par de $(b,c)$$b|c$, pero el quid es que debemos quitar "demasiados" elementos para evitar tener un par de $(b,c)$, después de lo cual no podemos tener un total de $n-1$ elementos en nuestra secuencia. Decir, por ejemplo, que el $n-1$ es el elemento más pequeño de nuestro sistema $\{a_1,..,a_{n+1}\}$. Luego tenemos a $(2n-(n-1)+1)=n+2$ números entre el $n-1$ $2n$ a seleccionar nuestra secuencia de n+1 elementos. Pero si hemos de seleccionar el número b=$n-1$ de nuestra serie, no podemos seleccionar a sus múltiples c=$2(n-1)$. Así que tenemos que tirar de $2(n-1)$, y nos quedamos con $n+1$. A continuación, debemos mantener $n=(n-1)+1$ junto con $ \{n,n+1,...,2(n-1)-1,2(n-1)+1,2n\}$ , para un total de $n+1$ términos en nuestra secuencia. Pero eso significa que $n$ $2n$ ambos estarán en la secuencia, y $n|2n$. El argumento generalizado de $n-k$ siendo el mayor elemento seleccionado en $\{a_1,..,a_n\}$
Saeed Neamati
Puntos
157
Esto se desprende el principio del casillero. Considerar el conjunto de primeros números de $2n$. Puede crear $n$ subconjuntos de números primos Co $\{2k-1,2k\}$ $1\leq k \leq n$. Es fácil ver que éstos sean coprimos (su diferencia es 1, por lo que su MCD es 1). Ahora tienes $n$ pares de coprimes, y entre cualquier número de $n+1$ en este rango, al menos dos serán un par de coprimos.
Nota: he seguido la definición para permitir $(1,2)$ a ser un par de coprimos.
Eric Bailey
Puntos
55
El más simple profe que he encontrado La Historia de Louis Pósa (Gracias Pete L. Clark) que es: "Me tiene n+1 número entero positivo menor o igual que 2n, debe haber dos de ellos consecutivos, lo que significa que son relativos prime."
Por cierto, la razón de que "debe haber dos de ellos son consecutivos" es porque el Principio del Palomar
