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 https://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.

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

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:

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:

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:

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

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í:

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:

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:

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:

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!