Solución al problema de la bola de cristal
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.
Comentarios a través del feed: RSS 2.0
Dirección de trackback.
3 comentarios
Yo también lo encaré así. Aunque no hice la sumatoria explicita sino que use lo de 1 + 2 +... N = N(N+1)/2, etc.
Una observación: esta solución es la óptima sólo según cierto criterio: es la que mejor acota la cantidad máxima de intentos (peor caso). Queda abierto, me parece, cuál es la estrategia óptima si, por ejemplo, queremos minimizar la cantidad esperada de intentos (para lo cual habría que postular un probabilidad a priori). Lo voy a pensar.
Hola hernan. Efectivamente es la óptima en ese sentido, pero es que precisamente el enunciado dice
¿Cuántas comprobaciones son necesarias hacer para descubrirlo?
Y la respuesta es que con 15 seguro que puedes, para hacerlo en menos de 15 ya tienes que tener suerte.
Y sí, tu pregunta también es interesante, sería calcular la esperanza de la distribución que consideremos. Habría que estudiar para cada piso la cantidad necesaria de intentos con esta estrategia, sumarlos, sumar también la cantidad necesaria si la bola no se rompe nunca y dividirlo entre 118 (ya que son 118 casos incluido el que no se rompa). En nuestro caso vamos a ver lo que da:
-Si se rompiera desde el primer piso haría falta 2 comprobaciones.
-Si se rompiera en el piso 2, 3 comprobaciones.
-En el 3, 4 comprobaciones.
....
-En el 14, 15 comprobaciones.
-En el 15, 15 comprobaciones.
-En el 16, 3 comprobaciones.
-En el 17, 4 comprobaciones.
...
-En el 28, 15 comprobaciones.
-En el 29, 15 comprobaciones.
-En el 30, 4 comprobaciones.
...
-En el 41, 15 comprobaciones.
-En el 42, 15 comprobaciones.
Creo que se va viendo lo que va saliendo, para los primeros 15 pisos.
2+3+4+5+6+7+8+9+...+14+15+15
En los 14 siguientes (del 16 al 29)
3+4+5+6+7+8+9+...+14+15+15
En los 13 siguientes (del 30 al 42)
4+5+6+7+8+9+...+14+15+15
Y seguimos así (primero 15 pisos, luego 14, luego 13...., cuando añadamos 3 habremos llegado a 117 ya que 3+4+5+...+15=117).
En los 3 últimos, 14+15+15.
Sumemos todo lo que nos sale. Un truco para sumarlo sería añadirle la suma
1+2+3+4+...+14 (=105)
El 1 sale 1 vez, el 2 sale 2 veces, el 3 3 veces, el 4 sale 4 veces,..., el 14 sale 14 veces y el 15 sale 26 veces.
Por un lado
que para n=14 sale 1015. Si le añadimos 15x26 nos da 1405. Ahora le restamos la suma 1+2+3+...+14 que le habíamos añadido y nos queda 1300.
Nos falta sumar el caso en el que la bola no se rompa desde ningún piso, para este nos hacen falta 13 comprobaciones así que la suma total será 1313.
Dividimos esto entre 118 y nos queda
1313/118
que aproximadamente vale
11,1271
Lo he ido haciendo conforme escribía así que no descarto haberme equivocado en alguna cuenta. ¿Se puede encontrar una estrategia que mejore esto? Pues sí, una pequeña variación de la que hemos puesto valdría (es fácil bajar el número de comprobaciones para los últimos pisos). ¿Cuál sería el óptimo? Habría que pensarlo, claro.
Informaci�n de BlogESfera.com......
Puedes valorar este post en BlogESfera.com haciendo click aqui....