El problema de la semana (XVIII)
Volvamos a los casos de vida o muerte, pero esta vez no es la nuestra, sino la de nuestros invitados. ¿Por qué? Porque vamos a dar una fiesta dentro de un mes, pero tenemos la mala fortuna de que una de las mil botellas de vino de nuestra bodega está envenenada. El vecino de al lado tiene envidia de nuestra fiesta y quiere arruinarla, por lo que parece.Afortunadamente un anónimo nos ha avisado del hecho, pero no sabemos cuál de todas está envenenada. Para no alarmara nadie, no queremos llamar a la policía, ni al laboratorio, ni nada de eso, pero claro, si vamos a gastar las mil botellas en la fiesta, tendremos que saber cuál vamos a descartar.
La solución más obvia, puesto que el veneno mata en menos de un mes, es darle un poco de vino a las ratas, y así averiguar que botella tenemos que descartar, pero... ¿cuántas ratas necesitamos?
Actualizado: Ya tenemos solución, el primero en darla fue Alvaro, que se calló los detalles para haceros pensar. Y después de unas cuantas divagaciones el usuario anónimo dió con la explicación correcta. Enhorabuena.
Etiquetas: El problema de la semana
enviado por Sergio @ 1:38 p. m.
11 Comentarios:
Pues yo creo que solo una rata ( la que muera.
Mmm, pero si muere una rata, ¿de cuál de las mil botellas ha bebido?
ok. Pensaba que era de pensamiento lateral.
¿Cuando dices que mata en menos de un mes, es posible que en un mes te de tiempo a comprobar con una misma rata mas de una botella?
Nop, solo sabemos que actua en menos de un mes, con lo que igual son 29 días, así que no puedes esperar, y si no se muere darle a probar de otra.
Sin embargo una rata sí puede beber de más de una botella. De hecho, Alvaro dió con la solución y da más pistas de lo que parece :)
Método de la bisección?
Con 10 ratas lo haces, siempre y cuando en la primera iteración no mueran ambas, una por el veneno y la otra de intoxicación etílica por probar 500 botellas de vino. Y si ésta sobrevive, como caiga siempre en la mitad en que no está el veneno, a largo plazo le diagnostico cirrosis roedoril fulminante.
En cualquier caso más te vale desratizar antes de la fiesta :p
lo veo pero no lo veo.
le damos 500 a una rata y 500 a otra.
una de las 2 morira.
de las 500 q le dimos a la q se muera le damos 250 a una y 250 a otra. de esas otras 2 morira una. de esa q muera le damos 125 a una y 125 a otra y asi sucesivamente.
esto se podria acer todo de una vez el mismo dia cada mitad porque no sabemos cual morira y al final del mes seguro q tenemos algo
seguro q tambien de la primera division la rata q no muera se podria beber 250 de la otra mitad. si muere podria ser porque la envenenada estaba en su mitad o porque estaba en las 250 de la otra. sino muere la otra de la primera division esque estaba en su mitad y si mueren las 2 esque estaba en la mitad de la que solo bebio 500
vamos un pifostio de cojones, aun asi seguro q acabo usando mas ratas de 1000
:P
acabo de leer lo q e escrito y si alguien lo entiendo que me lo explique
:D
Menudo lío que tenemos aquí!
El método de la bisección es una solución que propuso Ra porque no se le ocurrió otra cosa, y tiene el problema de que no nos da tiempo, como ya dijo Alvaro, necesitarímos 10 meses.
Claro, luego Alvaro empezó a darle vueltas a ese tema, pero que quede claro, la solución no va por ahí.
Como bien dijo Alvaro ya, la solución es log2(n) (logaritmo en base dos de n) con n el número de botellas, que a estas alturas, y como tiene que ser un número entero, todo el mundo debería saber que necesitamos 10 ratas.
Bien, lo que no dice Alvaro precisamente para que lo penseis, es como narices hacemos con 10 ratas para hallar la botella envenenada en menos de un mes.
Espero que con este queden las cosas más claras ;)
Habría que comenzar numerando bien las botellas y marcando las ratas para no confundirnos. A continuación, dejaríamos que la primera rata probara las 500 primeras botellas y no las 500 últimas, la segunda rata, probaría las 250 primeras botellas y las 250 primeras que la otra primera rata no probó)
Por sencillez a ver si me explico, vamos a decir que la primera rata prueba 500 ---, la segunda 250 -- 250 ---, donde --- quiere decir que no prueba las botellas
La tercera rata, probara 125 --- 125 --- 125 --- 125 ---
así sucesivamente, la rata n tomara 1000/2^n --- 1000/2^n --- 1000/2^n........
para poder identificar las botellas, necesitamos que la última rata pruebe una botella si una no, luego 1000/2^n = 1 y obtenemos las 10 ratas.
Con un número más pequeño, para que sirva de ejemplo, si tenemos 16 botellas, llamamos 1 a beber y 0 a no beber, tenemos
1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0
1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0
1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
pasado un mes, supongamos que la 2 y 3 rata han muerto pero no la 1 y la 4, tenemos una columna 0 1 1 0 y por tanto la botella envenenada es la 10
Creo que el usuario anonimo lo deja claro , otra forma intuitiva de explicarlo seria:
1 rata bebe de las botellas contadas de dos en dos y saltandose dos , es decir , de la 1, la 2 , la 5, la 6, la9 , la 10....
la rata 2 de 4 en 4 , es decir la 1,2,3,4 , la 9,10,11,12.....
la rata 3 de 8 en 8 ...
y asi hasta la decima. Todas beben 500 botellas , y sabiendo las que mueren obtenemos la botella envenenada.
No sé si he complicado la explicacion anterior ... ( que es la misma , pro con un buen razonamiento matematico)
Bueno, el problema está resuleto :)
Ahora voy a dar una explicación que considero un poco más intuitiva (quizá no) y que vuelve a ser la misma.
Cada rata solo nos puede dar un bit de información, porque o se muere o no (lamentablemente esto no es cuántica).
Lo que tenemos que hacer para aprovecharnos de esto es numerar las botellas del 0 al 999 en binario. Ahora, una vez etiquetadas las botellas, asignamos a cada rata un bit. Como 2^10=1024, necesitaremos 10 ratas, y además con estas 10 ratas también podríamos hacerlo si tuvieramos hasta 1023 botellas.
Ahora cada rata, bebe de cada botella solo si en su posición de bit hay un uno. Cuando haya pasado un mes, habrán muertos unas sí o otras no, las que sigan vivas nos dan un 0, las que esten muertas nos dan un 1. Con esto recomponemos el número de botella y ya está.
En definitiva es lo mismo que habeis explicado ya, pero el hecho de numerar las botellas en binario, me parece una buena solución (por supuesto no es mía) y algo más intuitiva.
Enhorabuena a todos.
Publicar un comentario
<< Inicio