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[/latex] números enteros positivos. Demostrar que   <p align="center">[latex] \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

    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 [latex]\cfrac{1}{mcm(a_0,a_1)}\leq 1-\cfrac{1}{2^1}[/latex]
    Puesto que [latex]0<a_0<a_1[/latex]
    tenemos que [latex]a_1[/latex] vale como poco 2, ya que son desigualdades extrictas de números enteros positivos. Se tiene que [latex]mcm(a_0,a_1)[/latex] 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 [latex]\cfrac{1}{mcm(a_0,a_1)}\leq \cfrac{1}{2} = 1-\cfrac{1}{2^1}[/latex]

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

    Si [latex]a_1 > 2[/latex] 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 [latex]2n+2\leq 2^{n+1} [/latex] para todo n positivo. (Es trivial comprobar esta desigualdad)
    Bien, tenemos entonces que ver si [latex]\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}}[/latex]

    Echando cuentas, se tiene que [latex]1-\cfrac{1}{2^{n+1}} = 1 – (\cfrac{1}{2^{n}}-\cfrac{1}{2^{n+1}})[/latex]

    Por lo que equivalentemente se tiene

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

    Como [latex]2n+2\leq 2^{n+1} \rightarrow [/latex] [latex] \cfrac{1}{2^{n+1}}\leq\cfrac{1}{2n+2}[/latex]

    el último término [latex]\cfrac{1}{mcm(a_n,a_{n+1})}\leq\cfrac{1}{2n+2}[/latex] porque [latex]a_n[/latex] 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 [latex]a_{n+1}>a_n[/latex])

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

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

    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

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

    tu razonamiento requiere que $latex \frac{1}{mcm(a_n,a_{n+1})}\leq 2^{-(n+1)}$. Efectivamente se tiene que $latex 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 $latex 2(n+1)\geq 2^{n+1}$ (y lo que se da es la desigualdad con $latex \leq$).

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

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

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

    Alguien me puede explicar por que ha de ser :

    [latex] \cfrac{1}{mcm(a_n,a_{n+1})}\leq\cfrac{1}{2n+2} [/latex]

    😕

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

    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 $latex 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

    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

    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:

    $latex a_{n+1}=2 \cdot a_n$

    Pero después afirmas que $latex a_n=2^n$ sin demostrarlo. Entiendo que haces una inducción mental partiendo del resultado anterior hasta llegar a $latex 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:

    $latex 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:

    $latex 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

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

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

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

    elegir los [latex] a_i [/latex] de tal forma que

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

    es decir,

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

    Por tanto,

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

    Teniendo en cuenta lo anterior, se concluye que

    [latex]{\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}} [/latex]

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

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

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

    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

    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 [latex] a_0<a_1<\cdots<a_n [/latex] es una sucesión que hace máximo
    [latex]{\displaystyle\sum_{i=1}^n\frac{1}{mcm(a_{i-1},a_i)}}[/latex] entonces [latex] a_{i-1}\mid a_i, \ i=1,2,\dots,n[/latex]

    Razonemos por inducción:

    Para [latex] i=1 [/latex]. Supongamos que [latex] a_0\nmid a_1[/latex]

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

    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 $latex n=1$ debería ser cierto (tal como sucede). Además, si $latex n=i$ es cierto, $latex n=i+1$ debería serlo también. Así

    [latex]\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}[/latex]

    [latex]\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})}[/latex]

    [latex]\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}[/latex]

    [latex]\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}}[/latex]

    Luego,

    [latex]\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}}[/latex]

    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

    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 $latex n=1$ debería ser cierto (tal como sucede). Además, si $latex n=i$ es cierto, $latex n=i+1$ debería serlo también. Así

    [latex]\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}[/latex]

    [latex]\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})}[/latex]

    [latex]\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}[/latex]

    [latex]\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}}[/latex]

    Luego,

    [latex]\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}}[/latex]

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

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

    No entiendo el último paso GCCA.

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

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

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

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

    $latex 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 $latex a_{n+1}\geq 2^{n+1}$ entonces $latex mcm(a_n,a_{n+1})\geq 2^{n+1}$ y $latex 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 $latex a_{n+1}<2^{n+1}$.

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

    Luego, $latex \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, $latex 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

    M, veo tu prueba perfecta. Enhorabuena!

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

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

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

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

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

    De $latex 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 $latex \displaystyle{a_i}$ para los cuales no cumplirá la afirmación, puesto que $latex S(a_{n+1})$ puede ser hasta dos veces el valor de $latex 1-\displaystyle\frac{1}{2^{n+1}}$.

    Si $latex A=S(a_{n+1})$ y $latex B=2+\displaystyle\frac{1}{2^n}$, hay dos posibles conclusiones, que los $latex \displaystyle{a_i}$ sean lo suficientemente grandes para hacer que $latex \displaystyle\frac{A}{2} \le \displaystyle\frac{B}{4}$ , por lo que la afirmación cumpliría. Pero si $latex \displaystyle\frac{A}{2} > \displaystyle\frac{B}{4}$, entonces se tiene que cumplir que $latex A > \displaystyle\frac{B}{2}$.
    Esto es como imaginar los valores de $latex \displaystyle{A}$, $latex \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 $latex \displaystyle{a_i}$ enteros positivos.
    (sería interesante sabe bajo que condiciones se cumple)

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

    Brillante M, sobre todo la segunda parte.

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

    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.