El Tamiz

Ignora lo accesorio, atesora lo esencial

Desafíos - Los cristales blindados de Bootes (solución)

El Tamiz: Desafío

La semana pasada os planteamos el primer desafío de la temporada, el de los cristales blindados de Bootes. Era un desafío puramente matemático y con un matiz interesante: que hay muchas posibles soluciones (muchos algoritmos para calcular la resistencia de los cristales), no sólo una. La cuestión estaba en llegar a una solución más eficaz que las de los demás.

Como me pasa siempre, he disfrutado como un enano leyendo vuestras soluciones. Estos desafíos me vienen de perlas como cura de humildad: yo estaba orgulloso de la mía, pero luego ha resultado que no era ni de lejos la óptima, y las vuestras (y sus explicaciones) me han encantado a la vez que bajado los humos.

Pero recorramos juntos los distintos grupos de soluciones, que son básicamente tres. He intentado describirlas en el orden en el que suelen ocurrírsele a quien piensa en el problema, pero ese orden es además, claro, orden de eficacia de menor a mayor. Sospecho que el primer tipo es el primero que se le ocurre a casi cualquiera al pensar en el problema, luego te planteas el segundo –si es que llegas ahí, claro– y finalmente el tercero. Por si a quienes no hayáis llegado lejos en este proceso os sirve de algo, yo tampoco llegué al tercer grupo, así que podemos llorar juntos.

Aunque sean diferentes todas las soluciones, naturalmente, tienen algo en común: que las pruebas con el segundo cristal son puramente secuenciales, aumentando o disminuyendo la resistencia de uno en uno. Es la única manera, al fin y al cabo, de asegurar el valor de la resistencia del cristal. Si sólo tuviéramos un cristal, de hecho, las pruebas tendrían que ser secuenciales de 1 a 100. Pero podemos utilizar el segundo cristal para reducir el intervarlo en el que hacemos las pruebas secuenciales, y en cómo hacerlo es donde se diferencian vuestras propuestas y los grupos en los que se dividen.

He escrito un programita en python para probar vuestras soluciones. Cerca del principio he llamado pruebas_XXXX al sistema de pruebas de que se trate, para que puedas ver los resultados tú mismo. Para probar una solución determinada no hace falta más que cambiar la línea “pruebas = pruebas_XXX” y poner, en vez de pruebas_XXX el conjunto de pruebas que quieras probar de los de arriba.

Más fácil aún, si vas a http://eltamiz.com/files/disparos.html puedes simular cualquier solución prefijada o la que tú quieras probar (introduciendo los números de prueba del primer cristal entre comas). Gracias a Sergio por este archivo, mucho más sencillo que modificar y ejecutar el mío.

Voy a llamar a este primer grupo soluciones de punto medio (en el programa es el conjunto pruebas_bin). Básicamente, con 2 cristales y resistencia 1-100, al no saber la resistencia, empezamos probando con el punto medio del intervalo total, que es 50. Si el cristal resiste es que el nuevo intervalo es 51-100, cuyo punto medio es 75, si resiste ahí entonces está en 76-100, cuyo punto medio es… y así hasta que el primer cristal revienta.

Una vez hecho eso, como en todas las soluciones, se utiliza el segundo de manera secuencial. Por ejemplo, si el primer cristal aguanta 50 pero no 75, empezamos en 51 y vamos subiendo hasta que el cristal se rompa.

Este primer grupo tiene un problema horrible, que manda todo a freír espárragos tanto en el número máximo de disparos como el número medio: si el primer cristal se rompe en 50, entonces tenemos que empezar desde 1 y podemos llegar a 49 sin que el segundo se rompa, lo cual supone 50 disparos. La media de disparos de este tipo de soluciones es también muy alta comparada con otras, de unos 19 disparos.

El segundo grupo es bastante mejor que el primero; se trata de las soluciones de incremento constante. En ellas, el primer cristal se prueba incrementando la potencia del disparo una cantidad fija (2, 5, 10, 20, lo que sea) hasta que se rompa. Luego, como siempre, se prueba el intervalo restante de manera secuencial con el segundo cristal.

Este tipo de soluciones tienen la ventaja de que, si el incremento no es muy grande, cuando se rompa el primer cristal el segundo no hace falta probarlo muchas veces. Por ejemplo, con un incremento de 5, si el primer cristal aguanta 10 pero se rompe en 15 sólo hace falta probar el segundo de 11 a 14. Pero claro, supongo que ves el dilema: cuanto más pequeño el incremento del primer cristal, más pruebas con el primer cristal harán falta. Pero cuanto más grande ese incremento, más pruebas harán falta con el segundo. ¿Cuál es el intervalo idóneo?

La respuesta es que el incremento idóneo es 10. Aunque algunos lo habéis demostrado más concisamente, creo que la explicación de Alfonso es la más clara:


Puesto que sólo tenemos 2 cristales, la mejor estrategia sería utilizar el primer cristal para acercarnos al objetivo y el segundo cristal para afinar. Consideremos que tenemos un rango de posibles resistencias entre 1 y n. (En el desafío, n=100 en primera instancia).

Primer cristal

Disparamos consecutivamente hacia el primer cristal con potencias de disparo múltiplos de un factor que denominaremos A (de acercamiento). Por ejemplo, si consideramos que A=5, disparamos hacia el primer cristal con potencias de disparo de 5, 10, 15, 20, etc… hasta que el primer cristal se rompe. En ese momento, sabemos que el valor correcto de resistencia está entre las 2 últimas potencias de disparo utilizadas, que indican el límite inferior y el límite superior de los valores posibles de la resistencia.

El valor máximo de disparos para este primer cristal es de n/A, redondeado hacia abajo. Redondeamos hacia abajo ya que no hace falta realizar ningún disparo de potencia superior a n porque el propio n indica el límite superior.

“valor máximo de disparos para primer cristal” = n/A

Segundo cristal

Disparamos consecutivamente de menor a mayor, una a una, todas las potencias de disparo intermedias entre los 2 límites anteriormente encontrados, hasta que descubrimos cuál es el umbral de resistencia.

Puesto que entre los 2 límites anteriormente encontrados sólo hay A-1 posibles potencias, el valor máximo de disparos para este segundo cristal es de A-1.

“valor máximo de disparos para segundo cristal” = A-1

Desarrollo de los resultados observados

Sumando ambos resultados, obtenemos la ecuación del número máximo de disparos, denominado Tmax, que se realizarían en función del factor de acercamiento A:

“número máximo de disparos totales” = Tmax = n/A + A-1

es decir,

Tmax = n*A-1 + A – 1

Para obtener el valor mínimo de disparos necesarios derivamos la ecuación con respecto a A:

dTmax/dA = -1n A-2 + 1

Igualamos a cero para obtener el mínimo:

dTmax/dA = 0 = -n* A-2 + 1

1 = n/A2

A2 = n

A = √n


En el caso que os planteábamos, como n = 100, el incremento idóndeo (lo que Alfonso llama factor de acercamiento) es la raíz de 100, que es 10. Podéis comprobar esa solución en el programa como pruebas_10, y veréis que mejora al grupo anterior de soluciones en todos los aspectos: el máximo número de disparos pasa de 50 a 19, y la media baja a unos 11 disparos.

Aquí es donde me quedé yo. ¡Pero no es el final del camino! Nuestros finalistas y ganador fueron más allá, ganándose mi admiración y espero que la vuestra. Este último grupo de soluciones es el de soluciones de incremento decreciente.

El quid de la cuestión es que el incremento no tiene por qué ser fijo, y que al no hacerlo fijo puede mejorarse el resultado. El principal defecto de las soluciones del grupo anterior es que mantienen fijo el incremento, pero no mantienen fijo el número combinado de disparos entre los dos cristales. Por ejemplo, si usamos incrementos de 10, no es lo mismo que el primero se rompa en 20 que en 90: en el segundo caso habremos disparado mucho más. Este tercer grupo de soluciones mantiene fijo el número combinado de disparos en el peor caso, reduciendo así el incremento en cada paso.

Pero, como siempre, mejor os lo explican ellos que yo. Por fin conocéis al primero de los finalistas, Jose, que vio la luz del incremento decreciente (su primera solución era de incremento fijo) así:


Ahora bien, los saltos que se hacen con el primer cristal no tienen porque ser de igual longitud. La idea de este método es ir reduciendo la longitud de forma que si la resistencia buscada está al final de uno de estos intervalos (el peor caso) el número de disparos sea el mismo para todos los intervalos.

Por ejemplo, empezaríamos probando con una potencia 10, si se rompe probaríamos secuencialente con las potencia de 1 hasta 9 hasta que se rompa, si se rompe en 4 la resistencia sería 3 (4-1) si probamos todos y no se rompe (este es el peor caso) es que la resistencia era 9. Es este último caso habremos hecho 10 (1+9) disparos.

Si al probar con 10 no se rompió daríamos un salto de 9 y probaríamos ahora con 19 (10+9) para estar seguros que si se rompe, en el peor caso para ese intervalo (resistencia 18), solo necesitaremos 8 disparos adicionales para localizar la resistencia exacta. En ese caso habremos hecho también 10 (2+8) disparos.

Siguiendo con esta idea la máxima resistencia que podremos determinar será 10 + 9 … + 2 + 1 = 10 * ( 10+1) / 2 = 55 resistencias distintas.

Generalizando, si el salto inicial es s la resistencia máxima n que podremos determinar determinar será

n = s(s+1)/2

Cómo lo que queremos conocer es el salto inicial en función de la resistencia máxima n, despejamos y nos sale:

s = (-1 + sqrt( 1+8n) )/2

[la solución negativa no tiene sentido]

Por tanto, si la resistencia máxima es 100 el salto inicial sería de 13,65… o sea, 14 para los amigos :-)


La solución correspondiente está en el programa como prueba_14, y mejora tanto el número medio de disparos (muy ligeramente respecto a las de incremento fijo, hasta 10,37) como el número máximo de disparos (en mucho, ya que disminuye a 14). En este privilegiado grupo se encuentran gente como Suso, Argus, Raúl, Alberto y el propio Jose. ¡Pero hay más!

Sin embargo, como dice Jose, es también posible usar 13 en vez de 14, y de hecho varios de los finalistas habéis “retocado” los números muy ligeramente, de modo que en esos casos he incluido cada algoritmo con nombre, uno para cada uno y otro para el ganador.

Con estos “retoques” el número máximo de disparos no cambia, pero el número medio disminuye dos centésimas, de modo que entre estas soluciones debía estar el ganador. Elegir ha sido muy difícil, y creo que todos los que habéis llegado a esta solución óptima –salvo que alguien salga ahora con otra aún mejor– merecéis que os hagamos la ola: Octavio, Alejandro, Eduardo y Enrique son los finalistas de este desafío.

Como digo, ha sido muy complicado elegir. Al final lo he hecho porque, tras leer las explicaciones, la que me ha parecido más entretenida, clara y “de encendido de bombilla” ha sido la del ganador; desde luego, es posible que a otros su explicación no resulte igual de clara, pero a mí me ha encantado leerla. Os dejo con la solución completa de nuestro ganador de esta vez, Mmonchi, loado sea su nombre, que además da las soluciones a las otras dos preguntas –infinitos cristales y límite arbitrario de resistencia–:


Antes de analizar lo que puede hacer Tooseb con dos cristales analicemos lo que puede hacer con uno solo, y de ahí podremos sacar conclusiones útiles. El cristal puede resistir un rayo de potencia entre 0 y 100, y nuestro pato puede disparar un rayo de potencia entre 1 y 100. Sí, podría disparar un rayo de potencia 0, pero ¿para qué? Vamos a representar en una gráfica la potencia del disparo, P -en el eje de ordenadas- frente a la resistencia del cristal, R -en el eje de abscisas. Un punto rojo indica que el cristal se rompe o lo que es lo mismo, que P>R, y uno negro que no se rompe.

Mmochi

Si representamos todos los puntos posibles obtenemos un triángulo rojo y uno negro:

Mmochi

En esta situación, con un solo cristal, Tooseb tiene una opción: empezar con la mínima potencia haciendo un disparo con el rayo en 1 e irla aumentando hasta que se rompa el cristal. Eso significa que si la resistencia es, digamos, menor que 7, deberá hacer siete disparos con potencia 1, 2, 3, 4, 5, 6 y 7. Los seis primeros los resistirá y con el séptimo se romperá. La gráfica de sus intentos en función de la resistencia del cristal es la siguiente:

Mmochi

Pero esto es muy poco eficiente, por eso le han dado dos cristales. Para resolverlo debe dividir el problema. Por ejemplo, si dispara un rayo con la mitad de la potencia a estudiar, en este caso entre 0 y 100 con potencia 50, obtiene lo siguiente:

Mmochi

En los casos en los que el cristal se rompe, únicamente le queda la opción ya vista para el caso en el que solo tenía un cristal, pero si no se rompe puede repetir el proceso en la mitad que le queda haciendo lo mismo, disparando un rayo con la mitad de la potencia a estudiar, en este caso 75:

Mmochi

Sigue haciendo lo mismo hasta que averigua la resistencia del cristal. El diagrama que indica la estrategia en cada caso es el siguiente:

Mmochi

Pero, si hemos mejorado la solución haciendo un disparo cuya potencia sea la mitad del intervalo, podemos tratar de mejorarlo aún más. Si la potencia es un tercio del intervalo el diagrama queda así:

Mmochi

Es fácil ver que este sistema es mejor que el anterior, pues cada punto representa un disparo y el número de puntos coloreados es visiblemente inferior. Y si con un tercio del intervalo mejoramos la solución, aún la mejoraremos más con un cuarto, un quinto, un sexto… ¿Hasta cuándo? Hasta el infinito. Para conseguir la solución óptima nuestro pato debe limitarse a hacer disparos cuya potencia sea un infinitesimal del intervalo de potencias que le queda por probar.

¡Eh! ¡Un momento! ¿Cómo se hace un disparo con potencia de un infinitesimal de 100? Además la clasificación de la resistencia de los cristales no es continua, toma valores “enteros” entre 0 y 100. A nadie le interesa saber si el cristal resiste un rayo de 23,12 o 23,84, solo si resiste 23 o 24. Y para calcular el valor “exacto” de lo que resiste el cristal haría falta un número infinito de disparos, algo que Bootes, Gal. Inc. todavía no está dispuesta a pagar.

Así que Tooseb tiene que adaptar su estrategia a un problema discreto, no continuo. Pero algo ha aprendido del análisis anterior: que los intervalos de potencia a estudiar deben ser decrecientes, de modo que cuando el primer cristal se rompa no deba hacer demasiados disparos al segundo. Para que la suma de ambos números de disparos no varíe (los que hace al primer cristal hasta que se rompe y los que debe hacer como máximo al segundo) el número de potencias del rayo posibles entre un disparo y el siguiente debe ir disminuyendo de uno en uno, ya que el número de disparos realizados va aumentando también de uno en uno. Es decir, la altura de los triángulos que veíamos en la gráfica debe seguir una secuencia 1, 2, 3,… k, donde k es el número de disparos máximo que se pueden hacer sin que se rompa el primer cristal pero también es la potencia a la que se hace el primer disparo.

Una vez entendido lo anterior el pato tiene un método para averiguar la resistencia del cristal al mínimo coste. Calcula k sabiendo que 1+2+3+…+k=n (n es la resistencia máxima) y hace el primer disparo con potencia k. Si el cristal se rompe hace disparos con potencia 1, 2, 3,… hasta que se rompe el segundo cristal y ya sabe su resistencia. Si en cambio el primer cristal no se rompe, hace el segundo disparo con potencia k+(k-1) y repite el proceso hasta que encuentra la respuesta.

Pero esta solución todavía presenta un problema: los números del tipo 1+2+3+…+k no son todos los números, solo los números triangulares cumplen esa propiedad. 91 y 105 son triangulares y nos darían valores de 13 y 14 para k, pero 100 no lo es. ¿Qué hacemos en ese caso? Si resolvemos k en 1+2+3+…+k=n tenemos la ecuación de segundo grado k2+k-2n=0 cuya solución positiva es k=√(8n+1)/2 - ½, que en el caso de n=100 vale 13,651. Es fácil comprobar (bueno, quizás no tan fácil) que cuando k no es entero la media de disparos que se alcanza tomando k=[k] o k=[k+1] es la misma, por lo que no importa elegir un valor u otro.

¿Qué hará Tooseb para averiguar la resistencia de su cristal, que está entre 0 y 100? Primero calcular los valores de k: k1=[√(8100+1)/2 - ½]=13; para hallar k2 sustituye el 100 del primer intervalo por el 100-13=87 del segundo y la k obtenida se la suma a 13, obteniendo k2=[√(887+1)/2 - ½] + 13=25; de forma sucesiva obtiene los valores de las k: {13, 25, 36, 46, 55, 64, 72, 79, 85, 90, 94, 97, 99, 100}. Ahora empieza a hacer disparos con los valores de k hasta que el primer cristal se rompa con la potencia ki, lo que acotará el intervalo de resistencias posibles entre ki-1 y ki-1. A continuación hace los disparos con potencia ki-1+1, ki-1+2, ki-1+3 hasta romper el segundo cristal o llegar a ki-1 y ya sabe su resistencia.

El diagrama será el siguiente:

Mmochi

No hay que confundir este diagrama con los últimos: aquellos eran diagramas continuos, en los que las líneas y los puntos tenían un grosor despreciable, mientras que este es discreto y la gráfica tiene valores enteros.

Como sabemos que todos los valores de R entre 0 y 100 son igual de probables, sumamos el número de disparos en cada caso y dividimos el total entre los casos posibles, 101. El resultado nos da el número de disparos medio, 1045/101=10,3465. El máximo ya lo conocemos y es el valor de k redondeado hacia arriba, o sea 14.

Por ejemplo, si la resistencia máxima es 60 la secuencia de disparos será {13, 25, 36, 46, 55, 64, 56, 57, 58, 59, 60, 61} donde están indicados en negrita [modificado para mostrar en la web] los disparos que rompen el cristal. En la gráfica está destacado el caso P=60, cuyos puntos coinciden con los valores anteriores:

Mmochi

Por último, para un valor de n distinto de 100 se construye la lista de las ki del mismo modo que la anterior y se realiza el proceso.

¿Qué habría tenido que hacer Tooleb si hubiese dispuesto de todos los cristales que necesitara? En ese caso el problema se simplifica mucho, pues se reduce a irlo dividiendo en problemas menores y resolverlos. Es decir, se hace un disparo con la potencia media del intervalo en el que puede estar la resistencia del cristal, en su caso 50. Si se rompe estará entre 0 y 50, si no se rompe entre 51 y 100. Ahora se toma el valor medio del nuevo intervalo y se repite el proceso. Cuando un valor no da exacto se redondea, da igual hacia arriba que hacia abajo. Si en lugar de un intervalo 0-100 se tiene 0-n el proceso es exactamente igual.

En su caso el diagrama de los disparos que se deben hacer en función del valor de R es el siguiente:

Mmochi

Si la resistencia máxima del cristal fuera 60, como antes, la secuencia de disparos sería {50, 75, 63, 56, 59, 61, 60} averiguando el valor con siete disparos.

La suma de los disparos en todos los casos es 680, que al dividirlo entre todos los casos posibles da un promedio de 680/101=6,7327, inferior al del caso anterior, y el valor máximo es 7.

En general se puede decir que el máximo cuando hay dos cristales tiende a √(2n) y el promedio a √n, mientras que si no hay límite de cristales tanto el máximo como el promedio tienden a log2n.


Espero que os lo hayáis pasado al menos la mitad de bien que yo pensando en esto y leyendo lo que han pensado los demás y, como siempre, ¡hasta el próximo desafío!

Desafíos, Matemáticas

43 comentarios

De: Octavio
2012-10-08 22:40:14

En el programa disparos.py no se tiene en cuenta la posibilidad de que la resistencia sea
0 ,por eso la media es mayor que la que algunos hemos calculado (1044/101).¡Muy entretenido el problema!


De: Pedro
2012-10-08 22:42:33

Octavio, es que al corregir las soluciones se me olvidó que en el desafío se admitía 0 y no empezaba en 1... ¡oops! Ahora no tengo tiempo, pero mañana lo cambio para quien quiera jugar con él, ¡gracias! :)


De: Sergio Cinos
2012-10-09 07:26:23

Brillante lo de reducir el intervalo!!! Yo era de los que me quedé en mis 19 disparos y tan contento. Lo de que se admitía resistencia 0 no lo sabía, mi solución quedó un poco guarra al tener que empezar en 1 :). Muy buen problema, gracias por hacerme pasar un rato tan bueno.

Propongo como sub-problema el generalizarlo para X cristales, que es bastante más complejo que generalizarlo para N energía :)

PD: Voy a ponerme a hacer algo interactivo, cuando lo tenga te aviso


De: Sergio Cinos
2012-10-09 07:31:12

Por cierto, acabo de ver que muchas soluciones (al menos tal como están implementadas en el programa en python) son mejorables, ya que casi todas hacen un disparo a 99 y otro a 100. El último no es necesario, ya que si a 99 no se rompe, es que la resistencia es 100, no?


De: Pedro
2012-10-09 07:47:36

Corregido, las resistencias ya incluyen 0. El máximo de disparos no cambia para las soluciones ganadora y finalistas pero, como decía Octavio, las medias se reducen ligeramente. Cuando Sergio tenga algo lo colgamos y podéis jugar con ello para probar diferentes soluciones :)


De: alb.
2012-10-09 10:02:59

Con 14 disparos y 2 cristales se pueden obtener 106 niveles de resistenca diferentes.
Como solo necesitamos 101 niveles(contando el cero), nos sobran 5 niveles de resistencia.

El resultado optimo se obtiene al descontarlo de los 5 primeros intervalos.

De esta manera llego a 10,31


De: Alb.
2012-10-09 10:12:23

Hola Pedro.

Ayer, fuera de plazo, te envié una solución general al problema. Que permite determinar el numero máximo de disparos para cualquier numero de resistencias y de cristales.

¿Lo has visto?


De: Alb.
2012-10-09 10:15:54

Sergio Cinos
Si no se rompe a 99, significa que su resistencia es mayor que 99.
Puede ser 99 o 100
Necesitas hacer un disparo a 100, para poder saber si es 99 o es 100.


De: Sergio Cinos
2012-10-09 10:24:50

@Alb, Tienes toda la razón, fallo mio :)


De: Dani
2012-10-09 13:54:51

Espera porque a mi me surge una duda, ¿en algún momento del desafío se dice que la resistencia del cristal es continua?

Lo digo porque si es discreta, si no se rompe a 99, entonces tiene seguro que ser 100, ¿o estoy cometiendo algún fallo tonto del que luego me avergonzaré?

PS Estoy hablado de resistencia no de la potencia del rayo, me explico, entiendo que si un rayo de potencia 1 rompe el cristal, éste tiene resistencia 0; por lo que si el rayo de 100 rompe el cristal, tendría una resistencia de 99 y si lo resiste de 100. (en ambos casos se necesita tan solo un disparo)


De: Pedro
2012-10-09 21:03:03

Dani, la resistencia es discreta, no continua.

Lo digo porque si es discreta, si no se rompe a 99, entonces tiene seguro que ser 100, ¿o estoy cometiendo algún fallo tonto del que luego me avergonzaré?

Si el cristal no se rompe con un rayo de potencia 99 sigue habiendo dos posibilidades: que la resistencia sea 99 o que sea 100. Por tanto, sigue haciendo falta otro disparo más.


De: maltes
2012-10-09 21:32:15

Quería participar en este desafío, pero no tuve tiempo, pero os lanzo una idea.
La idea es hacer un primer disparo de potencia tres, si el cristal se rompe, pues nada, se coge el otro y a probar con 1 y si se salva con potencia 2, nada nuevo ¿no?. Lo nuevo viene ahora, nuestro pato, coloca los dos cristales seguidos y dispara a los dos con potencia 6 si el primero se rompe tiene que probar el segundo con 4 y 5, sino prueba con 11 luego con 19, 26 …, lo difícil aquí y lo que no tengo tiempo de hacer, y a lo mejor tampoco habilidad, es calcular los incrementos óptimos, pero creo que partiendo del truco de poner los dos cristales seguidos se podría mejorar la solución.


De: Dani
2012-10-10 01:17:18

Ok Pedro, entiendo lo que dices y no quiero haceros perder mucho tiempo, pero sigo sin entender una cosa.

Si disparo un rayo de 1 y el cristal se rompe, tendrá resistencia 0. Si un rayo de 60 rompe el cristal (suponiendo que has probado las anteriores) tendrá 59 de resistencia. Por lo tanto, si disparo un rayo de 100 y se rompe, tendrá 99 de resistencia, si no se rompe, tendrá 100 (porque habrá resistido todos los rayos). ¿Supone esto alguna diferencia en los cálculos?


De: Sergio Cinos
2012-10-10 06:11:52

@Dani, es como tu lo expones, pero no hay ningún cambio, de hecho es como funcionan todos los disparos. Si disparo a X y el cristal no se rompe, entonces resistencia>=X. Si el cristal se rompe, resistencia<X. Si antes ya he disparado con todas las potencias de 1 a X-1 (y no se ha roto), entonces la resistencia del cristal es X-1.

Si el problema fuera "... el cristal se rompe entre 1 y 100" y ya hemos disparado de 1 hasta 99 sin que se rompa, entonces no hay que hacer mas pruebas, el cristal se rompe en 100 (puesto que es el único número que queda sin probar). Pero el problema es "... el cristal resiste entre 1 y 100". Aunque hayas disparado de 1 a 99 sin que se rompa, todavía tienes que hacer un último tiro a 100 para ver si el cristal resiste 99 o resiste 100, tal como dice Pedro.


De: Argus
2012-10-10 10:22:38

Creo que Dani, y corrígeme si no es así, se refiere a la singularidad del 100, ya que no hay posibilidad de tener un cristal de resistencia mayor. Esto influye en el cálculo de la media a la baja porque te ahorras un disparo: Para detectar un cristal de resistencia 99 se necesitan los mismos disparos que para detectar un cristal de resistencia 100. Esto no sucede con cristales de resistencia distinta a 100.


De: Dani
2012-10-10 13:23:12

Muchas gracias a los dos, ¡creo que habéis explicado lo que quería decir mejor que yo! Qué difícil es escribir a veces lo que uno piensa para que lo entiendan los demás...


De: Alburton
2012-10-10 14:32:07

Muchas gracias Pedro!
Por favor sube más desafíos matemáticos porque son de lo mejorcito de la página!


De: Enrique
2012-10-10 16:34:02

Muy buenas,

Pedro, en el programa en python para comprobar las soluciones hay que poner r=101 (en lugar de r=100, que está ahora mismo) para que se prueben los 101 casos posibles de resistencia, desde 0 hasta 100 ambos incluidos. De esta manera resulta que todas las soluciones finalistas y ganadoras dan el mismo resultado, el 10,3465 de la solución (hay una errata, en el texto pone 10,4365).

De todas formas, parece que todavía queda una pregunta abierta; yo no lo supe hacer en mi solución y entiendo que ningún otro tampoco. El que una solución proporcione el menor número máximo de disparos no implica que proporcione el menor número promedio; y la inversa tampoco es cierta, el que el número de disparos medios sea mínimo no implica que el número sea máximo. O, al menos, no está demostrado. Por ejemplo, en teoría de grafos se sabe que un grafo puede tener distancia media menor que otro, pero con menor diámetro, y viceversa.

Lo que quiero decir es que en la solución de Mmonchi (muy buena, ojo, no se entienda como crítica ni falta de deportividad) se busca el valor k que minimiza el número máximo de disparos. Si el número de cristales restantes es un número triangular, k es el único salto que permite minimizar el número máximo de disparos; circunstancialmente, resulta que dicho salto también minimiza el número medio de disparos (pero habría que demostrarlo).

En cambio, si el número de saltos restantes no es triangular, entonces para minimizar el número máximo de disparos nos vale cualquier valor que nos acerque a la secuencia formada por números triangulares. Por ejemplo, la secuencia {9, 22, 34, 45, 55, 64, 72, 29, 85, 90, 94, 97, 99, 100} minimiza el número máximo de disparos, pero no el número promedio. En concreto, para minimizar el número medio de disparos tenemos que hacer saltos k o k+1 (empezando en 13 o 14, no en 9, por ejemplo), y mi pregunta es ¿por qué? Yo había llegado a ese resultado haciendo una búsqueda exhaustiva con el ordenador, pero estaría bien demostrar que dicha condición es necesaria (y suficiente) para minimizar el número medio de disparos.

¿Alguna idea?


De: Pedro
2012-10-10 17:18:26

@Enrique, corregidas ambas, gracias :)

@Todos, acabo de subir el html que me ha pasado Sergio para poder simular cualquier solución (las finalistas/ganadora y cualquier solución propia que quieras introducir para probar), es muy fácil de usar y espero que lo paséis bien jugando un rato con ella si queréis probar otras soluciones. ¡Gracias, Sergio! El archivo está en http://eltamiz.com/files/disparos.html.


De: Alb.
2012-10-10 19:30:52

Argus... Para determinar una resistencia n se necesitan dos disparos, de ponencias n y n+1.
El cristal resiste el disparo a pontencia n y se rompe a potencia n+1.

Sin embargo hay dos excepciones, en los dos puntos extremos(o y 100) solo se necesita 1 disparo.

Si no resiste el disparo a potencia 1, su resistencia es cero
Si resiste el disparo a 100, su resistencia es 100.

Pero estas excepciones, no cambia el hecho de que para obtener el numero mínimo de disparos, se deba ensayar la secuencia (13, 25, 36, 46, 55, 64, 72, 79, 85, 90, 94, 97, 99, 100)

Se va disparando sobre el primer cristal hasta que se rompa. Si se dispara en 97 y sigue sin romperse... entonces solo quedan 4 posibilidades... que resista 97, 98, 99 ó 100.

Para determinar el valor exacto hay que hacer 2 disparos mas. Se dispara sobre 99, si se rompe la resistencia sera 97 ó 98. Si no se rompe sera 99 ó 100.

En ambos casos se necesita un disparo mas para determinar el valor exacto.

Aunque resulte algo chocante y contraintuitivo que en la secuencia optima de disparos haya dos disparos de potencias contiguas en el extremo, asi son las cosas.


De: Jose
2012-10-10 19:59:06

Enrique,
el martes por la tarde envié a Pedro una solución en la que los valores de los saltos vienen determinados por la minimización del número esperado de de disparos. Me parece que esa solución sería óptima (si no me he equivocado) siempre que se siga el esquema de dos niveles que hemos usado todos.

Para la tranquilidad de todos diré que el número promedio de disparos es el mismo que han obtenido todos los finalistas, así que todos hemos encontrado la solución ¿optima? por diversos métodos.

Supongo que a Pedro aún le ha dado tiempo a digerirla...


De: Pedro
2012-10-10 20:48:38

Jose, está siendo una semana horrible, y seguramente lo seguirá siendo: a lo más que llegaré será a subirla y enlazarla para que la gente pueda leerla :)


De: Sergio Cinos
2012-10-10 22:05:25

Yo sigo dandole vueltas a generalizar la solución para M cristales. Creo que tengo una generalización si se usa un intervalo fijo de saltos:

En general, el número de "pasadas" es igual al número de cristales. En el caso de dos cristales, primero hacíamos una pasada con salto=10 (caso fijo) y una segunda pasada con salto=1. En el caso de M cristales, el salto que debemos dejar según la pasada que estemos realizando es (raiz M-ésima(N))^(M-p) siendo N la energía máxima, y p el número de pasada (eg: p=1 para la primera pasada con el primer cristal, p=2 para la segunda...) En el ejemplo del desafío: N=100 y M=2, lo cual nos da los valores 10 (p=1) y 1 (p=2). Si tenemos 3 cristales y una energía de 1 a 125, haremos una primera pasada saltando 25, una segunda saltando 5 y una última secuencial (saltando 1).

Creo que es correcto (aunque no estoy muy seguro ni se como demostrarlo), pero no se hacerlo para saltos variables :(


De: Alb.
2012-10-10 22:42:34

Sergio Cinos
He encontrado unas sencilla solución para el caso general en funcion del numero de cristales y del numero de niveles de potencia.

La he colgado aqui, si te interesa:

https://dl.dropbox.com/u/48024270/desafio%202.pdf


De: Octavio
2012-10-10 23:35:42

En respuesta a Enrique:
Yo creo que descontando el método de la fuerza bruta,los otros métodos sirven como
demostración,yo use un árbol binario en el que cada nodo representa la potencia de un disparo y según el resultado se sigue por la izquierda si se rompe o por la derecha
si no se rompe,el numero máximo de disparos depende del numero de niveles del árbol,y el numero promedio dependerá de la altura de los nodos en el árbol,de modo que si el árbol esta nivelado ,la solución no se puede mejorar,por que no se puede mover ningún nodo del ultimo nivel a un nivel inferior.El ultimo nivel del árbol puede estar incompleto ,y en este nivel se pueden cambiar los nodos de sitio sin que eso afecte al numero medio de disparos,por eso hay varias posibles soluciones,tantas como distribuir 9 nodos entre 14 posiciones posibles.
Aunque el árbol es binario ,en cada nivel solo se bifurca el nodo de mas a la derecha porque solo hay dos cristales,si hubiese mas cristales ,el árbol tendría mas bifurcaciones (mas ancho) y menos niveles,así que harían falta menos pruebas.


De: Jose el albañil
2012-10-11 00:57:47

Joer, yo que soy albañil y no he ido a la escuela como vosotros he encontrado la solución en 5 segundos.
Se requiere saber qué metodo es mejor para descubrir cual es la dureza del cristal ¿no? Vamos, producir los menores disparos posibles en una escala del 1 al 100 con únicamente dos cristales. Es decir, los disparos del disruptor tienen un nivel de potencia del 1 al 100 y solo tenemos 2 cristales y hay que averiguar la secuencia de los niveles intentándonos aproximar al nivel más cercano que pueda soportar el cristal.

Después de pensar mi respuesta he leído cual sería la solución más óptima y no me he enterado de nada con tanta fórmula, pero viene a decir que es 50, 75, 63, 56, 59, 61, 60.

Pues es mucho más sencillo hacer con un cristal un disparo a 50. Luego a 75, luego a 62, luego a 56, luego a 53 y luego a 51. Como tenemos dos comodines que son los cristales sabremos por si se rompe uno que es 51 ó 52.

Veamos, vuestra solución: 50, 75, 63, 56, 59, 61, 60.

Mi respuesta: 50, 75, 62, 56, 53 y 51.

La mía tiene menor número de intentos. Bueno, aunque en la solución viene 61,60, yo debería incluir 51 y 52, ó 52, 51 si probamos primero el 52. Pero yo he tardado 5 segundos en hacerlo mentalmente, mientras que en la solución de Pedro habrán invertido horas en sacarla.

Mi procedimiento ha sido bien sencillo, como mi nivel de estudios. He cogido el 50% de probabilidades y a partir de ahí he ido dividiendo por dos las probabilidades que quedaban.


De: Jose el albañil
2012-10-11 01:55:42

Perdón, está mal mi sistema porque un cristal se rompería a 75. Pero no le quitaría validez al método por probabilidades que explico. Pedro ya dice arriba que uno de los sistemas sería probar primero con 50, y luego ir dividiendo entre 2 las probabilidades, pero luego dice que el más fiable es el de incrementos por 10, lo que me parece incorrecto.

En el peor de los casos:
Mi método sería probar a 50, si se rompe: a 25, si se rompe tenemos un resultado de 1 a 25
El otro método dice que se pruebe a incrementos de 10. Si se rompe a 10, probar a 20, y tendríamos un resultado de 21 a 100. Aunque se comenzase en cualquier cifra el resultado siempre sería mayor que el 1 a 25 mio. Por ejemplo probar 90 y luego 80: resultado 79 que es mayor que 25. Por poner otro ejemplo; probar a 50 y luego 40, resultado: 1 a 39. Podemos probar a 20 y luego 10, pero ojo, que estamos hablando de probabilidades, y lo más seguro es ir al 50%, como en el truco de la martingala. (no sé si lo conocereis)

En el mejor de los casos:
Mi método a 50: si no se rompe, a 75; si no se rompe, a 88; si no se rompe, a 94, si no se rompe, a 97; si no se rompe, a 99. Y acertamos.
El de incrementos de 10: si no se rompe, a 20; si no se rompe, a 30, hasta 100 y acertamos.

No se si me explico bien, pero la respuesta mas acertada sería la de probabilidades por 50 %, es decir: el truco de la martingala.


De: Jose el albañil
2012-10-11 01:58:36

No me salen los comentarios publicados donde explicaba la solución, pero para acortar diré que el sistema más fácil es el de probabilidades por 50% e ir reduciendo. Lo que se conoce como el truco de la martingala en el juego.


De: Jose el albañil
2012-10-11 02:13:44

Por otro lado, mi sistema tendría el mismo número de disparos que el mejor que por aquí se ha dicho: siete disparos. Pero no hace falta pensarlo tanto.


De: J
2012-10-11 08:56:23

Yo no pasé de la solución de tipo 2, pero al leer las de tipo 3 se me ocurre una explicación que, cualitativamente, pueda ayudar a alguien a verlo. La cuento.

Supongamos que la solución de tipo 2 es correcta, y para N=100 resistencias posibles, tenemos que A=sqrt(N)=sqrt(100)=10.

So far, so good.

Entonces disparamos el primer rayo con potencia 10 y supongamos que no se rompe. Podríamos ahora seguir aplicando el algoritmo y disparar con potencia 20... pero... un momento: si ya hemos disparado hasta 10, estamos ante un nuevo problema que podemos reevaluar: tenemos un cristal que de resistencia entre 11 y 100.

Es decir, es un nuevo problema, igual que el anterior, pero en vez de con 100 posibles valores, con 90 posibles valores. ¿Por qué no lo atacamos otra vez desde el principio? Como tenemos 90 posibles valores, el valor de A óptimo sería A=sqrt(N)=sqrt(90)=9,48=9. Así que disparamos con potencia 19.

Si no se rompe, idéntico razonamiento podemos realizar ahora: tenemos entre 20 y 100. 81 posibles valores. Debemos disparar con incremento A=sqrt(81)=9 (bueno, este caso es un poco especial, porque por culpa del redondeo sale lo mismo, pero se ve la idea, ¿no?), es decir, con 28. Y así sucesivamente.

Es decir, hemos convertido el problema "recursivo" en un problema "iterativo" o "de inducción". El único problema que queda es obtener el incremento inicial. Seguro que alguien con más neuronas que yo puede resolverlo planteando la ecuación iterativa y luego resolviéndola, pero como yo soy muy cazurro, lo haría por fuerza bruta.

Ojo, que esto no se me hubiera ocurrido sin conocer previamente las soluciones de los ganadores. Creo únicamente que una forma más sencilla de que se le encienda la bombilla a alguien que no termine de entender los gráficos de Mmonchi et al.


De: Pedro
2012-10-11 11:54:12

Jose, creo que no has entendido el resto de soluciones, efectivamente. La tuya no es la mejor ni de lejos, como puedes comprobar si la pones en el simulador que ha hecho Sergio. Sí que hace falta pensarlo bastante :)

J, tu explicación me parece magistral... de encendido de bombilla total, al menos para mí :)


De: Mmonchi
2012-10-11 14:19:17

Hola a todos. Pedro, gracias por elegir mi solución, aunque estoy seguro de que cualquiera de las demás también lo hubiera merecido. He tratado de imitar un poco tu estilo, pero eso de ser claro y ameno a la vez es mucho más difícil de lo que parece, solo lo tenéis al alcance unos pocos elegidos (tú, Asimov y alguno más ;-) ).

Estoy analizando cómo resolver el caso de N cristales de forma sencilla, cuando compruebe que da la solución óptima lo subo.

Saludos.


De: Dani
2012-10-11 14:36:55

Jose, sí que hace falta pensarlo un rato. De hecho a los cinco segundos de leer tu método, he visto un error que habría hecho que te despidieran de Bootes a la primera.

El problema de tu método, es que funciona mucho mejor si la resistencia es de más de 50 que si es de menos. Por ejemplo tu dices:

En el peor de los casos: Mi método sería probar a 50, si se rompe: a 25, si se rompe tenemos un resultado de 1 a 25

¡Pero solo tienes dos cristales! ¡ Y ya has roto los dos ! Y sigues sin saber cuál es la resistencia del cristal, porque dudo mucho que le valga a la empresa que le digas que la resistencia está entre 0 y 25...Ese es el problema de tu método -que por cierto, comenta Pedro en el artículo-, que si el cristal se rompe con un disparo de 50 (y esto pasará un 50% de las veces), no tienes más opción que ir probando desde el 1 hasta el 49.

Es decir, en tú método, si la resistencia es de 49, harías un primer disparo a 50, se rompe, coges el segundo cristal y empiezas a probar desde el 1, luego el 2, etc. ¡ Habrías tardado 50 disparos en llegar a la solución !

El otro fallo de tu argumento es cómo valorar las distintas soluciones. No parece muy justo que compares el mejor de tus casos (99) con el peor del otro (99 también). Además no estás valorando el tercer tipo de solución que es la de incremento variable (en vez de ir de 10 en 10, empezamos con 14 y vamos reduciendo el intervalo). Lo más lógico sería decir: -vamos a probar toooodas las posibilidades y vamos a apuntar cuánto tarda cada solución en llegar a la resistencia-. Empezamos, si el cristal tuviera resistencia 1, ¿cuánto tarda el método que sea, en encontrar la solución? Seguimos con el 2, el 3, y así hasta el 100. Una vez que tengamos todos, hacemos la media y averiguamos cuál sería el mejor método, estadísticamente hablando.

Así que me parece que sí había que pensarlo un poco.


De: Alb.
2012-10-11 19:55:22

Mmonchi

Aun a riesgo de ser pesado, dire que ya encontre la solucion general para c cristales y n numero de resistencias

Es una expresion soprendentemente sencilla.

Lo explico a en este pdf.

https://dl.dropbox.com/u/48024270/desafio%202.pdf


De: Mmonchi
2012-10-11 20:17:37

Alb., he visto tu solución pero no acabo de entender de dónde salen las potencias que se ensayan en cada caso. Tu resultado para C=2 coincide con el mío, y tu manera de representarlo es mucho más comprensible que mi gráfico.

Tengo un algoritmo relativamente sencillo para determinar la potencia a utilizar en función de tres parámetros: la mínima potencia que resiste (0 al principio), la máxima que puede resistir (100 al principio) y el número de disparos de que dispone. Me falta refinarlo porque en algunos casos no da el resultado óptimo (concretamente, cuando el número de cristales es relativamente grande).

Si has calculado la probabilidad para el caso con C=3, el resultado que obtengo es 757/101. Puedes comprobar si te da el mismo valor o no.


De: Lemur
2012-10-12 04:50:18

Hay un problema, que considero equivalente:
http://uva.onlinejudge.org/external/118/11843.pdf
Tomando N como el número de resistencia máxima del cristal y S - 1 como las placas que nos dan. Ese problema, lo resolví usando programación dinámica.


De: Jose M
2012-10-13 10:01:46

Hola,
acabo de leer el problema y me surgr una duda ¿porqué solo 2 cristales?, si el área del mismo no influye de forma directa en su resistencia... creo que el problema es de los ingenieros.... con mas cristales de menor tamaño (aunque es cierto que este no se indica) la mejor aproximación para el ahorro energético en los disparos sería una búsqueda dicotómica ... siempre y cuando el proceso de generación de cristales de menor tamaño no consumiese más recursos base que la generación del rayo, claro....

Saludos!!!
P.D. Lo digo en tono jocoso!, porque he llegado tarde.... he disfrutado cada una de las aportaciones!!!!


De: octavio
2012-10-13 15:43:29

Con mi metodo para c=3 obtengo 860/101.
Mmonchi,me gustaria saber como haces para obtener 757/101


De: Mmonchi
2012-10-14 22:25:42

Octavio, he conseguido 754/101 con la siguiente secuencia de disparos: {29,51,67,78,89,96,99,100}. A partir de estos datos solo necesitas la secuencia para c=2 en cada caso, que sigue el sistema ya visto.

No estoy consiguiendo generalizar las secuencias para otros valores de c. El texto de Alb me parece la mejor opción, pero no consigo transformarlo en algo sencillo.


De: Mmonchi
2012-10-14 23:57:27

Lo he hecho con el método de Alb y la secuencia es {29,51,67,78,86,93,97,99,100} con el mismo resultado: 754/101.


De: octavio
2012-10-15 17:07:30

Mmonchi, me equivoque ,tus numeros son correctos.Yo tampoco encuentro una formula generica,y si la hay ,no creo que sea sencilla,dado que hay muchas posibles soluciones.
Mi metodo del arbol sigue funcionando,pero requiere dibujarlo y contar nodos o hacerlo con un programa.
El problema habria sido mucho mas dificil con ,por ejemplo c=20 y n=1 trillón :)


De: Mmonchi
2012-10-15 19:18:35

Tengo ya un método relativamente sencillo para hacer los disparos. Se parte de tres datos: la resistencia mínima del cristal, n, que en nuestro caso era 0; la resistencia máxima del cristal, m, que en nuestro caso era 100; y el número máximo de disparos, d. Se calcula el valor de f(m-n,d) y se obtiene la potencia a la que se debe hacer el siguiente disparo, que es f(m-n,d)+m.

Por ejemplo, con n=0, m=100 y d=2 hallamos que f(100,2) vale 13, así que el primer disparo se hace con potencia 13. Si se rompe tenemos que n=0, m=12 y d=1 y hallamos que f(12,1) vale 1, que sería el siguiente disparo. En cambio si no se rompe tenemos que n=13, m=100 y d=2, y como f(87,2)=12, la potencia del siguiente disparo será f(87,2)+12=25.

Teniendo la tabla m-n/d se puede resolver cualquier caso de forma inmediata.

El número de disparos es 1045/101 para 2 cristales, 754/101 para 3, 690/101 para 4, 681/101 para 5 y 680/101 para 6 o más cristales.

No sé como subir un documento con la tabla y la forma de hacerla, que se basa en el método que explicó Alb. en su documento.


De: Mmonchi
2012-10-15 19:45:42

Octavio, para c=20 y n=1.000.000.000.000.000.000 la potencia del primer disparo es 239.058.748.663.208.600. :-)


Escribe un comentario

Todos los comentarios deben ser aprobados por un moderador antes de ser publicados. Si quieres puedes usar markdown. Todos los campos son opcionales excepto el cuerpo del comentario, claro:

Nombre:
E-mail: (privado, para que aparezca tu gravatar)
Sitio web:

« Desafíos - Los cristales blindados de Bootes Los tipos espectrales [2/10], en vídeo »