sábado, 21 de septiembre de 2013

Multiplicación grande, resultado pequeño

Enunciado

Este es un problema bastante complicado, porque implica cálculos con polinomios bastante grandes, y no he encontrado una manera de resolverlo que no implique "probar" funciones sencillas. Este método, que yo sepa, no se puede generalizar, aunque a mí me ha servido al menos en dos problemas muy diferentes.

Es difícil encontrar una pauta en el crecimiento de esta multiplicación conforme le vamos añadiendo términos. Veamos los ejemplos que podemos calcular sin mucha dificultad.

El primer elemento que encontramos es 2 (1 + 1/1), evidentemente menor que 3.

El segundo factor es 1 + 1/8 = 9/8, que es poco mayor que 1, así que el producto da 9/4, también menor que 12/4 = 3.

El tercer factor es 1 + 1/27 = 28/27, que nos proporciona 7/3, claramente menor que 9/3.

Hasta aquí, tenemos cierta esperanza de que los términos se simplifiquen hasta dar un patrón claro, pero el cuarto factor, 65/64, nos da un total de 455/192, que, aunque es menor que 576/192 = 3, no es una fracción precisamente sencilla.

No parece mejorar con el siguiente factor, 126/125 que nos da un total de 1911/800. No parece que sugiera un patrón claro.

Una alternativa para estos casos consiste en acotar la sucesión de productos, es decir, probar con una sucesión sencilla (casi tanteando), que sea algo mayor que todos los términos y nos permita generalizar. Así, probaremos que, aunque tomemos tantos términos como queramos, siempre estaremos por debajo del valor que se pide, 3, en particular, si tomamos 2013 términos como pide el enunciado.

No nos vale con una cota constante, ya que cada vez habrá que multiplicarla por un número algo mayor que 1, y crecerá, lógicamente. Necesitamos algo que se acerque a 3 lentamente, para comprobar que el nuevo resultado de añadir un factor nuevo al producto es algo menor que el elemento correspondiente, aunque sea algo mayor que el anterior.

Una sucesión que hace algo similar sería la sucesión 3 - 1/n, y podemos comprobar que sirve a nuestro propósito. Tal vez no sea la única que sirva pero sí es muy sencilla y no es excesivamente difícil operar con ella.

Nuestro objetivo, ahora, es comprobar que desde el primer término, todos los productos de m términos de esa sucesión son más pequeños que 3 - 1/m, y así cualquier producto de cualquier cantidad de términos estará por debajo de 3.

Para hacerlo, comprobaremos que los primeros términos cumplen esa propiedad. De esta forma, 2 no sobrepasa a (es menor o igual que) 3 - 1/1 = 2.

También podemos ver que 2*(9/8) = 9/4 es menor que 3 - 1/3 = 8/3, como puedes comprobar (en realidad, bastaría con que a partir de cierto término sea menor o igual).

El caso es que ahora veamos que, si para cierta cantidad m es cierto que el producto de los m primeros elementos es menor que 3 - 1/m, entonces podemos comprobar que al añadir un factor más, aún estamos por debajo de 3 - 1/(m + 1). Si conseguimos comprobar esta propiedad, todos los productos estarán acotados, y el enunciado estará probado.

Así pues, supongamos que el producto de los m primeros factores es menor que 3 - 1/m.

Añadir un factor nuevo significa multiplicar todo lo anterior por el elemento (1 + 1/(m + 1)3), y como todo lo anterior es menor que 3 - 1/m, el producto ese será seguro menor que (3 - 1/m)*(1 + 1/(m + 1)3).

Ahora, debemos comprobar si el resultado es menor o no que 3 - 1/(m + 1), y, si es así, el razonamiento estará acabado.

Vamos a intentar expresar el producto (3 - 1/m)*(1 + 1/(m + 1)3) de una forma más sencilla. Pasamos por la expresión (3m + 1)*((m + 1)3+ 1)/(m*(m + 1)3) Reduciendo a un polinomio el numerador, pero no el denominador, obtenemos una expresión bastante larga, pero que es la que necesitamos: (3m4 + 8m3 + 6m2 + 3m - 2)/(m*(m + 1)3). Observa que necesitamos mucha precisión para hacer estos cálculos, y necesitamos que el denominador siga factorizado para compararlo con 3 - 1/(m + 1), porque tendremos que restarlo.

Como suponemos que será inferior a esta cantidad, restaremos a 3 - 1/(m + 1) la fracción obtenida. Para eso, le ponemos el mismo denominador, transformándolo en (3*m*(m + 1)3 - m*(m + 1)2)/(m*(m + 1)3) y después en (3m4 + 8m3 + 7m2 + 2m)/(m*(m + 1)3).

La diferencia entre estas dos cantidades es (m2 - m + 2)(m*(m + 1)3). Sólo nos queda darnos cuenta de que es positiva para cualquier valor de m, o al menos a partir de cierto valor de m (en ese caso, los valores inferiores a esa cantidad habría que comprobarlos uno a uno).

Sin embargo, tenemos suerte, porque m2 - m + 2 = m2 - 2*m*(1/2) + 2 = m2 - 2*m*(1/2) + 1/4 + 7/4 = (m - 1/2)2 + 7/4, que es claramente positivo. Y el denominador también lo es para todo m positivo, por lo que tenemos finalizada la demostración (una alternativa sería ver que es una ecuación de segundo grado sin soluciones o que su solución es un número bajo que podemos comprobar a mano).

No hay comentarios: