Usar casillero principio para probar que dos números en un subconjunto de $[2n]$ dividen entre sí

Question

Que $n$ ser mayor o igual a $1$ y que $S$ ser un $(n+1)$-subconjunto de $[2n]$. Demostrar que existen dos números en $S$ tal que uno divide el otro.

Cualquier ayuda se agradece!

Answer 1

Sugerencia: Crear un casillero para cada número entero positivo impar $2k+1<2n$ y poner en ella todos los números en $[2n]$ de la forma $(2k+1)2^r$ $r\ge 0$.

Answer 2

Pensé que valdría la pena escribir de Brian prueba con más detalle.

Deje $A=\{1,2,\dots,2n\}$. Escribir $A=E\cup O$ donde $E$ son de la iguala y $O$ son las probabilidades. A continuación,$|O|$, el tamaño de $O$$n$. Ahora vamos a $x\in A$. A continuación, por la única factorización de números enteros, podemos escribir la $x=2^ab$ donde $b$ es impar. La asociación de $f:x\mapsto b$ por lo tanto da una bien definida la asignación de $A\rightarrow O$. Desde $|O|=n$, $|f(C)|\leq n$ para cualquier subconjunto $C\subseteq A$. Por lo tanto, si $C\subseteq A$ $n+1$ elementos, debe haber dos elementos $c_1,c_2\in C$ tal que $f(c_1)=f(c_2)$. En otras palabras $c_1=2^{a_1}b$$c_2=2^{a_2}b$. Así que si $a_1<a_2$ $c_1$ divide $c_2$. De lo contrario, $a_1>a_2$ $c_2$ divide $c_1$. Q. E. D.

Answer 3

Me doy cuenta de que esta pregunta es viejo, pero lo resuelto recientemente, cuando alguien me preguntó cómo demostrarlo.

La prueba que se me ocurrió no utiliza el principio del palomar, en lugar de ello utiliza la Inducción Matemática:

Supongamos que la afirmación es verdadera para $[{1,2,....,2k}]$

Consideremos el conjunto $P$= $[{1,2,.....,2k,2k+1,2k+2} ]$

Su fácil si se la partición, por lo tanto tenemos:

$P_1$ = $[{1,2,....,2k}]$ ,$P_2$ =$ [{2k+1,2k+2}]$

Tenemos que seleccionar al menos $k$ elementos de $P_1$ como si seleccionamos cualquiera menos de $k$ elementos de $P_1$, dicen que seleccione $k-1$, entonces los otros tres elementos debe venir de $P_2$, pero esto es imposible, como $P_2$ sólo tiene dos elementos , por lo que asumimos el peor de los casos, y seleccionar exactamente $k$ elementos de $P_1$. Si tuviéramos que seleccionar más, por nuestra inductivo, la hipótesis de la prueba sería completa.

Bueno, digamos que nuestra selección es $S_k$ .

Ahora, ya que es el peor de los casos, seleccionamos a nuestros dos restantes elementos$2k+1$$2k+2$, como si seleccionamos las dos restantes elementos de $P_1$ nosotros ya estaría hecho, por nuestra hipótesis inductiva.

Considere la posibilidad de $2k+2 = 2(k+1)$ . Claramente $k+1 | 2k+2 $

Si elegimos $k+1$ como parte de $S_k$, hemos terminado.

Si no elegimos $k+1$ como parte de $S_k$$P_1 - S_K$ .

Ahora considere el $S_k \cup \ k+1 $

Algo en $S_k$ DEBE dividir $k+1$ o $k+1$ DEBE dividir algo en $S_k$. Esto es debido a que $S_k \cup \ k+1$ contiene $k+1$ artículos, así que por nuestra hipótesis inductiva este debe ser el caso. Pero si $k+1$ divide algo en $S_k$, tenemos una contradicción, ya que al menos varias de $k+1$$2k+2$, que no es ciertamente en $S_k$.

Por lo tanto, algo en $S_k$ DEBE dividir $k+1$ .

Si algo en $S_K$ divide $k+1$, entonces algo en $S_k$ divide $2k+2$, y la prueba está completa.