2006-12-04

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:

15 Comentarios:

At 8:19 p. m., Blogger Jose said...

Pues yo creo que solo una rata ( la que muera.

 
At 8:29 p. m., Blogger Sergio said...

Mmm, pero si muere una rata, ¿de cuál de las mil botellas ha bebido?

 
At 9:39 p. m., Blogger Alvaro G.A. said...

Este comentario ha sido eliminado por un administrador del blog.

 
At 10:41 p. m., Blogger Alvaro G.A. said...

La solución es: log2(n)
Con n=numero de botellas

Jose dijo...
Pues yo creo que solo una rata ( la que muera.

Aunque el resto de las 999 ratas sobrevivan, ¿las necesitarias para hacer las pruebas no? Da igual que las mates, las liberes o las uses de guarnición, las necesitas para hacer las pruebas.

 
At 9:01 a. m., Blogger Jose said...

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?

 
At 9:05 a. m., Blogger Sergio said...

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

 
At 1:21 p. m., Anonymous Ra said...

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

 
At 1:19 p. m., Blogger Alvaro G.A. said...

Solo hay tiempo para una iteración.

Pero, me gustaría confirmar que entiendo el metodo que "propones". Porque no lo explicas.

Tu proponpones: darle 500 botellas a una rata y otras 500 a otra. Una de las dos ratas morirá.

Divides la mitad envenenda en dos partes, una se la bebe la rata superviviente y otra una nueva.

Esto se repite hasta que solo queda una botella en la "mitad envenenada".

Pues así necesitarias casi 10 meses. Porque el veneno tarda en actuar casi un mes.

Eso si, has descubierto una nueva modalidad de ruleta rusa.

Un miniproblema: ¿Cuantas posibilidades tiene de sobrevivir el proceso, una de las dos ratas iniciales?

 
At 1:34 p. m., Blogger Alvaro G.A. said...

Una forma derivada de la anterior y que "solo" retrasaría la fiesta 4 meses. Sería empezar dandole a cada una de las 10 ratas 100 botellas. Solo una morirá.

Se dividen las 100 botellas entre 9 ratas. Unas tocan a 12 otras a 11.

Se dividen las 11 o 12 botellas entre las 8 ratas. Unas tocan a 1 otras a 2.

Si por desgracia muere una de las que bebieron 2 botellas. Se utiliza una voluntaria para beberse una de las dos que quedan.

Y otra mejora sería dejar en cada iteración un grupo de botellas sin probar, lo que en la práctica es como tener una rata extra. Además habría una posibilidad de tardar un mes menos si el grupo envenenado en algunas de las iteraciones resulta ser inocuo.

Pero... ninguna de estas ideas son la solución óptima.

 
At 2:31 p. m., Anonymous moralejo said...

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

 
At 2:32 p. m., Anonymous moralejo said...

acabo de leer lo q e escrito y si alguien lo entiendo que me lo explique

:D

 
At 2:40 p. m., Blogger Sergio said...

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 ;)

 
At 5:30 p. m., Anonymous Anónimo said...

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

 
At 11:47 a. m., Blogger Jose said...

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)

 
At 11:59 a. m., Blogger Sergio said...

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

Enlazan a este artículo:

Crear un enlace

<< Inicio