Processing math: 100%

8 votos

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

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|bb|c.

He intentado usar la inducción matemática, pero no puede proceder de k k+1ya 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.

7voto

amakelov Puntos 71

Llame a nuestro conjunto de 3n+1 números de A. Escribir cada una de las aA 2sk donde s0 k es impar. Ahora, los posibles valores de k{1,3,,4n1}, 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, aA,bA, 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,,2n1} 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.

4voto

Misha Puntos 1723

La partición del conjunto de {1,2,,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,
  • 3,6,12,24,48,
  • 5,10,20,40,80,
  • 2n1,4n2
  • 2n+1
  • 2n+3
  • 4n1

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,bab. 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 abbc, 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.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X