Fracciones con mínimo común múltiplo

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

Sean a_0 < a_1 < \ldots < a_n números enteros positivos. Demostrar que

 \cfrac{1}{mcm(a_0,a_1)}+\cfrac{1}{mcm(a_1,a_2)}+\ldots+\cfrac{1}{mcm(a_{n-1},a_n)} \leq  1-\cfrac{1}{2^n}

A por él.


Share

22 comentarios

  1. eulerianos | 8 de mayo de 2012 | 11:42

    Vótalo Thumb up 2

    Voy a intentar hacer la prueba por inducción :)
    Aunque dejaré varios comentarios porque no sé porqué, pero en la vista previa, se borran palabras y símbolos látex y estoy desesperando x)

    Primero veamos para n = 1
    tenemos que ver que \cfrac{1}{mcm(a_0,a_1)}\leq 1-\cfrac{1}{2^1}
    Puesto que 0<a_0<a_1
    tenemos que a_1 vale como poco 2, ya que son desigualdades extrictas de números enteros positivos. Se tiene que mcm(a_0,a_1) es un múltiplo de 2 entonces, y el más pequeño (para maximizar la fracción) sería el propio 2. tenemos entonces que \cfrac{1}{mcm(a_0,a_1)}\leq \cfrac{1}{2} = 1-\cfrac{1}{2^1}

  2. eulerianos | 8 de mayo de 2012 | 11:43

    Vótalo Thumb up 1

    Si a_1 > 2 entonces el mcm sería mayor y por consiguiente, la fracción con menor valor, lo que implicaría que se sigue cumpliendo la igualdad.

    Ahora supongamos para n, y veamos si se cumple para n+1
    Para la demostración, haré uso de que 2n+2\leq 2^{n+1} para todo n positivo. (Es trivial comprobar esta desigualdad)
    Bien, tenemos entonces que ver si \cfrac{1}{mcm(a_0,a_1)}+\cfrac{1}{mcm(a_1,a_2)}+\ldots+\cfrac{1}{mcm(a_{n-1},a_n)}+\cfrac{1}{mcm(a_n,a_{n+1})} \leq 1-\cfrac{1}{2^{n+1}}

    Echando cuentas, se tiene que 1-\cfrac{1}{2^{n+1}} = 1 - (\cfrac{1}{2^{n}}-\cfrac{1}{2^{n+1}})

    Por lo que equivalentemente se tiene

    \cfrac{1}{mcm(a_0,a_1)}+\ldots+\cfrac{1}{mcm(a_n,a_{n+1})}\leq 1-\cfrac{1}{2^n}+\cfrac{1}{2^{n+1}}

    Como 2n+2\leq 2^{n+1} \rightarrow  \cfrac{1}{2^{n+1}}\leq\cfrac{1}{2n+2}

    el último término \cfrac{1}{mcm(a_n,a_{n+1})}\leq\cfrac{1}{2n+2} porque a_n vale como poco n+1, y como su mínimo común múltiplo es un múltiplo suyo, tiene que ser como mínimo 2n+2 (ya que a_{n+1}>a_n)

    Aplicando hipótesis de inducción y que el último término \cfrac{1}{mcm(a_n,a_{n+1})}\leq\cfrac{1}{2n+2} para todo n, se resuelve el problema :D

  3. eulerianos | 8 de mayo de 2012 | 11:45

    Vótalo Thumb up 2

    Después de una hora luchando con LaTeX, espero que sea correcta la demostración =D
    y disculpen si hay alguna incoherencia o no quedó claro. Saludos :)

  4. Trackback | 8 may, 2012

    Bitacoras.com

  5. M | 8 de mayo de 2012 | 16:23

    Vótalo Thumb up 1

    Eulerianos, el desarrollo que indicas no prueba el enunciado. Te has liado con las desigualdades en el siguiente sentido:

    tu razonamiento requiere que \frac{1}{mcm(a_n,a_{n+1})}\leq 2^{-(n+1)}. Efectivamente se tiene que mcm(a_n,a_{n+1})\geq 2(n+1). Sin embargo, para que tu prueba fuera válida, lo que debería darse es que 2(n+1)\geq 2^{n+1} (y lo que se da es la desigualdad con \leq).

  6. juantv | 8 de mayo de 2012 | 22:53

    Vótalo Thumb up 1

    El mínimo común múltiplo de dos números (a_0 ,a_1), donde el menor divide al mayor , a_0 < a_1 < a_2 … , será el mayor : a_1 ?

  7. jc | 9 de mayo de 2012 | 01:01

    Vótalo Thumb up 1

    Alguien me puede explicar por que ha de ser :

     \cfrac{1}{mcm(a_n,a_{n+1})}\leq\cfrac{1}{2n+2}

    :?

  8. sive | 9 de mayo de 2012 | 03:46

    Vótalo Thumb up 1

    Yo en seguida me di cuenta de que construyendo el caso más desfavorable, se demostraba el enunciado, pero después le vi una pata coja a mi razonamiento que no he sido capaz de resolver.

    Lo cuento por si a alguien le da alguna idea.

    Es obvio que dados dos enteros positivos a y b, con b>a, el mcm de ambos es, como mínimo, el doble del menor de ellos, es decir, 2a. No lo voy a demostrar porque, como digo, la demostración final no me termina de cerrar, pero es muy fácil.

    Entonces, el caso más desfavorable se conseguiría cuando los sumandos en la izquierda de la desigualdad son máximos, es decir, cuando los denominadores son mínimos.

    No voy a ser muy formal, así que voy a llamar a y b a los números menor y mayor respectivamente en cada sumando.

    El primer denominador mínimo se consigue con a=1 y b=2, en el siguente, el mcm más pequeño posible se conseguiría cuando mcm = 2·2, es decir con a=2, y b=4. En el siguiente, el mcm más pequeño se consigue cuando mcm=2·4, es decir con a=4, y b=8. Es decir, que en la izquierda de la desigualdad tenemos una suma de inversas de potencias consecutivas de 2, comenzando en 2^1, lo que nos dejaría en bandeja la demostración del enunciado.

    Esto se puede escribir de manera más formal, y más detallada, pero dado que la demostración tiene una pega, lo voy a dejar ahí.

    La pega, lo que no soy capaz de demostrar, es que necesariamente haya que usar el caso más desfavorable en cada sumando individual, para conseguir la suma total más desfavorable…

    Es muy tarde, mañana le daré otra pensadita.

  9. Alfa | 9 de mayo de 2012 | 12:08

    Vótalo Thumb up 1

    Si tomamos el mcm de dos números a y b, tendremos como cotas que: a<mcm(a,b)<a*b
    tomando que a_(n+1) tiene que ser mayor que a_n, la cota pasa a ser: 2*a_n<mcm(a_n,a_(n+1))<a_n*a_(n+1).
    Tomando la suceción que hace crecer menos a mcm con las condiciónes del problema:
    a_(n+1)=2*a_n y a_0=1.
    entonces a_n=2^n
    entonces mcm(a_n,a_(n+1))=2^(n+1)
    Al ser a_n la suceción que cumple los requisitos del problema que minimisa el mcm entonces nos da la cota superior a esa suma, la cual es:

    sum(1/mcm(a_k,a_(k+1)), k=0…(n-1))=sum(1/2^(k+1), k=0…(n-1))
    =sum(2^k, k=0…(n-1))/2^(n)=(2^(n)-1)/2^(n)=1-2^(-n).

    Q.E.D.

  10. sive | 9 de mayo de 2012 | 13:37

    Vótalo Thumb up 1

    Alfa tu demostración es muy parecida a mi intento, y lamentablemente contiene el mismo error, me temo.

    Es correcta hasta cuando concluiste que, en el caso más desfavorable:

    a_{n+1}=2 \cdot a_n

    Pero después afirmas que a_n=2^n sin demostrarlo. Entiendo que haces una inducción mental partiendo del resultado anterior hasta llegar a a_0=1

    El problema de este razonamiento, es que estas presuponiendo que si elijes el valor mínimo para el mcm en cada sucesivo sumando, vas a obtener la suma máxima, y aunque eso, en este caso, parece ser cierto, hay que demostrarlo.

    Entiendo que el error es sutil, así que te voy a poner un ejemplo en el que esa misma suposición es errónea. Supongamos que queremos demostrar que:

    mcm(a_0,a_1)+mcm(a_1,a_2)+\ldots+mcm(a_{n-1},a_n) \geq 2^{n+1}-2

    Si hacemos el mismo razonamiento, podemos “demostrarlo” fácilmente… pero resulta que eso es imposible, porque el enunciado es falso. Por ejemplo, no se cumple para:

    a_0 = 1, a_1 = 2, a_2 = 3, a_3 = 6, a_4 = 12

  11. José Antonio | 13 de mayo de 2012 | 14:02

    Vótalo Thumb up 1

    La suma es máxima cuando cada sumando es máximo ¿por qué no?

    Dados dos números enteros positivos con a<b es claro que
    mcm(a,b)\geq\max\{a,b\}=b alcanzándose la igualdad cuando  a\mid b
    Por tanto, para que

    {\displaystyle\sum_{i=1}^n\frac{1}{mcm(a_{i-i},a_i)}} sea máximo, habrá que

    elegir los  a_i de tal forma que

    {\displaystyle a_i\mid a_{i+1}, \ i=0,1,\dots,n-1}

    es decir,

     a_{i+1}=u_ia_i \ i=0,1,\dots,n con  u_i \geq 2 (ya que si  u_i=1 entonces  a_{i+1}=a_i contradiciendo la hipótesis del enunciado).

    Por tanto,

     a_i\geq 2a_{i-1}\geq 2^2a_{i-2}\geq\cdots\geq 2^ia_0\geq 2^i para todo  i\in\{0,1,\dots,n\}

    Teniendo en cuenta lo anterior, se concluye que

    {\displaystyle\sum_{i=1}^n\frac{1}{mcm(a_{i-i},a_i)}=\sum_{i=1}^n\frac{1}{a_i}\geq\sum_{i=1}^n\frac{1}{2^i}=1-\frac{1}{2^n}}

  12. José Antonio | 13 de mayo de 2012 | 14:13

    Vótalo Thumb up 1

    Me acabo de dar cuenta que en la última línea he puesto mal  \geq en lugar de  \leq

  13. sive | 13 de mayo de 2012 | 17:42

    Vótalo Thumb up 1

    José Antonio, la afirmación con la que comienzas tu solución no se puede aceptar sin demostración, porque en este caso cada sumando no es independiente de los demás. Si al hacer máximo un sumando, estas condicionando al siguiente, tienes que demostrar que lo que ganas ahora al maximizar ese sumando, no lo pierdes después en los demás.

    Yo sé que el error es un tanto sutil, y que puede pasar desapercibido, pero está ahí.

    Puse un ejemplo, en la segunda mitad de mi comentario anterior, en el que demostraba que esto puede suceder. Intenta aplicar tu razonamiento al enunciado de ejemplo que puse, y verás como puedes “demostrarlo” sin dificultad, a pesar de ser falso.

  14. José Antonio | 14 de mayo de 2012 | 23:00

    Vótalo Thumb up 1

    Tienes toda la razón Sive. Requiere demostración la afirmación inicial.

    A ver si funciona el siguiente argumento.

    Vamos a demostrar que si  a_0<a_1<\cdots<a_n es una sucesión que hace máximo
    {\displaystyle\sum_{i=1}^n\frac{1}{mcm(a_{i-1},a_i)}} entonces  a_{i-1}\mid a_i, \ i=1,2,\dots,n

    Razonemos por inducción:

    Para  i=1 . Supongamos que  a_0\nmid a_1

  15. gcca | 16 de mayo de 2012 | 17:23

    Vótalo Thumb up 1

    Hola a todos. Hace mucho que no pasaba por el foro.
    Me animo con una demostración:

    Si la afirmación inicial fuese correcta, entonces el caso n=1 debería ser cierto (tal como sucede). Además, si n=i es cierto, n=i+1 debería serlo también. Así

    \frac{1}{mcm(a_0,a_1)}+\frac{1}{mcm(a_1,a_2)}+\ldots +\frac{1}{mcm(a_{n-1},a_n)\}\le 1-\frac{1}{2^n}

    \frac{1}{mcm(a_0,a_1)}+\frac{1}{mcm(a_1,a_2)}+\ldots +\frac{1}{mcm(a_{n-1},a_n)\}+\frac{1}{mcm(a_n,a_{n+1})}\le 1-\frac{1}{2^n}+\frac{1}{mcm(a_n,a_{n+1})}

    \frac{1}{mcm(a_0,a_1)}+\frac{1}{mcm(a_1,a_2)}+\ldots +\frac{1}{mcm(a_n,a_{n+1})\}\le 1-\frac{1}{2^n}+\frac{1}{mcm(a_n,a_{n+1})}\le 2-\frac{1}{2^n}

    \frac{1}{2}(\frac{1}{mcm(a_0,a_1)}+\frac{1}{mcm(a_1,a_2)}+\ldots +\frac{1}{mcm(\a_n,a_{n+1})})\le 1-\frac{1}{2^{n+1}}

    Luego,

    \frac{1}{mcm(a_0,a_1)}+\frac{1}{mcm(a_1,a_2)}+\ldots +\frac{1}{mcm(a_n,a_{n+1})\}\ge 1-\frac{1}{2^{n+1}}

    Lo que contradice la hipótesis. Así, la afirmación es falsa.

    (Un trabajo muy interesente el de gaussianos.com)

  16. gcca | 16 de mayo de 2012 | 17:33

    Vótalo Thumb up 1

    Excusen por el mensaje anterior, al parecer las fórmulas no estaban bien escritas: el emacs dejó el salto de línea.

    Si la afirmación inicial fuese correcta, entonces el caso n=1 debería ser cierto (tal como sucede). Además, si n=i es cierto, n=i+1 debería serlo también. Así

    \frac{1}{mcm(a_0,a_1)} + \frac{1}{mcm(a_1,a_2)} +\ldots + \frac{1}{mcm(a_{n-1},a_n)}\le 1-\frac{1}{2^n}

    \frac{1}{mcm(a_0,a_1)}+\frac{1}{mcm(a_1,a_2)}+\ldots +\frac{1}{mcm(a_{n-1},a_n)}+\frac{1}{mcm(a_n,a_{n+1})}\le 1-\frac{1}{2^n}+\frac{1}{mcm(a_n,a_{n+1})}

    \frac{1}{mcm(a_0,a_1)}+\frac{1}{mcm(a_1,a_2)}+\ldots +\frac{1}{mcm(a_n,a_{n+1})}\le 1-\frac{1}{2^n}+\frac{1}{mcm(a_n,a_{n+1})}\le 2-\frac{1}{2^n}

    \frac{1}{2}(\frac{1}{mcm(a_0,a_1)}+\frac{1}{mcm(a_1,a_2)}+\ldots +\frac{1}{mcm(a_n,a_{n+1})})\le 1-\frac{1}{2^{n+1}}

    Luego,

    \frac{1}{mcm(a_0,a_1)}+\frac{1}{mcm(a_1,a_2)}+\ldots +\frac{1}{mcm(a_n,a_{n+1})}\ge 1-\frac{1}{2^{n+1}}

    Lo que contradice la hipótesis. Así, la afirmación es falsa.

  17. Antonio | 16 de mayo de 2012 | 17:50

    Vótalo Thumb up 1

    No entiendo el último paso GCCA.

    En general,  \cfrac{1}{2}x\leq  y no implica que  x\geq y. Por ejemplo,  \cfrac{1}{2} 2\leq 3 pero no es cierto que  2\geq 3.

  18. M | 16 de mayo de 2012 | 18:32

    Vótalo Thumb up 1

    A continuación se indica una prueba (por inducción) formalizando un poco las ideas expuestas anteriormente:

    El caso n=1 es obvio. Supongamos cierta la propiedad para un natural n y veámosla para n+1. Sean 1\leq a_0< a_1 <\ldots <  a_n <  a_{n+1} naturales. Entonces:

    S_{n+1}:=\displaystyle{\sum_{i=0}^{n}} \dfrac{1}{mcm(a_i,a_{i+1})}\leq 1-\dfrac{1}{2^n}+\dfrac{1}{mcm(a_n,a_{n+1})}.

    Primero, si a_{n+1}\geq 2^{n+1} entonces mcm(a_n,a_{n+1})\geq 2^{n+1} y S_{n+1}\leq 1-\frac{1}{2^n}+\frac{1}{ 2^{n+1}}=1-\frac{1}{2^{n+1}}.

    Supongamos, en segundo caso, que a_{n+1}<2^{n+1}.

    Ya que mcd(a_i,a_{i+1})|a_i y mcd(a_i,a_{i+1})|a_{i+1}, tenemos que mcd(a_i,a_{i+1})|(a_{i+1}-a_{i}), siendo a_{i+1}-a_{i} positivo por hipótesis. En particular, mcd(a_i,a_{i+1})\leq a_{i+1}-a_{i}.

    Luego, \dfrac{1}{mcm(a_i,a_{i+1})}=\dfrac{mcd(a_i,a_{i+1})}{a_i\cdot a_{i+1}}\leq \dfrac{a_{i+1}-a_{i}}{a_i\cdot a_{i+1}}=\dfrac{1}{a_i}-\dfrac{1}{a_{i+1}}.

    Finalmente, S_{n+1}\leq \displaystyle{\sum_{i=0}^n}\left(\dfrac{1}{a_i}-\dfrac{1}{a_{i+1}}\right)=\dfrac{1}{a_0}-\frac{1}{a_{n+1}}< 1-\dfrac{1}{2^{n+1}}.

  19. Antonio | 16 de mayo de 2012 | 18:41

    Vótalo Thumb up 1

    M, veo tu prueba perfecta. Enhorabuena!

  20. gcca | 17 de mayo de 2012 | 16:45

    Vótalo Thumb up 1

    Hola Antonio, lo explico de otra manera (debí ser más explícito)

    Si
    S(a_n)=\displaystyle\sum_{i=0}^{n-1}\frac{1}{mcm(a_i,a_{i+1})},
    B(a_n)=\displaystyle\frac{1}{mcm(a_n,a_{n+1})} y
    b=\displaystyle{1-\frac{1}{2^n}}.

    Luego,
    B(a_n)\le 1,
    S(a_n)\le b y S(a_n)+B(a_n)=S(a_{n+1}).

    Así
    S(a_n)+B(a_n)\le b+B(a_n)\le b+1 \longrightarrow S(a_{n+1})\le b+1,
    donde b+1=2-\frac{1}{2^n} .

    De S(a_{n+1})\le 2-\frac{1}{2^n} \longrightarrow \frac{1}{2}S(a_{n+1})\le 1-\displaystyle\frac{1}{2^{n+1}} es posible asumir que existen valores de \displaystyle{a_i} para los cuales no cumplirá la afirmación, puesto que S(a_{n+1}) puede ser hasta dos veces el valor de 1-\displaystyle\frac{1}{2^{n+1}}.

    Si A=S(a_{n+1}) y B=2+\displaystyle\frac{1}{2^n}, hay dos posibles conclusiones, que los \displaystyle{a_i} sean lo suficientemente grandes para hacer que \displaystyle\frac{A}{2} \le \displaystyle\frac{B}{4} , por lo que la afirmación cumpliría. Pero si \displaystyle\frac{A}{2} > \displaystyle\frac{B}{4}, entonces se tiene que cumplir que A > \displaystyle\frac{B}{2}.
    Esto es como imaginar los valores de \displaystyle{A}, \displaystyle{B} y sus mitades en la recta numérica. Como existe un intervalo en el que la propiedad no cumple, la afirmación no puede tomarse como válida para todos los \displaystyle{a_i} enteros positivos.
    (sería interesante sabe bajo que condiciones se cumple)

  21. Sive | 18 de mayo de 2012 | 03:26

    Vótalo Thumb up 1

    Brillante M, sobre todo la segunda parte.

  22. kevin | 25 de abril de 2013 | 17:26

    Vótalo Thumb up 1

    la solucion es 5

Escribe un comentario

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. Utiliza la Vista Previa antes de publicar tu comentario para asegurarte de que las fórmulas están correctamente escritas.