El problema de Louis Pósa

Hoy os traigo un problema que puede ser realmente complicado si no se sigue el camino correcto pero extremadamente sencillo si se encuentra la senda:

Sea n un número natural. Demostrar que si se escogen n + 1 números naturales de los del conjunto {1, … , 2n} se tiene que al menos dos de ellos son primos relativos

Si alguien conocía ya el problema que no diga la solución. Como suelo decir lo interesante es que lo resolvamos desde cero. Y lo vuelvo a decir: muy difícil o muy fácil dependiendo del camino escogido para su resolución.

¿Por qué he llamado así al problema?. Pues porque Paul Erdös propuso el problema a Louis Pósa cuando éste tenía 12 años y el amigo Louis lo resolvió casi al instante mientras se comía una sopa. Impresionante, sobre todo teniendo 12 añitos.

No pongo la fuente porque ahí esta la solución. Cuando lo resolváis la pongo.

Actualización: Ya que está resuleto pongo la fuente: Mathematics Weblog

Autor: ^DiAmOnD^

Miguel Ángel Morales Medina. Licenciado en Matemáticas y autor de Gaussianos y de El Aleph. Puedes seguirme en Twitter o indicar que te gusta mi página de Facebook.

8 Comentarios

  1. Creo que se demuestra, simplemente viendo que dos números naturales consecutivos siempre van a ser primos entre si, es imposible que tengan factores común.
    Ejemplo: Veamos la sucesión de números que tienen como factor al 2: 2,4,6,8… es decir, cada dos números. Con cualquier factor que cojamos, va a ocurrir esto, luego concluimos que dos números consecutivos, serán siempre primos entre si.
    En el conjunto 1…2n, siempre encontraremos al menos 2 números.
    Conclusión: Siempre habrá al menos dos numeros primos entre si en el conjunto citado.

    Publica una respuesta
  2. Para cualquier número X y dada su descomposición en producto de números primos… siempre tenemos que X+1 no es divisible por ninguno de los factores primos de X (se obtiene resto 1), por tanto X y X+1 son primos entre sí.

    Además como n es natural es mayor que 0, por tanto n+1 es al menos 2 y siempre hay al menos dos números (consecutivos) en el conjunto 1,…,2n.

    Uniéndolo todo queda resuelto 😛
    (Acabo de ver que es lo mismo que dice Javier… dos personas no pueden estar equivocadas!! xD)

    Publica una respuesta
  3. Como casi siempre resolvéis el tema muy rápido :).

    Exacto, esa es la razón. Si escogemos n + 1 números naturales entre 1 y 2n siempre habrá al menos 2 que son consecutivos. Como dos números consecutivos son siempre primos relativos (para esto valdría el razonamiento de mimetist; yo tenía otro con más cuentas) tenemos el resultado pedido.

    Enhorabuena a los dos 😀

    Publica una respuesta
  4. Jejeje, claro que esto con 12 años no lo hacemos ninguno de nosotros.

    Yo no sabía lo que eran los primos relativos a esa edad 🙁

    Publica una respuesta
  5. mimetist cuando lo vi pensé lo mismo que tú: ¿yo sabía lo que eran dos números primos relativos con 12 años? 😛

    Publica una respuesta
  6. otra:supongo que ningun numero es pesi a otro entonces todos son divisibles por lo menos por un primo,ahora sea pk (p es el factor comun)el menor de estos ,ahora el mayor de estos como minimo sera p(k+n)y siempre este sera > 2n,lo cual es un absurdo .

    como p>=2 y k >=1 entonces 2(k+n)>2n.

    Publica una respuesta
  7. si tuviera 2n numeros empezando de cualquier numero, entonces tambien habran al menos 2 numeros coprimos en los n+1 numeros escogidos,en general si tuviera kn numeros es necesario y suficiente tomar [kn/2]+1 numeros para que al menos 2 sean coprimos,y esto se debe al primer primo.

    Publica una respuesta

Puedes utilizar código LaTeX para insertar fórmulas en los comentarios. Sólo tienes que escribir
[latex]código-latex-que-quieras-insertar[/latex]
o
$latex código-latex-que-quieras-insertar$.

Si tienes alguna duda sobre cómo escribir algún símbolo puede ayudarte la Wikipedia.

Y si los símbolos < y > te dan problemas al escribir en LaTeX te recomiendo que uses los códigos html & lt; y & gt; (sin los espacios) respectivamente.

Envía un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *