Demuestre que existen al menos dos números$(a,b)$ tales que$a|b$ o$b|a$.

Question

Tenemos este conjunto:$$A=\{1,2,3, \dots , n\}

Elegimos$\left\lceil\frac{n}{2}\right\rceil+1$ números de$A$. ¿Podemos probar que existen al menos dos números que son divisibles? (En otras palabras, ya sea$a\mid b$ o$b\mid a$.)

Ejemplo: Si$A = \{1,2,3,\dots ,20\}$ debemos elegir$11$ números para obtener al menos dos números divisibles.

Answer 1

Sí, es cierto, pero sólo si $n$ es incluso. Hay un montón de contraejemplos que son claramente mencionado en los comentarios y otras respuestas que explica por qué la $n$ no puede ser impar.

SUGERENCIA: Pruebe principio del palomar.

Por factoring como muchos de $2's$ como sea posible, cualquier número de la serie dada se puede escribir como $2^k.a$ donde $a$ es impar número y $k\ge0$.

Por ejemplo, $12=2^2\times 3$ $3$ es impar. $28=2^2\times 7$ $7$ es impar. $33=2^0\times 33$ $33$ es impar, etc.

Ahora $a$ puede ser cualquier extraño decir $1,3,5......$ Desde el conjunto y no se $\frac{n}{2}$ de dichos números ($a$). Así que cuando usted seleccione $\frac{n}{2} + 1$th número debe haber dos números de tener el mismo valor de $a$. Por ejemplo,$l=2^p\times a$$m=2^q\times a$.

Al $p>q$ $m|l$ e al$q>p$$l|m$.

Answer 2

No, deje$n=3$ tal que$A = \{1,2,3\}$. Ahora seleccionamos$\lfloor \frac{3}{2} \rfloor + 1 = 2$ números de$A$, siendo$2$ y$3$. Estos son relativamente primos, por lo tanto, no divisibles.

Answer 3

Para$n=2m+1>1$ elije$x$ para$m+1\leq x\leq 2m-1$ y elige$m$ y elige$2m+1.$ Esto da$m+2$ números, no hay dos que sean divisores el uno del otro . Para incluso$n,$ I dk.