Hace unos meses propuse el problema de la bola de cristal casi irrompible. Resumiendo el problema consistía en esto:
Se disponen de 2 bolas de cristal y se quiere saber a partir de que piso de un edificio de 117 plantas se rompen. ¿Cuántas comprobaciones son necesarias hacer para descubrirlo? Aclaro que como solo disponemos de 2 bolas, cuando se rompa la segunda no podremos hacer más comprobaciones.
Para ver un enunciado más largo y bonito id a la entrada original.
Bien, voy a razonaros como llegar a la solución. Lo primero es observar que cuando nos quede una sola bola, lo único que podemos hacer es ir probando desde un piso superor al mayor desde el que sabemos que no se romperá ya que si por ejemplo supiésemos que no se rompe en el 54 y la tiramos y se nos rompe la última bola en el 56, no podremos saber si en el 55 se rompería o no.
Por lo tanto, si la primera comprobación se hace a altura n y se nos rompe la bola, como tendremos que ir probando desde el piso 1 hasta quizá el n-1 es posible que necesitemos n comprobaciones. Así que si nos bastara con n comprobaciones, está claro que la primera como mucho podrá ser en el piso n.
Ahora bien, tras la primera comprobación, suponiendo que la bola no se nos ha roto (ya que si se rompe tendríamos que probar desde más abajo), usando el mismo razonamiento del párrafo anterior, dado que nos quedan n-1 comprobaciones, podríamos subir como mucho n-1 pisos más así que la segunda comprobación se haría en el piso n+(n-1) o en un piso más bajo.
Si seguimos razonando igual, la tercera comprobación se debería de hacer en el piso n+(n-1)+(n-2) o uno inferior, la cuarta en el n+(n-1)+(n-2)+(n-3), la quinta…
Con esto en mente es fácil sacar ya la solución. Está claro que con 14 no podemos asegurar que podamos lograrlo ya que si resultase que la bola no se rompiese en ningún intento, llegaríamos como mucho al piso
14+13+12+11+10+9+8+7+6+5+4+3+2+1=105<117
así que necesitaríamos más intentos. Sin embargo con 15 sí que podremos ya que
15+14+13+12+11+10+9+8+7+6+5+4+3+2+1=120>117.
La estrategia sería:
-Probamos en el 15, si se rompe probamos en el 1, 2, 3, 4… hasta que se rompa.
-Si no se rompe en el 15, en el segundo intento probamos en el 15+14=29. Si se rompe ahora vamos probando en el 16, 17,…,28 (13 pisos) o hasta que se rompa.
-Si no se rompe en el 29, probamos en el 29+13=42…
Y así seguiríamos. Está claro que de esta forma encontraríamos el piso en a lo sumo 15 intentos.
"
No hay comentarios:
Publicar un comentario