Encuadernado en tamaño de subconjunto de $\{1,2,\ldots,2n\}$ donde ningún miembro es múltiplo de otro

Question

Use inducción matemática, dada un conjunto de n +1 enteros positivos, ninguno superior a 2n, hay al menos un entero en este sistema que divide a otro entero en el conjunto.

No entiendo por qué cuando n = 1 que esta ecuación es correcta. Creo que puedo poner como número entero 3 y 5 que no conoce la respuesta.

Ahora mi primer paso está claro, que no entiendo muy bien cómo debo pensar para el siguiente paso.

Answer 1

Deje $P(n)$ ser la proposición de que, dado cualquier conjunto de números enteros $\{a_j\}$ contiene $n+1$ diferentes $a_j$ todos los cuales están a menos de o igual a $2n$, entonces existe algún $j_1 \neq j_2$ tal que $a_{j_1}$ divide $a_{j_2}$.

$P(1)$ es trivial demostrar que: Para cualquier conjunto de dos enteros todos de los cuales son menores o iguales a 2, que contiene dos idénticos números enteros (que divide cada uno de los otros) o que contiene a $1$, el cual se divide $2$.

Ahora dicen que el $P(n)$ mantiene y que $P(n+1)$ es falso. Entonces a partir de la $P(n+1)$ no hay algunos de $S \equiv \{s_j\}$ contiene $n+1+1$ enteros y todos los $s_j \leq 2n+2$, y no $s_j$ divide cualquier $s_k$$k \neq j$.

A menos $2n+1 \in S$$2n+2 \in S$, la $T = S-s_j: s_j > 2n$ contiene al menos $n+1$ enteros, sin que exceda $2n$, y por $P(n)$ se sabe que uno de estos elementos divide a otro. Ya sabemos que no hay dos elemento de $S$ divide a otro elemento de $S$ eso no puede ser. Así que si $S$ existe,

$$ 2n+1 \S \text{ y } 2n+2 \in S $$

Entonces sabemos que el $(n+1) \not \in S$ desde que divide $(2n+2)$.

Ahora consideremos el conjunto $U = S - \{(2n+1), (2n+2)\} + \{(n+1)\}$. $U$ ha $n+1$ elementos, todos los cuales están a menos de o igual a $2n$. Así por $P(n)$ uno de los elementos divide a otro. Pero si los dos elementos en cuestión no incluye el elemento $(n+1)$ entonces también se divide cada uno de los otros cuando se la considera como elementos de $S$, lo que por supuesto no es el caso.

Así que algún elemento de $u\in U$ divide $n+1$ (o $n+1$ divide algún otro elemento de $U$, que no puede ser ya que el máximo elemento en $U$ es de menos de $2n+1$).

Pero $u\in S$$u|n+1 \implies u|2n+2$, sin embargo,$2n+2 \in S$, por lo que tenemos una contradicción de nuevo.

Por lo tanto, si $P(n)$ mantiene, $P(n+1)$ debe ser cierto, por lo tanto el establecimiento de la inducción.

Answer 2

SUGERENCIA:
Dividir los números de $1$ $2n$ $n$ grupos. Cada grupo es una cadena de números, dos números en el mismo grupo, uno es múltiplo del otro.
Por ejemplo, cuando $n=2$, los grupos podrían ${1,2,4}$ y ${3}$.

Answer 3

Aquí es una prueba no muy por inducción:

Deje $S=\{1,2,3,\ldots,2n\}$ y supongamos que existe al menos un $(n+1)$-element set $C\subset S$ de manera tal que no hay dos elementos de $C$ son múltiplos uno de otro.

Considere ahora el más pequeño elemento $x\in C$. Desde $C$ $n+1$ elementos, tenemos $x\le n$; de lo contrario, no hay espacio en $C$ para todos los elementos que necesita.

Sin embargo, a continuación, $2x$ $S$ pero no se en $C$. Y $x$ es el mayor divisor adecuado de $2x$, por lo que el único divisor de $2x$ $C$ $x$ sí (recuerde que $x$ fue el más pequeño elemento de $C$).

Por lo tanto, el conjunto de $(C\setminus\{x\})\cup\{2x\}$ es en sí una posible $C$, y su elemento más pequeño es mayor que $x$.

Por lo tanto, podemos seguir doblando el elemento más pequeño de $C$ hasta el elemento más pequeño es mayor que $n$, lo cual es absurdo, por lo original de la $C$ no han existido.

---

Para formalizar esta prueba, uno podría expresar como una prueba por inducción sobre $h\ge 0$ que para cualquier $h<n$ luego theset $$ \{n-h,n-h+1,\ldots,2n-1,2n\} $$ no contiene subconjunto de tamaño $n+1$ donde ningún elemento divide a otro.

Answer 4

Sencillo de inducción.

deje $S$ se fijó en la pregunta seleccionada de $N$: $S=\{i_1,i_2,i_3,...i_k\}$ enteros todos $\le 2n, n\in N$, $S_m\subseteq S$ de los distintos números enteros. $|S_m|=n+1$

$1)$caso base: $n=1: S=\{1,2\}/\{1,1\}/\{2,2\};S_m=\{1,2\}$; $1|2$

$2)$hipótesis inductiva: $\forall_{S_m\subseteq S\wedge |S_m|=n+1}\exists_{c,d\in S_m\wedge c\neq d}c|d$

$3)S_1=\{i_1,i_2,i_3,...i_t\}$ enteros todos $\le 2(n+1)=2n+2, n\in N$,$S\subseteq S_1$,$S_{m_1}\subseteq S_1$ de los distintos números enteros. $|S_{m_1}|=n+1+1=n+2$

$4)$ Tenemos $3$ diferentes casos aquí:

$a)(2n+1\notin S_{m_1}\wedge 2n+2\notin S_{m_1})$: $S_m\subseteq S_{m_1}\subseteq S$ y así inductivo hipótesis puede ser aplicado. $b)(2n+1\in S_{m_1}\wedge 2n+2\notin S_{m_1})\vee (2n+1\notin S_{m_1}\wedge 2n+2\in S_{m_1})$:en estos casos inductivo hipótesis tiene como $n+1$ distintos números enteros son seleccionados a partir de $S$. $c)2n+1\in S_{m_1}\wedge 2n+2\in S_{m_1}$:En este caso hay dos posibilidades:$1)$si $2$ o $n+1$ seleccionado hecho, ya que tanto la brecha $2n+2$. $2)$ de lo contrario, $n+1$ puede ser dicho para ser seleccionado como cualquier otro # que divide $2n+2$ debe dividir $n+1$. el elemento más pequeño en $S_{m_1}$ debe $\le n+1$/debe ser $\ge n$ cifras en $S_{m_1}/S$. con $n+1$(número de $n+1$ $n$ otros) enteros seleccionados de $S$, inductivo hipótesis puede ser aplicado.

Por lo $\forall_{S_m\subseteq S\wedge |S_m|=n+1}\exists_{c,d\in S_m\wedge c\neq d}c|d\rightarrow \forall_{S_{m_1}\subseteq S_1\wedge |S_{m_1}|=n+2}\exists_{c,d\in S_{m_1}\wedge c\neq d}c|d$

Por lo tanto, en el principio de Inducción Matemática $\forall_{n\in N}[\forall_{S_m\subseteq S}\exists_{c,d\in S_m, c\neq d}c|d]$