Cinco primos relativos por parejas

Vamos con el problema de esta semana. Aquí tenéis el enunciado:

Dado el conjunto S=\lbrace 1,2,3, \ldots ,280 \rbrace, encontrar el mínimo número natural n tal que en todo subconjunto de S que tenga n elementos haya cinco números que son primos relativos dos a dos.

A por él.

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.

11 Comentarios

  1. Una cota superior simple es la siguiente:

    P = Nº de primos en S

    Cota n = 280 – P + 5 dado que siempre entraran 5 primos en cualquier subconjunto de cardinal n

    Publica una respuesta
  2. Disparando un poco al aire es claro que el conjunto que tiene a los multiplos de 2,3,5 y 7 no verifica la propiedad pedida. Asi que cota inferior es la cardinalidad de ese conjunto más uno. Creo que puede ser la exacta incluso (me parece lógico pero no me he parado a mirar los detalles).

    Publica una respuesta
  3. O sea, Daniel, 217.

    140 múltiplos de 2 + 47 múltiplos de 3 y no de 2 + 19 múltiplos de 5 y no de 3 ni de 2 + 10 múltiplos de 7 y no de 2 ni de 3 ni de 5 +1 = 217.

    Publica una respuesta
  4. A mí me parece sensato en el sentido de que una vez metido un factor primo no penaliza meter los múltiplos y parece la forma más económica de meter números minimizando penalizaciones.

    Publica una respuesta
  5. Muy bueno, Daniel Cao.

    Entonces el mínimo pedido queda seguro entre 217 y 226… eso lo tengo claro (lo cual deja sólo 10 posibles soluciones).
    Y aunque el 217 parece buen candidato todavía no estoy seguro de que sea.

    Lo del 226 viene de lo que dijo Mmonchi, lógicamente.

    primos = [2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277]

    Si no conté mal son P = 59
    Así que 280-59+5 = 226

    Cualquier subconjunto de 226 elementos tendrá al menos 5 primos (y, por tanto, 5 primos relativos 2 a 2).

    Publica una respuesta
  6. Daniel, estando de acuerdo contigo creo que la explicación mejora diciendo simplemente que tu ejemplo es un contraelemplo para valores iguales o inferiores a 216.

    Creo que si añado el 1 la situación no cambia por lo que sugiero que la solución es 218.

    Intuitivamente es la solución pues los múltiplos de 11 que no son de los anteriores solo son 11 y 121, de 13 son 13 y 169 luego no puedo meter números sacando de una clase de las ya metidas sin introducir nuevos primos relativos.

    Necesito 7 numeros a meter para anular los múltiplos de 7 que … y me meten mas de 1 primo relativo

    Publica una respuesta
  7. Perdon,
    Para 11 son 11, 121, 143, 187, 209, 253 (6 y <7)
    Para 13 son 13, 169, 221 (3 y <7)
    y el resto son todos primos

    Publica una respuesta
  8. Tomemos un conjunto de 216 números formado por los múltiplos de 2, de 3, de 5 y de 7 menores que 280. Si añadimos un número cualquiera de los otros 64 (que son el 1, los 55 primos entre 11 y 277 y los números 121, 143, 169, 187, 209, 221, 253 y 247) dicho conjunto de 217 cumple la condición.

    Ahora cambiamos un número. Quitamos uno cualquiera y por tanto tenemos dos números del grupo de 64 -digamos el 121 y el 143, que no son coprimos. ¿Hay cinco primos relativos dos a dos? Sí. El 2, el 3, el 5 y el 7 de los números iniciales y cualquiera de los dos nuevos. Si el quitado era uno de esos cuatro no tengo problema en reemplazarlo, por ejemplo con su cuadrado. Lo haga como quiera, siempre voy a tener cuatro números coprimos entre sí sacados del primer grupo, los divisores de 2, 3, 5 y 7, y un quinto número que será coprimo con todos ellos.

    ¿Y si quito los diez divisores de 7 que no lo eran de 2, 3 ni 5? Tengo tres números coprimos entre sí de los 206 divisibles entre 2, 3 o 5 y once del otro grupo de 64. Y como en ese grupo de 64 hay 55 primos, seguro que tengo al menos dos. (Y de aquí sale el número 280).

    Quitar también los divisores de 5, o de 3, aumentará el número de primos.

    Publica una respuesta
  9. El problema de meter al 1 es que es coprimo con cualquier natural pues mcd(n,1) es 1 para cualquier natural y entonces al meterlo ya tienes 5 coprimos (y con esa técnica no puedes hacer los 218 y te quedax en 217).

    Publica una respuesta
  10. Daniel Cao

    Ok (pensaba que el 1 no entraba como coprimo de ninguno)

    Publica una respuesta

Trackbacks/Pingbacks

  1. Bitacoras.com - Información Bitacoras.com Valora en Bitacoras.com: Vamos con el problema de esta semana. Aquí tenéis el enunciado: Dado el conjunto…

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 *