Demostrar que cualquier conjunto de números de $3n+1$de % de $\{1,2,...,4$n $\}$ contiene tres diferentes números $a$, $b$, $c$ tal que $a|b$ y $b|c$.

Question

Para arbirary interger $n>0$, demostrar que el conjunto de $3n+1$ número de $\{1,2,...,4n\}$ contiene tres números diferentes $a$, $b$, $c$ tal que $a|b$$b|c$.

He intentado usar la inducción matemática, pero no puede proceder de $k$ $k+1$ya que no está claro cómo elegir a tres nuevos números enteros desde el agrandamiento de conjunto.

Desde mi experiencia, las respuestas a este tipo de problemas pueden aparecer como un (alucinante) construcción de boquetes, pero no puedo pensar en una manera de completar la construcción de tales.

Answer 1

Llame a nuestro conjunto de $3n+1$ números de $A$. Escribir cada una de las $a\in A$ $2^sk$ donde $s\geq0$ $k$ es impar. Ahora, los posibles valores de $k$$\{1,3,\ldots,4n-1\}$, lo que ha $2n$ elementos, y tenemos $3n+1$ números, por lo que algunos números se terminan con el mismo $k$. Si tenemos al menos tres números con el mismo $k$, estamos hace porque se van a separar una de la otra en secuencia.

Así que supongamos que no hemos terminado - entonces, por Encasillar habrá, al menos, $n+1$ disjuntos a pares de números de $a,b$ donde $a< b$, $a\in A,b\in A$, y $a$ $b$ comparten el mismo impar parte $k$. Pero para cada par, el correspondiente impar parte $k$ sólo puede ser entre $\{1,3,\ldots,2n-1\}$ porque de lo contrario $b>4n$; ya que estos son $n<n+1$ posibilidades, esto es una contradicción, por lo que este caso no puede surgir.

Answer 2

La partición del conjunto de $\{1,2,\dots,4n\}$ a $2n$ cadenas (algunos de los cuales son bastante cortos), comenzando con un número impar y doblando a cada paso:

• $1, 2, 4, 8, 16, \dots$
• $3, 6, 12, 24, 48, \dots$
• $5, 10, 20, 40, 80, \dots$
• $\dots$
• $2n-1, 4n-2$
• $2n+1$
• $2n+3$
• $\dots$
• $4n-1$

Si tomamos cualquier $2n+1$ números, entonces vamos a obtener dos números de la misma cadena, y entonces uno divide la otra: hemos encontrado un par de $a, b$$a \mid b$. Esa es la versión fácil del problema, para lo cual se pidió más a menudo. (Véase, por ejemplo, esta pregunta, que es donde tengo la idea.)

Para garantizar en su lugar $a, b, c$ tal que $a \mid b$$b \mid c$, tenemos tres números en una cadena. Por lo que necesita para demostrar que si elegimos $3n+1$ números, entonces usted está garantizado para terminar con tres en la misma cadena.