Los acertijos que suelo poner no requieren grandes conocimientos de matematicas ( entre otras cosas por que el moderador de la pagina no los tiene), normalmente suele bastar con las operaciones basicas , y eso sí , aplicar bien la logica y el sentido común.
El siguiente problema me gusta mucho; no es sencillo y creo que puede resolverse con la ayuda de una hoja de calculo si diseñamos bien la formula adecuada ( yo no sé) , pero tambien puede resolverse de una forma mas sencilla. Quizá no se pueda demostrar matematicamente , pero si alguien consigue un resultado mejor deberá probarlo.
El problema dice así:
Tenemos un edificio de mil plantas de altura ( es imaginario , claro) y disponemos de un tipo de bombilla que si la dejamos caer desde la planta N , se rompe , y logicamente desde todas las plantas superiores a la N , pero no se rompe si la dejamos caer desde las plantas inferiores a N.
La bombilla es solo un accesorio para plantear el problema , es decir , no podemos adivinar nada por su aspecto; igual puede romperse desde el piso 1 o necesitar llegar al 1000 , y tampoco hay ningun otro factor ( forma de lanzar , cómo se rompe, etc...) que influya , es solo un problema matematico de optimizacion de estrategia.
Podemos lanzar la bombilla tantas veces como queramos.
Si solo disponemos de una bombilla , solo se puede seguir una estrategia , empezar desde el piso 1 e ir subiendo piso a piso hasta que se rompa.En el peor de los casos , llegariamos al piso 999, si no se ha roto , por definicion del enunciado , tiene que romperse en el 1000. Esto nos da que habriamos necesitado 999 lanzamientos. Logicamente ,se puede ( se deberia , probablemente) romper antes , pero vamos a situarnos en el peor escenario posible.
No hay otra estrategia que nos permita realizar menos lanzamientos, pues si empezamos por un piso distinto del 1 , y se rompiera , no sabriamos cual es el piso N.
Con una bombilla está claro; pero ahora suponed que nos dan 2 bombillas.
¿Cual seria la estrategia para minimizar el numero de lanzamientos y saber el piso N?
¿ Cuantos lanzamientos necesitarias?
Volvemos a suponer , claro , el peor de los escenarios posibles, es decir , se podrá acertar en menos lanzamientos , pero cual es el minimo con el que te aseguras que sabrás el piso N , usando (rompiendo) solo 2 bombillas.
Solucion en comentarios
14 comentarios:
De primeras se me ocurren 500, pero me da que no va a ser tan fácil...
No , son bastantes menos , en cualquier caso , decid la estrategia.
pues aventar la bombilla desde el piso 4, 8, 12, 16 etc...
despues si se rompe en uno de eso ya la hicimos jaja pero si pues aventar la bombilla desde el piso 2, 6, 10 etc... si se rompe ahi ke bien pero si no entonces seria la 3 o la 5 etc...
Se puede saber en unos 63 intentos (uno arriba uno abajo, no me he parado a mirar el detalle).
Se tira la primera cada 32 pisos empezando por abajo ( Hay 32 grupos de 32 pisos en un edificio de 1000 pisos)
Cuando pete la primera bombilla sabemos en qué grupo de 32 está el piso buscado, solo falta recorrer esos 32 con la otra.
El peor caso es llegar con la primera hasta el grupo más alto de pisos, por tanto 32 grupos + 32 pisos en el último grupo.
Supongo que son 63 si deducimos que si no ha petado en el penúltimo piso del grupo es que petará en el último.
He comprobado con el Excel que el mínimo de intentos se da cuando hacemos los grupos de 32.
Para grupos de 25 y de 40 pisos saldría 65 (64) intentos, y empeora para grupos menores a 25 o mayores a 40.
Con esta técnica el mínimo sale en 32.
Correcto , Baterpruf.
Esperaba que durara mas tiempo y que hubiera mas opiniones, pero está visto que hay mucha materia gris por aquí.
Son 63 intentos y efectivamente hay que hacerlo por grupos de 32 ( 32 es la raiz cuadrada de 1000 , tomada como entero mas proximo), como bien explicas.
Pero no siempre sale así , incluso se puede buscar otro tipo de estrategia.
El reto ahora es hacerlo en un edificio de 100 plantas.Con las mismas condiciones del problema inicial, ¿Cuantos lanzamientos necesitariamos?
Sigue la misma lógica.
Hay que hacer grupos de 10 y en el peor caso harán falta 19 intentos.
Igual me paso de chulillo y me equivoco pero para un edificio de "p" pisos y una cantidad de bombillas "n" la solución óptima de agrupamiento sería:
Primer barrido: grupos de
(raiz n-ésima de p pisos) elevado a (n-1)
Segundo barrido dentro del subgrupo localizado: grupos de
(raiz (n-1)-ésima de p pisos) elevado a (n-2)
Tercer barrido dentro del subgrupo localizado: grupos de
(raiz (n-2)-ésima de p pisos) elevado a (n-3)
etc....
último barrido:
grupos de
raiz n-ésima de p pisos
Por ejemplo para 1000 pisos y 3 bombillas primero pasamos de 100 en 100 (raiz tercera elevado a 2 de 1000) y una vez encontrado el grupo de 100 lo barremos de 10 en 10 (raíz tercera de 1000).
En el peor caso salen unos 28 intentos.
Bueno , la solucion verdadera no coincide con ésto que parece lógico.
Realmente en el caso de 1000 pisos tampoco es así , pero es dificil calcularlo sin la ayuda de una hoja de excel o un programita.La solucion planteada por tí (baterpruf) es la mas logica ( al menos a mi me lo parece) inicialmente , pero hay otra posibilidad , y es que el barrido no sea uniforme , es decir , no lo hagamos en grupos de 32 ( en el caso de 1000 plantas) o de 10 (en el caso de 100 plantas)
En ambos casos , el razonamiento a seguir es el mismo , pero con 100 sí se puede hacer "manualmente".
Vamos allá:
En esta estrategia , empezamos desde 100 ,y restamos series de 0, 1, 2 ,3 de tal forma:
100 - 0 = 100
100 - 1 = 99
99 - 2 = 97
97 - 3 = 94
94 - 4 = 90
90 - 5 = 85
85 - 6 = 79
79 - 7 = 72
72 - 8 = 64
64 - 9 = 55
55 - 10 = 45
45 - 11 = 34
34 - 12 = 22
22 - 13 = 9 -> paramos , porque 9 - 14 = -5 ya no hay planta -5.
En este caso los bloques de barrido empezarian por el piso 8 , 21,33,...y en el peor escenario posible nos sale 13 , y no 19.
El razonamiento a seguir es el mismo para 1000.
No estoy de acuerdo con la solución.
¡Yo descubro el piso en sólo 45 intentos!
Así que nada de hacerlo en 63 intentos.
Lo que hay que tener en cuenta es que no es necesario lanzar la primera bombilla con el mismo intervalo de pisos sino que se puede ir reduciendo, creo que algo así quiere decir Jose en el último mensaje. Para encontrar el valor lo que hice fue sumar la progresión aritmética 1, 2, 3, 4, 5, ...n, y ver en que valor se logra superar los 1000 pisos. Esto es así porque cada vez que lance la primera bombilla una vez más, debo tener un lanzamiento menos para la segunda bombilla.
Veamos el procedimiento en concreto:
Lanzo la primera bombilla desde el piso 45. Si se rompe debo lanzar la otra bombilla desde el piso 1 hasta el 44 y cuando se rompa ese será el piso. En el peor de los casos, se romperá en el 44 y ese es el piso buscado o no se romperá y el piso será el 45. En el caso de que la primera bombilla permanezca intacta en su primer lanzamiento debo hacer el segundo lanzamiento en el piso 89 (45+44) si se rompe probaré con la segunda bombilla desde el piso 46 hasta el 88 (son un máximo de 43 lanzamientos mas los 2 que llevaba con la primera hacen 45). El procedimiento seguirá en caso de no romperse la primera bombilla en los pisos 132, 174, 215, 255, etc. Si no se rompe la primera bombilla, y siguiendo el mismo proceso, tras lanzarla 37 veces cada vez a una distancia menor, llego al piso 999 y ya tengo la solución. Si intentamos hacer lo mismo pero empezando en el piso 44 nos encontramos con que en el lanzamiento 44 de la primera bombilla solo estamos en el piso 990.
Con 100 plantas llegarán 14 intentos pues 1+2+3+...+14=105.
El razonamiento de Jose dice que son 13 porque se olvida de un lanzamiento. Veamos:
Primer lanzamiento--> Planta 9 (yo empiezo en la 14 pero como sobran 5 da igual).
2º lanz-->9+13=22. Si aquí se rompe, tras 2 lanzamientos, el caso más desfavorable es que la planta sea la propia 22, y tendríamos que probar con la segunda bombilla 12 veces (de la 10 a la 21) con lo que serían 14 en total.
Otro aspecto a considerar, si queremos ser perfeccionistas, es que una vez que hemos optimizado el número máximo de lanzamientos, también podemos minimizar los casos en los que se debe hacer este número de lanzamientos.
Tu razonamientoy explicacion, como siempre , estupendo ,email_galicia.
Como observaras, en el ultimo comentario, negaba que la solucion de 63 fuera la correcta; quizá no lo expliqué bien. Mi primera contestacion al problema de 1000 plantas de dar por buena la solucion de 63 , fue porque parece lo mas logico y no queria dar otra estrategia , ya que con mil plantas , calcular la progresion reduciendo pisos , conlleva el uso de una hoja de excel ( o al menos calculadora), así planteando el problema para 100 pisos , esto ya no es imprescindible ( hombre , en el caso de 1000 pisos , tampoco es imprescindible , pero sí conveniente) y se podia hacer manualmente.
Si hubiera comentado esto al principio , creo que lo hubiera puesto facil , aunque posiblemente tampoco lo hice bien con esa pequeña "trampa" que intenté aclarar después.
En el caso de 100 , tu razonamiento y el mio difieren en que tu empiezas a contar desde abajo y yo desde arriba para el calculo de los sectores; creo que es indiferente , pero efectivamente , he vuelto a repasar los lanzamientos efectivamente me he olvidado de 1 lanzamiento ( No se cual :D )y salen 14 lanzamientos.
Mis felicitaciones por tu exposicion.
esta claro, hay una parte de las matematicas llamada "programacion lineal", si la usas sabras el piso n.
Bien , anonimo , pero me perdí esa clase ;)
la planta n (solo pregunto)seria la 18 ¿no?
Bueno , realmente buscamos el numero de lanzamientos n , que en el caso de 100 plantas es 14 y en el de 1000 es 45
ok esq e seguido el abecedario (cosa de tontos q es solo x probar)y la n es la letra numero 18
Publicar un comentario