Inducción para probar que un conjunto de números enteros de $n+1$ entre $1$y $2n$ tiene al menos un número que divide a otro número en el conjunto de

Question

Estados de cuestión: "Mostrar que si $n+1$ enteros entre $1$ $2n$ (inclusive) son los elegidos, el conjunto de los enteros contienen al menos un número que divide a otro miembro de la misma".

He encontrado un no-inductivo de la prueba en línea, que utiliza el principio del palomar y expresar cada número de el set elegido como $2^{aj}$ donde $j$ es un número impar de $\{1,3,5,...,2n-1\}$. (así que hay $n$ cajas de $j$) prácticamente se dividen repetidamente un número por 2 hasta que el número es impar. Por ejemplo, podemos expresar $56$$2^3 \times 7$. tenemos $n+1$ números que pueden encajar en $n$ cajas, y por el encasillar a Principio llegamos a la conclusión de que hay dos números en un determinado $j$ cuadros; uno de ellos se divide de la otra.

Sin embargo, mi libro dice que no se puede demostrar la pregunta por el uso de la inducción. Obviamente, el caso base se mantiene. Aquí está mi progreso hasta ahora:

Asumir cierto para un número entero $n$. Tenemos que demostrar que un conjunto arbitrario de $n+2$ enteros de $\{1,...,2n,2n+1,2n+2\}$ tiene un número que divide a otro número desde el set elegido. Si uno o ninguno de los dos nuevos números ( $2n+1$ $2n+2$ ) es elegido, hemos terminado, ya que debe recoger, al menos, $n+1$ elementos del resto del conjunto,$\{1,...,2n\}$ .

Surge un problema si AMBOS de los dos nuevos números son elegidos. Entonces estamos obligados a demostrar que un conjunto arbitrario de $n$ a los números del conjunto $\{1,...,2n\}$ contiene dos números, uno de los cuales se dividen de la otra, o que el mismo conjunto arbitrario de números debe contener un número que divide a cualquiera de las $2n+1$ o $2n+2$. Si el conjunto arbitrario de $n$ números de contener $1$, $2$, o $n+1$, entonces hemos terminado. Así que debemos probar que un conjunto arbitrario de $n$ a los números del conjunto $\{3,4,...,n-1,n,n+2,...,2n\}$ contiene dos números, uno de los cuales se dividen de la otra, o que el mismo conjunto arbitrario de números debe contener un número que divide a cualquiera de las $2n+1$ o $2n+2$.

¿Cómo puedo mostrar esto?

Answer 1

Si por el $n+2$ seleccionar sólo uno de ellos es $2n +1$ o $2n+2$ luego el resto de la $n+1$ que escogió son de $1... 2n$ y debe tener un número divide a otro.

Si ambos de $2n+1$ $2n+2$ son elegidos luego de asumir, en aras de una prueba por contradicción, que ninguna de las $n+2$ términos de cualquier término dividiendo otro... entonces usted no coger $n+1$ y ninguno de los términos se dividen $n+1$ (el que divide $2n + 2$). Descartar $2n+1$ $2n+2$ y pick $n+1$ lugar. Ahora tiene $n+1$ términos de $1... 2n$. Ninguno de los términos que no se $n+1$ brecha $n+1$ o el uno al otro. $n+1$ no dividir cualquier número menor o igual a $2n$. Por lo que ninguno de los términos dividir cualquier otro. Que es una contradicción.

==== respuesta anterior donde me hizo la suposición de que la tenía que ser consecutivos ===

Supongamos que usted seleccionó $\{m,m+1,.....m+n+1\}\subset \{1....2n\} $

A continuación, $\{m,.....,m+n\}\subset\{1....2n\} $ tiene un número que divide a otro.

Si $\{m,m+1,...m+n+1\}\not \subset \{1....2n\} $$2n+1 \in \{m,m+1,...m+n+1\}$.

Cualquiera de las $m+n+1=2n+1$ $m=n$ y el conjunto ha $n $$2n $,

o $m+n+1=2n+2$, en cuyo caso $m=n+1$ y el conjunto ha $n+1$$2n+2$.