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
de tal manera que entre ellos no haya tres distintos, digamos
, tales que
sea divisor o múltiplo de
?
A por él.
¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉
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
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
El conjunto de todos los impares entre 3 y 2013 inclusive verifica lo pedido..puede ser un buen comienzo.
Pingaro, estas contradiciendo a Juanjo…
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… Lee más »
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í… Lee más »
Acido, creo que estás contando multiplos de más, como el 77 que es múltipo de 7 de 11 a la vez.
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.
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!
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
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… Lee más »
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:… Lee más »
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?
Parte entera de raíz cuadrada de 2014?
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… Lee más »
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…
¡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}… Lee más »
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.
De acuerdo con el razonamiento de rtomas y marcoT me pregunto si podré añadir a ese o esos conjuntos algun número par
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).
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.
Á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… Lee más »
MarcoTac, tienes toda la razón.
Muchas gracias por la corrección, un saludo.
Hola a todos.
En una primera pensada, he llegado a lo siguiente:
Sea
un conjunto que verifique la propiedad y sea
. Sea
el conjunto obtenido reduciendo módulo
todos los elementos de
. Entonces
y si
entonces
, ya que en caso contrario
(contradiciendo la hipótesis de que
verifica la propiedad). De aquí se obtiene (por el principio del palomar) que
. En particular,
.
Por otro lado,
.
Por tanto el par
pertenece al recinto limitado por las rectas
y
(pues
)…
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…
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… Lee más »
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).
Estupendo cierre acido!
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… Lee más »
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… Lee más »
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
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.
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… Lee más »
Hola.
En mi comentario «RB | 5 de febrero de 2014 | 11:45» probé (si no me equivoqué) que
. Entonces si existiera algún conjunto
con
, entonces tendríamos que
, es decir,
luego
luego
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.
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.
Ok, ¿y cambiando el 671 por 672?
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.
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 S. Sea S’ el conjunto obtenido reduciendo módulo k todos los elementos de S. Entonces [0] S’ y si [a],[b] entonces [a] [b], ya que en caso contrario k a-b (contradiciendo la hipótesis de que S verifica la propiedad). De aquí se obtiene (por el principio del palomar) que k+1. En particular, . Veamos con un ejemplo: Sea H =… Lee más »
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