Quinto problema de la Olimpiada Matemática Española 2013 celebrada en Bilbao. Ahí va:
Estudia si existe una sucesión estrictamente creciente de enteros
que cumple las dos condiciones siguientes:
i) Todo número natural puede ser escrito como suma de dos términos, no necesariamente distintos, de la sucesión.
ii) Para cada entero positivo
, se verifica que
.
Que se os dé bien.
¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉
Información Bitacoras.com…
Valora en Bitacoras.com: Quinto problema de la Olimpiada Matemática Española 2013 celebrada en Bilbao. Ahí va: Estudia si existe una sucesión estrictamente creciente de enteros que cumple las dos condiciones siguientes: i) Todo número natural pu……
No tengo tiempo ahora de verificarlo, pero me gusta la siguiente sucesión:
..0, ..1, ..2, ..3
..7, 11, 15, 19,
23, 27, 31, 35
los puntos son una peora de tablas en latex.
Cumple el punto i
Para el punto ii
A partir del 7, cada cuatro términos sumo 16 = 4^2, que tiene parecido con el segundo término de desigualdad n^2/16 = (n/4)^2
A mi suena que va a ser la sucesión de números primos.:-)
Olvidemos mi comentario anterior, el segundo término es cuadrático, por lo que la solución, en caso de existir, no puede ser lineal y debe ser cuadrática o superior
Puede ser la serie de Fibbonacci?
Podemos elegir cualquier grupo de números para iniciar la sucesión que cumpla la condición i). Siempre llegará el momento en el que, para llenar todos los huecos, necesitaremos continuar con nuevos números que deberán, como máximo crecer en progresión aritmética, Esto nos obliga a incumplir, a partir de cierto valor, la condición ii) que crece más deprisa que cualquier progresión de ese tipo. La respuesta a la cuestión es NO EXISTE.
JJGJJG, estoy de acuerdo contigo, pero como se demuestra?
Vaya! Pense que por la conjetura de Goldbach podiamos poner cualquier número natural como suma de dos primos, pero resulta que la sucesión de números primos crece demasiado lenta y no cumple la segunda condición
Niels Bohr, la sucesión de Fibbonacci crece demasiado rápido, ¿cómo lograr la suma de cualquier natural con tan pocos candidatos? Por ejemplo, el término número 100 ya es del orden de 6E20. No creo que podamos lograr completar 6E20 números combinando 100 elementos tomados de 2 en 2. De hecho solo podriamos conseguir a lo sumo 4950, y algunos posiblemente repetidos 🙂
Los primos no son, porque ya para el centésimo primo se incumple la segunda condición. La sucesión de Fibbonacci creo que tampoco (por ejemplo 33 no puede representarse).
No obstante, aunque yo pensé y planteé la misma solución que dice JJGJJG (planteándolo como un problema de crecimiento de funciones, y decidiendo que la pendiente
acabaría por superar cualquier sucesión que estableciéramos), sí que existe solución al problema.
Mis intentos (muy sencillos) han sido: a(0) = 0 por definición a(1) = 1 imprescindible para obtener el 1 Si sigo la estrategia de poner siempre el nº mas grande posible (para crecer suficientemente rápido) cumpliendo i, a(2) = 3 a(3) = 5 a(4) = 7 … es muy lenta. Crece mas rápida mi primera propuesta, pero no sirve. Aun mas rápida es a(i) = i para i€{0,15}, pero en a(16) ya tengo que subir para cumplir ii y si pongo por ejemplo a(16) = 31 (menor valor sin cubrir, salto de 16 en 16 que, aun siendo mas rápida… Lee más »
Construyó la siguiente serie: los números de 0 a 2 cada 1, de 2 a 8 cada 2, de 8 a 32 cada 4, y en general de 2^(2n-1) a 2^(2n+1) cada 2^n. Después todos los números de 0 a 2, de 4 a 8, de 64 a 80 y en general de 2^(2b) a 2^(2n)+2^(n+1).
Se ordenan y se eliminan los repetidos.
Creo que cumple las dos propiedades.
Mmonchi,
la primera parte te entiendo lo que escribes, la segunda (Despues todos …) revísalo, yo al menos no sé que quieres decir
Mmonchi,
Mi pregunta es, en esos intervalos, cada cuanto intercalas
Piensen en binario 😉
Cuando dice que cualquier termino «an» puede ser escrito como «la suma de dos términos no necesariamente distintos», podria darse que an=2*ak, siendo k cualquier valor menor que n? De ser así, entonces la serie podria ser 0,1,2,4,8,16,32….,2^(n-1)
Paul, ¿y cómo escribes el 7 con tu serie? ¿O el 11?
Hola, perdonad el comentario tan poco claro de antes, pero estaba en la calle y no tenía papel para poner en limpio las ideas. Lo que busco es una cadena de números consecutivos que pueda sumar a otros números para obtenerlos todos. Las cadenas son {0,1,2}, {4,5,6,7,8}, {16,17,…,24}, {64,65,…,80}, {256,257,…,288}, en general {2^2n,2^2n+1,2^2n+2,…,2^2n+2^(2n+1)}. Estas cadenas se las voy sumando a números «ancla» que me garantizan que los 2^(2n+1) números siguientes a un número ancla se puedan representar como suma de dos números de la sucesión. Pero como quiero que los números ancla sean los menos posibles, los hago aparecer de… Lee más »
Una vez analizada la serie con más calma he comprobado que siempre cumple a(n)>n^2/32, pero hay casos en los que no se cumple a(n)>n^2/16. Por ejemplo, a(35)=76<35^2/16=76,5625.
Yo sugiero también seguir la recomendación de GOB
desde luego con binarios se ven muchas mas posibilidades. Por ejemplo para poder componer todos los numberos de 4 cifras en binario bastan los siguientes 7: 0000 0001 0010 0100 1000 0101 1010 Para componer todos los de 8 cifras bastaria tener 2 de estas columnas. Habria entonces 7*7=49 elementos. El a_n mayor seria algo asi 2^7+2^5+2^3+2=170 y se cumple que 170 > 49^2/16=150. Generalizandolo a N bloques de 4 cifras (numeros binarios de 4*N cifras), habria entonces 7^N elementos de la serie a_n. El a_n mayor sera el sumatorio de las potencias impares de 2, mayor=2^{4N-1}+… 2^{4N-3} … +2… Lee más »
Ah, pues sí, OCL, siguiendo la recomendación de GOB…
A ver si acabo de escribir cómo sería y lo pongo aquí.
rtomas,
creo que no te salen las cuentas porque al hacer 7*N usas más combinaciones de las necesarias.
Por ejemplo, haces:
0001 1000
0001 1010
0001 0010
Que no son necesarias si tienes
0001 0000
0001 0001
0001 0100
0001 0101
y con las 7 primeras, es particular con estas 4
0000 0000
0000 0010
0000 1000
0000 1010
puedes hacer cualquier número de 5 cifras binarias
Quise decir: » al hacer 7^N »
Así, hasta 5 cifras binarias tenemos 7+4 = 11 elementos de la sucesión (con los que cubrimos todos los naturales de 5 cifras binarias o menos: de 1 a 31). 21 > 121/16
Hasta 6 cifras, otros 4 elementos, total 7+4+4 = 15… 42 > 225/16
Hasta 7 cifras, otros 8 elementos, total 7+4+4+8 = 23… 85 > 519/16
Hasta 8 cifras, otros 8 elementos, total 7+4+4+8+8 = 31… 170 > 961/16 = 60,0625
Y ahora una explicación más completa: Cualquier número natural s se puede separar como suma de un par p y un impar q, con cifras nulas alternas, que tendrían el aspecto binario siguiente: s = abcdefg p = 0b0d0f0 q= a0c0e0g s = p + q Así, la sucesión sería de esta forma: 0, 1, 10, 100, 101, 1000, 1010, 10000, 10001, 10100, 10101, 100000, … Es decir, 000000, 000001, 000010, 000100, 000101, 001000, 001010, 010000, 010001, 010100, 010101, 100000, … Que en decimal sería: 1, 2, 4, 5, 8, 10, 16, 17, 20, 21, 32… Ahora calculemos según el… Lee más »
Bueno, lo expongo un poco mejor: Aquí mi resolución completa: Cualquier número natural s se puede descomponer como suma de un par p y un impar q, con cifras nulas alternas, que tendrían el aspecto binario siguiente: s = abcdefgh p = a0c0e0g0 q = 0b0d0f0h s = p + q Nótese que * para el par p el número de cifras b es también par, 2m siendo nulas m de ellas… * para el impar q el número de cifras b es también impar, 2m-1 siendo nulas m-1 (descartando el cero a la izquierda) Así, la sucesión sería de… Lee más »
Aquí mi resolución completa: Ignórense (o bórrense) mis comentarios anteriores referentes a la resolución. Cualquier número natural s se puede descomponer como suma de dos binarios p y q con cifras binarias nulas alternas, que tendrían el aspecto binario siguiente: s = abcdefgh p = a0c0e0g0 q = 0b0d0f0h s = p + q Esto nos garantiza la condición i) A p y q los llamaré «PARISTA» e «IMPARISTA» por tener cifras binarias no nulas en posiciones pares e impares respectivamente. Nótese que: * para el «parista» p el número de cifras binarias v es par, 2m siendo nulas m… Lee más »
Al editar se fueron las barras \ antes de cada frac de LATEX
gracias, acido,
las cifras alternas, esa es la clave.
Muy entretenido!!!!
Acido
Muy bueno. No lo he revisado, pero la idea es magnífica
Comprobación de la validez de la solución de Acido: El cumplimiento de i) se desprende del razonamiento de construcción de la serie por contener todas las parejas posibles para cada número de dígitos binarios. El cumplimiento de ii) se desprende de la observación de que para cada n=2^k, a(n)= 2^(2k-2). Para cualquiera de estos términos concretos tenemos que a(n)=4*n^2/16, es decir, cumplen ii) sobradamente. El término que ocupa el lugar n=2^(k+1) vale 2^2k que precisamente es el cuádruple del término del lugar 2^k por lo tanto, todos los términos comprendidos entre los lugares m=2^k y m=2^(k+1) cumplirán que 4*m^2/16>a(m)>m^2/16 aunque… Lee más »
JJGJJG, basándome en la lista (parcial) que ha dado ácido, no veo que el término n=2^k valga 2^(2k-2). Por ejemplo, el término n=2^1=2, es a(2)=10=2 en la lista de ácido, no 2^(2-2)=1. Ni tampoco se cumple para n=16… Sólo coincide en la lista de acido en n=2^3.
Si os fijáis, las posiciones n donde hay potencias de 2 son: n=1 (2^0), n=2 (2^1), n= 3 (2^2), n=5 (2^3), n=7 (2^4), n=11 (2^5), n=15 (2^6), n=23 (2^7), n=31 (2^8), …. Qué curioso que coincida con muchos números primos!! Esas cifras son 1+1+1+2+2+4+4+8+8+… Pero 1+2+4+8… = 2^i – 1 De esta forma, en n= 2 * (2^i – 1) + 1 = 2^(i+1) – 1 el valor de a_n es a_n = 2^(2*i) i=0, n=1, an=1 i=1, n=3, an=4 i=2, n=7, an=16 i=3, n=15, an=64 i=4, n=31, an=256 Es similar a lo que dice JJGJJG pero a él se… Lee más »
Ah, por cierto, que aparezcan números primos en las potencias de 2 menos 1 no es nada nuevo, son los famosos primos de Mersenne.
En el caso k=4 evidentemente no es primo, ya que 4 es compuesto. Pero como k=2, k=3, k=5 son primos las potencias de 2 menos 1 sí pueden ser primos y de hecho lo son en estos casos.
Admito mi error en la denominación de los índices. Donde yo he considerado a(n) realmente me estaría refiriendo al término a(n-1). Lo que yo he deducido, entonces, es que a(n-1) es mayor que n^2/16, por lo que, al ser creciente la sucesión, a(n) también cumple ii).