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).

domingo, 15 de septiembre de 2013

Usando la regla y el trisector

Enunciado

La primera tentación que uno tiene al intentar este problema es triscar el segmento dado, y volver a trisecar alguno de los intervalos, esperando que alguno de los puntos así obtenidos sea el central. Al menos a mí me pasó. Tras unas pruebas, razoné que cada uno de los segmentos obtenidos tendría una longitud que sería una fracción del primero con un denominador potencia de tres, y ninguna suma de fracciones con esos denominadores pueden ser la fracción 1/2, así que parecía que estaba perdiendo el tiempo.

Mi siguiente idea fue fijarme en el material puesto a nuestra disposición: una regla y un trisector. ¿Para qué puedes usar una regla sin marcas? Pues para hacer rectas, claro. Necesito un segmento dividido por la mitad, y trazar rectas para llevar esas proporciones al segmento dado.

Sin embargo, es necesario que ese segmento dividido por la mitad esté en una paralela al segmento dado, ya que si no lo está, el trazar esas rectas no garantiza que el resultado esté exactamente en la mitad.

Eso llevó a otro problema ¿cómo trazar una paralela con el material que tenemos?

Se me ocurrió levantar un triángulo sobre el segmento dado, eligiendo como vértice un punto cualquiera que no estuviese alineado con el segmento, y dividir los otros dos lados (no el segmento) con el trisector. Uniendo ordenadamente esos puntos con segmentos trazados con la recta, consigues segmentos paralelos al de abajo (puedes razonar el paralelismo por semejanza).

Como sólo necesitamos un segmento paralelo, usamos el mayor de los dos. Ahora le volvemos a aplicar el trisector. Evidentemente, queda dividido en tres, no en dos, pero usamos tres puntos consecutivos de los cuatro puntos del segmento como si fuese un segmento divido en dos partes iguales, y con la recta trazamos las líneas necesarias para llevar esa división al segmento inicial.

Es mucho más fácil hacerlo que explicarlo, trataré de que lo veáis en un dibujo.

Ahora, vayamos con la demostración formal. En primer lugar, hemos de probar que, independientemente de la elección de C, el segmento KH es paralelo a AB. Para ello, usamos que los triángulos ABC y AKH son semejantes, por tener un ángulo igual y los dos segmentos que lo forman proporcionales. Después, obtenemos el punto R a partir de B y de Q (ver en el dibujo), y con ayuda de R y de P, obtenemos S. Está claro que P es el centro del segmento HQ, y por semejanza, RPQ es semejante a RSB, igual que RHP es semejante a RAS. Ahora, por la proporcionalidad, PQ es proporcional a SB en la misma proporción que HP a AS, y puesto que PQ y HP son iguales, también lo serán AS y SB, con lo que S es efectivamente el punto medio.

jueves, 5 de septiembre de 2013

El juego de los múltiplos

Enunciado

Uno de los comentarios da una solución muy breve, aunque no se explica el razonamiento que nos puede llevar a ella.

La clave está en entender bien cómo funcionan los números en cuanto a ser o no múltiplos de tres.

Si tenemos un número de tres cifras, y queremos que se trate de un múltiplo de tres, sus cifras deben sumar tres o múltiplo de tres. Ahora, observaremos diferentes opciones:

Si las tres cifras son múltiplo de 3, automáticamente el número es múltiplo de 3.

Es imposible que dos de las cifras sean múltiplo de 3, ya que la otra aportaría un sumando una unidad o dos mayor que un múltiplo de tres.

Si hay una cifra múltiplo de 3, otra de las cifras será una unidad mayor que un múltiplo de tres, y la restante será dos unidades mayor que un múltiplo de 3, ya que en otro caso no pueden sumar entre ambas un múltiplo de 3.

Si no hay ninguna cifra múltiplo de 3, las tres cifras deben ser del mismo tipo, es decir, exceder en uno un múltiplo de tres, o bien exceder en dos, ya que en otro caso podemos comprobar fácilmente que no llegan a sumar un múltiplo de 3.

Clasificando así las cifras, es muy sencillo construir múltiplos de tres, como 147, o 243.

En este problema, sólo disponemos de las cifras del 1 al 6, y no podemos repetir. Eso significa que sólo tenemos dos múltiplos de 3 (3 y 6), dos que exceden en 1 (1 y 4) y dos que exceden en 2 (2 y 5), luego sólo podemos construir números que tengan una cifra de cada tipo.

Ahora, está clara la estrategia que debe seguir Luis, ya que siempre puede ganar. Basta escoger una cifra de uno de los tipos, y si Elena elige otro tipo, dejando un único representante de ese tipo, elegir el que se ha quedado sólo, hasta completar el trío de representantes de cada tipo.

Por ejemplo, Luis elige el 4 y Elena el 5. Como el 2 se ha quedado "huérfano", Luis elige el 2, ahora, si Elena elige el 3, Luis puede seleccionar el 6 y completar el 426, que es múltiplo de 3 (evidentemente, Elena se queda con el 531, que también lo es). Y gana Luis.

Si es Elena la que empieza, Luis sigue teniendo ventaja, ya que puede elegir de nuevo el número que se queda único en su tipo hasta completar los tres tipos.

La última pregunta es bastante más difícil de contestar, ya que hay que contar de alguna forma cuántos números podemos construir, y cuántos de ellos serían múltiplos de 3. Vamos a imaginar que sólo elige uno de los jugadores, y que el otro se conforma con lo que queda, ya que para contar las opciones y saber si sale o no múltiplo de 3 nos da igual lo que haga el otro jugador.

Para elegir la primera cifra tiene 6 opciones, para la segunda, 5, independientemente de la cifra que eligiese en primer lugar, y para la tercera, cuatro opciones. Esto, contando todas las posibles ramificaciones del número, haría un total de 6*5*4 = 120 números posibles.

De todos ellos, vamos a contar los que sean múltiplos de 3. El primer número, hemos visto que puede ser cualquiera (6 opciones), pero el segundo sólo puede ser uno de los cuatro que no son del mismo tipo que el primero, y el tercero únicamente puede ser del tipo restante, formado por sólo dos números, es decir, que tendríamos 6*4*2 = 48 posibilidades.

En definitiva, jugando al azar, Luis tendría una probabilidad de ganar de 48/120, equivalente a 2/5, un 40% en porcentaje.