Ni divisor ni múltiplo

Os dejo hoy martes el problema de esta semana. Ahí va:

¿Cuál es la mayor cantidad de elementos que se pueden tomar del conjunto de números enteros

\lbrace 1,2, \ldots ,2012,2013 \rbrace

de tal manera que entre ellos no haya tres distintos, digamos a,b,c, tales que a sea divisor o múltiplo de b-c?

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.

39 Comentarios

  1. que chulo.
    Primera aproximacion trivial. Si esta x, ni x+1 ni x-1 pueden estar asi que la mayor cantidad es menor de 2012/2=1006

    Publica una respuesta
  2. Otra aproximación:

    El conjunto {3,5,7} cumple y el {3,5,7,11} no, pues 11-5=6 y el 3 es divisor

    Publica una respuesta
  3. El conjunto de todos los impares entre 3 y 2013 inclusive verifica lo pedido..puede ser un buen comienzo.

    Publica una respuesta
  4. Ufff lo primero que pensé es que este problema es dificilito.
    Luego pensé en todos los impares excepto el 1 (el 1 divide a todos) y eso serían 1006, que como se ha dicho es cota superior, pero ya he visto que tantos impares no lo cumplen.

    Mi siguiente estrategia es: quitar el 1 (quedan 2012), quitar múltiplos de 2 (quedan 1006), quitar múltiplos de 3 ({5, 7, 11, 13, 17, 19, 23, 25 …} quedan 660 y 17-7 = 2*5), quitar múltiplos de 5 {7, 11, 13, 17, }… y así hasta unos cuantos primos, hasta que se cumpla 🙂
    ¿Antes de la raíz cuadrada de 2013 < 45 dejo de contar los primos?

    Vamos a ver cuántos me quedan si quito hasta el 43:
    [5] 660 – floor(660/6) – 1 = 660 – 133 = 527
    [7] 527 – floor(527/7) – 1 = 527 – 76 = 451
    [11] 451 – floor(451/11) – 1 = 451 – 42 = 409
    [13] 409 – floor(409/13) – 1 = 409 – 32 = 377
    [17] 377 – floor(377/17) – 1 = 377 – 23 = 354
    [19] 354 – floor(354/19) – 1 = 354 – 19 = 335
    [23] 335 – floor(335/23) – 1 = 325 – 15 = 320
    [29] 320 – floor(320/29) – 1 = 320 – 12 = 308
    [31] 308 – floor(308/31) – 1 = 308 – 10 = 298
    [37] 298 – floor(298/37) – 1 = 298 – 9 = 289
    [41] 289 – floor(289/41) – 1 = 289 – 8 = 281
    [43] 281 – floor(281/43) – 1 = 281 – 7 = 274

    Y aquí paro de quitar, me quedan 274 números.

    ¿puede mejorarse?

    Creo que sí, si en lugar de partir del 1 partimos del centro quizá no haya que llegar hasta la raíz de 2013 sino hasta la raíz de 1006 < 34 que sería el primo 31 y podría quizá lograrse con unos 298, pero habría que verlo, quizá unos pocos menos.

    (Espero no haberme equivocado)

    Publica una respuesta
  5. Una cota razonable:
    Tomemos la serie de los números primos menores que 2013. hay exactamente 305 que son 2,3,5,…,2011.
    Descartamos el 2 porque obviamente eliminaría a todos los demás ya que todas las diferencias son pares. Ninguno de los 304 primos restantes tiene divisores distintos de 1 y él mismo por lo que su conjunto cumple la primera condición.
    Para que la diferencia (par) de dos primos sea múltiplo de otro tiene que ser igual o mayor que él doble de él. Esto ocurre siempre si el primo diferencia es menor que los dos tercios. del máximo primo. De aquí deducimos que todos los primos mayores que 2001/3=670,3… cumplen la segunda condición.
    Como el menor primo mayor que 2011/3 que es el primo nº122,: el 673 ya tenemos un conjunto de 305-122+1=184 números que, al menos son una cota inferior de la cantidad buscada. Faltaría comprobar si algún primo menor que el 673 puede incluirse en el conjunto.
    ,.3…

    Publica una respuesta
  6. Acido, creo que estás contando multiplos de más, como el 77 que es múltipo de 7 de 11 a la vez.

    Publica una respuesta
  7. JJGJJG me podés dar algún ejemplo de esto: “Para que la diferencia (par) de dos primos sea múltiplo de otro tiene que ser igual o mayor que él doble de él.” No entiendo bien ese enunciado, ya que cualquier diferencia par entre dos primos al menos será múltiplo de 2 que es primo.

    Publica una respuesta
  8. rthomas; tienes razón (no por el hecho de contradecir a juanjo, sino porque con mi estrategia aparecen, por ejemplo el 7, el 77 y el 777 que contradice lo pedido) Perdón!

    Publica una respuesta
  9. una construccion razonable,
    si empezamos por un k impar podemos ir anyadiendo impares (k+2..)
    hasta 3k, pues (2+3k)-(k+2)=2k y ya no cumpliria el enunciado.
    Esto nos lleva a un conjunto de k elementos con maximo 3k.
    Asi que un conjunto interesante es {673,675,…, 2013} con 671 elementos (no esta muy lejos de 1006!).
    Espero no haberme columpiado

    Publica una respuesta
  10. Es razonable empezar fijándonos en el conjunto de los impares eliminando el 1, I={3, 5, 7, …, 2013}, cualquier diferencia (B-C) será par y por lo tanto cualquier A no será nunca múltiplo de (B-C). Sin embargo, si podemos encontrar divisores de (B-C), por ejemplo si B-C=6, A=3 sería divisor, si B-C=10, A=5 sería divisor. Vamos entonces eliminando los primeros impares del conjunto I, es decir, 3,5,7… hasta un cierto M, obtneniendo el conjunto de impares F={M,M+2,…,2013} con la condición de que que no haya ningún número en el conjunto que sea divisor de la mayor de las diferencias. Es decir, (2013-M)/2<M, despejando tenemos 671<M y por lo tanto M=673. EL conjunto F={673,675,…2013} cumple la condición del enunciado y |F|=671.

    Publica una respuesta
  11. Para Julio Cesar Romero:
    “Para que la diferencia (par) de dos primos sea múltiplo de otro tiene que ser igual o mayor que él doble de él.”
    Precisamente por eso descarté el 2 en primer lugar y, por eso, elijo 673 como límite inferior ya que la diferencia entre dos primos mayores que 673 y menores que 2011 siempre será menor que (2011-673)/2=669 y no podrá ser múltiplo de ninguno del conjunto.

    He empezado a probar los primos menores que 673 en orden descendente y he averiguado que por encima de 500 solo pueden añadirse a mi secuencia los siguientes: 503, 563, 599, 659 y 661 con lo que mi cota inferior para la solución es de 189 números que cumplen. Solo me queda por analizar los primos menores que 500 que no llegan a un centenar.

    Publica una respuesta
  12. eh, MarcoTac, te me copiaste ! 😉

    JJGJJG, es interesante lo de los primos pero no vas a llegar a 671 elementos.

    Y bueno, esta claro que aun no hay ninguna demostracion rigurosa, parece que 671 es imbatible, pero como se demuestra?

    Publica una respuesta
  13. Además de el conjunto de impares F={673,675,…,2013} con 671 elementos, también cumple la condición del enunciado el conjunto de impares G={671,673,…,2011} (también con 671 elementos), ya que:-
    – Todas las diferencias de elmentos de F, b-c, son pares y ningún otro elemento a será múltiplo de b-c.
    – La mayor de las diferencias es 2011-671=1340 y su mayor divisor (sin contar con ella misma ya que es par) es 1340/2=670, que es menor que cualquier elemento de G, y también será menor cualquier otro divisor de esa o de cualquier diferencia menor.

    rtomas, tu razonamiento parece más claro y simple que el mio! pero en esencia se llega a lo mismo.

    Publica una respuesta
  14. si, MarcoT, el razonamiento es basicamente identico. Yo eludi aclaraciones…
    En cualquier caso creo que a todos se nos escapa algun razonamiento para poder asegurar que no hay otros conjuntos con mas de 671 elementos…

    Publica una respuesta
  15. ¡Muy bueno rtomas y MarcoTac!

    Lo que parece que se complica es demostrar que no hay un conjunto mayor.
    ¿no podrá haber uno con un número de elementos entre 672 y 1006?

    Está claro que vuestra solución es válida. Que en ese conjunto las diferencias son pares y no pueden ser divisores de ninguno, y tampoco pueden ser múltiplo de ninguno ya que son menores que 2*673=1346

    (x-673 < 2013-673 = 1340)

    Para M = 671 … 2*671 = 1342 … 2013 – 671 = 1342 así que {671, 673… 2011, 2013} no sirve pero sí {671, 673, … 2011} como también dijo MarcoTac … 2011-671 = 1340

    Publica una respuesta
  16. Creo que hay un total de 271 conjuntos con 671 elementos, los que empiezan por: 403, 405, 407, …, 671,673, donde sólo los 2 últimos tienen todos sus términos que son impares consecutivos, el resto tienen un número variable huecos alternos por el final de la secuencia.

    rtomas y MarcoTac, genial vuestro razonamiento.

    Publica una respuesta
  17. De acuerdo con el razonamiento de rtomas y marcoT me pregunto si podré añadir a ese o esos conjuntos algun número par

    Publica una respuesta
  18. juanjo escribano, no se puede añadir ningún número par a los conjuntos de impares F={673,…2013} y G={671,…2011}:
    Vamos con F:
    – No se pueden añadir ningún par perteneciente a {672,…,2012} ya que tendríamos diferencias b-c=1.
    – No se pueden añadir ningún par perteneciente a {2,…670} porque siempre encontraríamos diferencias b-c=671 (y 671*3=2013), se ve claro que: 673-2=675-4=677-6=…=1341-670=671.
    Para G se puede razonar igual con diferencias b-c=669 (y 669*3=2007, que estaría en G).

    Publica una respuesta
  19. ensnnet no creo que sea cierto lo de los 271 conjuntos….
    por ejemplo, el que empezaría en 669:
    está claro que el conjunto de impares {669,…,2005}, con 669 elementos, es un conjunto válido. Pero no podemos añadir el 2007 (ya que 2007-669=1338 y 669*2=1338), tampoco podemos añadir el 2009 (2009-671=1338), ni 2011, ni 2013, y por supuesto ningún par.

    Publica una respuesta
  20. Ácido y rtomas, un razonamiento para ver que no hay conjuntos con más 671 elementos que cumplan la condición podría ser el siguiente:
    Si el conjunto solución S contiene dos números de la forma n,n+2 (diferencia 2), dicho conjunto no podría contener ningún otro número par (salvo n), el resto han de ser todos impares.
    Ahora vemos las situaciones:
    – Si fijamos que la diferencia mínima entre dos elementos sea 3 el cardinal máximo de S sería |S|=2013/3=671
    – Si S contiene dos números de la forma n,n+2 (diferencia 2) y n es impar, el conjunto S sería sólo de números impares y el mayor conjunto de estos tendría |S|=671 (serían F={673,…,2013} y G={671,…,2011}).
    – Si S contiene dos números de la forma n,n+2 (diferencia 2) y n es par, el conjunto S tendría dos números pares y el resto impares. Ahora bien, es claro, como dije en un comentario anterior, que no se puede añadir ningún par a los conjuntos F y G, si buscamos conjuntos de impares (de forma similar a cuando encontramos F y G) con 669 y 667 elementos también nos daremos cuenta de que no podemos añadir ningún número par.

    Publica una respuesta
  21. MarcoTac, tienes toda la razón.

    Muchas gracias por la corrección, un saludo.

    Publica una respuesta
  22. Hola a todos.

    En una primera pensada, he llegado a lo siguiente:

    Sea S un conjunto que verifique la propiedad y sea k\in S. Sea S' el conjunto obtenido reduciendo módulo k todos los elementos de S. Entonces [0]\in S' y si [a],[b]\in S'-\{[0]\} entonces [a]\neq [b], ya que en caso contrario k\mid a-b (contradiciendo la hipótesis de que S verifica la propiedad). De aquí se obtiene (por el principio del palomar) que |S|\leq k+1. En particular, |S|\leq\min(S)+1.

    Por otro lado, |S|\leq 2013-(\min(S)-1)=2014-\min(S).

    Por tanto el par (\min(S),|S|) pertenece al recinto limitado por las rectas y=x+1, \ y=2014-x y y=3 (pues |S|\geq 3)…

    Publica una respuesta
  23. Una errata en el último párrafo de mi último comentario:
    …si buscamos conjuntos de impares (de forma similar a cuando encontramos F y G) con 669 y 670 elementos…

    Publica una respuesta
  24. MarcoTac,
    ummm Casi casi, pero creo que falta algún detalle, el cual aclaro ahora.
    De todas formas ¡bien enfocado!

    El último punto que dices no acabo de ver que sea completo.

    A los conjuntos F y G no se les puede añadir un número par, pero… ¿no será posible otro conjunto de impares al que se pueda añadir uno o dos pares?

    Veremos que no, pero hay que explicar por qué. No vale decir “si buscamos conjuntos de impares nos daremos cuenta de que no podemos añadir ningún número par”.
    La explicación que diste en la respuesta a Juanjo Escribano me parece demasiado complicada y que no tiene una validez tan general como la que voy a dar:

    No se puede añadir ningún par a F ni a G porque F y G tienen impares separados una distancia 2 (elementos cuya resta es 2) y 2 divide a todo número par (el par añadido sería múltiplo de la resta).

    Esta explicación creo que sí cierra mejor la demostración.
    * Con distancia 3 o mayor no pasamos de 671 (671 * 3 = 2013)
    * Entonces necesitaríamos una distancia 2 para superarlo, pero basta una distancia 2 para que no se puedan añadir pares.
    * Si la distancia de 2 es entre impares todos son impares y no podemos conseguir más de 671 impares
    * Si la distancia de 2 es entre 2 pares el resto son impares que deben estar separados a una distancia mínima de 4 (no pueden estar separados a una distancia de 2 porque hay pares) … lo cual nos da un máximo de 504 impares. (504 + 2 = 506 elementos, muy inferior a 671)

    Publica una respuesta
  25. Muy bien acido! cierras muy bastante bien la demostracion. El unico punto que tal vez no veo tan claro es:
    *Si la distancia de 2 es entre impares todos son impares y no podemos conseguir más de 671 impares

    Pues podriamos considerar distancias arbitrarias entre impares, 2, 4 y 6, por ejemplo (con distancia media menor de 3 para que se pueda superar 671).

    Publica una respuesta
  26. rtomas,
    cierto, habría que probar eso de que con impares no puede conseguirse más de 671.

    Voy a probarlo.

    Supongamos un conjunto C con 672 o más elementos impares (entre 1 y 2013, claro)
    Separo dicho conjunto en dos subconjuntos disjuntos:
    * Subconjunto inferior I = la parte por debajo del número 672 (con cardinal entre 1 y 335) y
    * Subconjunto superior S = la parte por encima de 673 (con cardinal entre 1 y 671 impares posibles).
    Por cada elemento x > 224 perteneciente a I existe un impar 3*x perteneciente a S que no debería estar. Esto es como decir que los impares mayores que 224 que tomemos unidos a los de S no serán más de 671, sea 1 impar mayor que 224 o sean 224 = (672 – 224)/2 impares mayores que 224 en I.
    Esto nos obliga a usar en I impares menores que 224.

    Vuelvo a dividir I en dos subconjuntos: II e IS según sean inferiores a 224 o superiores. |IS| + |S| menor o igual a 671.

    Pero 223 * 9 = 2007 y 223 * 3 = 669 … Es decir, por cada impar de II, menor que 224, se impide la existencia de al menos 1 de S y si es menor que 74 también uno de IS.
    Vuelvo a dividir II en III e IIS. ,, III U IIS = II ; III intersección IIS = vacío
    |IIS| + |IS| + |S| menor o igual a 671.

    Esto nos obliga a usar impares menores que 74…
    73 * 3 = 219; 73*9 = 657; 73*27 = 1971

    74 / 3 = 24
    Esto nos obliga a usar impares menores que 24

    24 / 3 = 6
    Nos vemos obligados a usar impares menores que 6: el 5 ó el 3.
    5*3 = 15; 5*9= 45; 5*27 = … 5*81 = …

    6/3 = 2
    Nos vemos obligados a usar impares menores que 2.
    Y aquí ya hemos llegado a la contradicción o absurdo.

    Publica una respuesta
  27. Acabo de encontrar un pequeño detalle que parece que hemos obviado con la prisas….

    El conjunto de impares S={671,673,…, 2013}, ¡¡¡con |S|=672!!!, si cumple las condiciones del enunciado. Me explico:
    – La mayor de las diferencias es 2013-671=1342 (y es única), pero aunque 1342/2=671 hemos de tener en cuenta que a,b y c han de ser DISTINTOS. Es decir no podemos escoger b=2013, c=671 y a=671.
    – Cualquier otra diferencia es 1340 o inferior (de estas hay varias). Y aquí ya nos valen los razonamientos que hemos expuestos hasta ahora.

    En fin, como dice rtomas, el único punto que queda por aclarar para cerrar completamente la cuestión es demostrar formalmente que no hay conjuntos de impares con más de 672 elementos.

    Publica una respuesta
  28. Oooooops, MarcoTac, ¡¡¡tienes razón!!! me temo que eso invalida mi demostración. jajaja

    Pero ahora sirve como prueba de que la máxima cantidad de elementos es 672.
    xD

    Publica una respuesta
  29. Sea S={671, 673,…,2011, 2013} Del cual ya se probó cumple con la condición propuesta.
    Sea D el conjunto de los valores absolutos de las diferencias entre ellos.
    D={|671-673|, |671-675|,… |671-2013|}
    D={2, 4, …, 1342} = {1*2, 2*2, …, 671*2}
    Luego todo número en el conjunto {1, 2, …, 671} es divisor de al menos algún elemento de D.
    Por lo que no es posible agregar al conjunto S ningún elemento adicional que cumpla con la condición propuesta.

    Publica una respuesta
  30. Matias Carerian, tu comentario está bien y es aclaratorio. Pero cuando construimos el conjunto de impares de diferencia 2 (llegado a {671,…,2013}) lo hicimos con la condición de que este sea el máximo posible. Es decir, construimos un conjunto de impares en el que cada elemento está a una distancia 2 del anterior (o del siguiente) de la forma {k,k+2,k+4,…,3k-2,3k} (que es un conjunto que contiene k+1 elementos al que no se le puede añadir ningún elemento más) y hacemos que 3k sea el máximo posible (3k=2013). A estos conjuntos no se les puede añadir ningún elemento, como bien explicas tenemos las diferencias 2,4,6,…,2k.

    La cuestión que queda abierta es demostrar que no existen conjuntos de números impares en los que alguno o algunos elementos estén a distancias distintas de 2, es decir, a distancias 4,6,… y que cumpliendo la condición del enunciado tengan 672 elementos. Evidentemente si con estas condiciones se demuestra que no hay conjuntos de 672 elementos tampoco los habrá de más de 672 ya que si un conjunto no cumple la condición seguirá sin cumplirla al añadir elementos.

    Publica una respuesta
  31. Hola.

    En mi comentario “RB | 5 de febrero de 2014 | 11:45” probé (si no me equivoqué) que |S|\leq \min(S)+1. Entonces si existiera algún conjunto S con |S|>671, entonces tendríamos que 671<\min(S)+1, es decir, \min(S)\geq 671 luego S\subset\{671,672,\dots,2013\} luego S debe contener a todos los pares de ese conjunto y un impar, o bien a todos los impares más un par, llegando a contradicción.

    Publica una respuesta
  32. RB, el conjunto {671,672,673,…,2011,2012,2013} tiene 1343 elementos (2013-671+1=1343) de los cuales 671 son pares y 672 impares. No se llega a tal contradicción, pueden ser todos impares.

    Publica una respuesta
  33. No hace falta cambiar, si tu demostración es correcta queda demostrado que si |S|>671 el mínimo de S ha de ser mayor o igual que 671 y el único conjunto de impares que cumple la condición sería el encontrado {671,673,…,2013}. Ningún otro conjunto de impares podría tener >671 elementos y cumplir la condición.
    Con esto estaría resuelto.

    Publica una respuesta
  34. RB,
    Tu demostración es muy interesante (mucho más elegante y simple que la mía), pero hay una parte que creo que necesitaba que se explicase un poco más. Dijiste:

    Sea S un conjunto que verifique la propiedad y sea k \in S. Sea S’ el conjunto obtenido reduciendo módulo k todos los elementos de S. Entonces [0]\in S’ y si [a],[b] \in S'-\{[0]\} entonces [a]\neq [b], ya que en caso contrario k\mid a-b (contradiciendo la hipótesis de que S verifica la propiedad). De aquí se obtiene (por el principio del palomar) que |S|\leq k+1. En particular, |S|  \leq\min(S)+1.

    Veamos con un ejemplo:
    Sea H = {671, 673… 2013}
    Tomamos S = H
    con k = min(S) = 671 sería:
    S’ = {[0], [2], [4] … [670], [1], [3], [5], … [669], [0]} = {[0], [1]… [669],[670]}
    |S' - \{[0]\}| = 670
    Nótese que 670 = |S' - \{[0]\}|\neq |S|-1 = 672-1

    Debería decirse:

    por el principio del palomar |S'| \leq k  (\forall k \in S)
    y, en particular, para k = min(S)
    |S'|\leq  \min(S)
    |S' - \{[0]\}| < \min(S) (de menor o igual a menor estricto)
    o bien: |S' - \{[0]\}|\leq \min(S) - 1

    Como |S|-1 en general no es igual que |S' – {[0]}|
    ( en el ejemplo S = H resulta |H| = 672 y |S' – {[0]}| = 670 )
    esa desigualdad no permite asegurar nada respecto a |S|

    |S' – {[0]}| está acotado por el mínimo de S pero |S| en principio puede ser mucho mayor que ese mínimo.

    Si se prueba que no puede haber 3 múltiplos de min(S) (2 distintos de min(S)) en S creo que ya lo tenemos. Por cada b de S que no sea múltiplo de min(S) sólo puede resultar un [b] diferente a los demás, máximo min(S)-1. Y si hay como mucho 2 múltiplos de min(S) el máximo cardinal de S será min(S)-1 + 2 = min(S)+1

    Y probar esto es fácil.

    Sean: k = min(S) ; k2 = k * n2 ; k3 = k * n3
    k3 – k2 = (n3 – n2) * k … es decir, múltiplo de k
    lo cual contradice las condiciones de S

    Luego en S sólo puede haber un múltiplo de min(S) distinto de min(S) … k2 = k * n2 pero nunca 2 o más,
    Por tanto, |S| \leq |S' - \{[0]\}| +2  < \min(S) +2
    O bien la fórmula que diste tú obviando cosas que creo que requerían la pequeña explicación que he dado:
    |S| \leq \min(S) +1

    Para min(S) = 671 … |S| <  671+2 = 673 … máximo |S| = 672

    para \min(S) \leq 670 (especialmente suponiendo otro conjunto de impares que quizá pudiese tener cardinal mayor de 672) … |S| < 670 +2 = 672 y a lo máximo que podríamos llegar sería 671, nunca superarlo. Así que otros conjuntos de impares ni siquiera llegan a igual el cardinal 672 (y mucho menos superarlo).

    Publica una respuesta
  35. Gracias Ácido, sencillamente al tomar clases a k+2 elementos o bien aparece la clase 0 tres veces, o bien hay dos clases distintas de cero iguales. Por tanto, como mucho hay k+1

    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 *