Demostrar el uso de la inducción que a partir de un conjunto de $n+1$ números de $1..2n$, al menos un número se dividen equitativamente otro.

Question

Dado un conjunto de $n+1$ números de la primera $2n$ números naturales, $1,2,\ldots,2n$, demostrar que hay dos números en el conjunto, uno de los que se divide la otra.

Yo no puedo decir si estoy de reducir el problema de la manera correcta. Sería algo así como:

Inducción de la Hipótesis: Un conjunto de $n+1$ números de la primera $2n$ números naturales contiene dos números, uno de los cuales uniformemente divide los otros.

Caso Base: $n=1$, $\{1,2\}$, 2 es divisible por 1.

Considerar un conjunto de $n+2$ números, $A$, desde el primer $2n+2$ números naturales. Hay tres casos:

1. Cada número en $A$ es menor o igual a $2n$. La prueba se sigue de la hipótesis de inducción.

2. Un número en $A$ es mayor que $2n$. El conjunto restante de $n+1$ números deben ser menor o igual a $2n$. La prueba se sigue de la hipótesis de inducción.

3. $A$ contiene $2n+1$$2n+2$. No estoy seguro de cómo resolver este caso.

Estoy trabajando a través de la Udi Manber la Introducción A los Algoritmos: Un Enfoque Creativo para el desarrollo personal, por lo que en consonancia con el espíritu del libro, estoy tratando de utilizar la inducción.

Sin la inducción, la pregunta es idéntica a Probar dos números de un conjunto se dividen equitativamente el otro

Answer 1

$3$.

(1) Si $n+1$$A$,$n+1|2n+2$.

(2) Si $n+1$ no $A$, entonces si reemplazamos $2n+2$$n+1$, dicen que el nuevo conjunto es $B$, podemos utilizar la hipótesis de inducción como en el caso de $2$ a la conclusión de que existen $a|b$$B$. Si tanto $a,b\neq n+1$, $a,b$ $A$ y hemos terminado. Si bien $a,b=n+1$, entonces el otro se encuentra en $A$ y que el número se divide $2n+2$. QED.