Divulgación El barril envenenado

[angel relativamente]

Hola compañeros, dejo aquí un acertijo interesante que me ha planteado una amiga. ¡Suerte!

Un rey quiere dar una fiesta en sus tierras dentro de 31 días, y para ello ha encargado a la bodega 1000 barriles de vino. Una noche, un intruso se cuela en la bodega y envenena uno de los barriles. A pesar de que lo capturan, el intruso no recuerda cuál de todos es el barril envenenado. Lo único que les puede decir es que ha envenenado tan solo 1 barril, y que el veneno es letal y tarda unos 30 días en hacer efecto. Como el rey no quería la fiesta sin vino y tampoco quería envenenar a su pueblo, se le ocurre una solución al problema. Propone darles a probar 100 barriles distintos a cada uno de sus 10 esclavos. De esta manera, el día antes de la fiesta moriría uno de los esclavos, y podrían retirar el lote de 100 que bebió el esclavo muerto. No obstante, un sabio consejero le dice que existe una forma para detectar exactamente el barril envenenado sacrificando como máximo a esos 10 esclavos. ¿Cuál es esa forma?

[Alriga]

Re: El barril envenenado

El problema me parece muy bonito. No respondo porque lo conozco desde hace años. Pero te agradezco que lo hayas puesto, me trae buenos recuerdos.
Saludos.

[Richard R Richard]

Re: El barril envenenado

Creo que me dado cuenta por donde van los tiros, aunque en la practica como le sucedería al rey sería engorroso practicarlo pero no imposible.

Ocultar contenido

Mostrar solución Ocultar solución

Consiste en darle a cada esclavo un cóctel del vino extraído de 500 barriles ( la mitad ) y el problema es mas exacto de resolver si fueran 1024 los barriles, por lo que podría agregarle la compra de esos 24 adicionales y encontrar al barril envenenado también. el tema es que al primero se le dan el cóctel de 500 barriles o 512 para se exactos, numerados del 513 al 1024 al segundo se le da la el cóctel proveniente de la mitad de los que se le dieron al anterior y la mitad de los que no se probaron es decir del 257 al 512 y los que se numeran del 769 al 1024, así se han creado 4 conjuntos (1 no ha si probado por nadie, otros dos por uno solo de ellos y uno por los dos) resumiendo el problema a esta situación es fácil ver que si no muere ninguno es barril esta en el primer conjunto, si muere uno esta en 2 o 3 depende quien muera o en el 4 si mueren los dos así que siguiendo con la subdivisión de conjuntos.... al tercero se le da la mezcla de la mitad de esos 4 conjuntos formando 8 conjuntos así el décimo prueba un cóctel de 1 entre 2^10 conjuntos 1024 , por lo tanto es posible que registrando que es lo que tomo cada uno, el día 31 sabiendo cuales han muerto por intersección de conjuntos, saber cual es barril que esta presente en todos los conjuntos de los que han muerto, ergo ese el barril envenenado. es un problema muy similar a ese juego de ingenio que consiste en presentar en una lamina con una serie de dibujos, escoger uno, en identificarlo en una serie de cartas, según en las cartas en que aparece es posible saber de que dibujo se trata por asignar un valor a la carta proporcional a $2^n$ la sumatoria de $c_i2^n_i$ donde $c_i$ es o bien 0 o 1 dependiendo si la carta no contiene o contiene el dibujo. En este problema si numeramos del 1 al 1024 los barriles y de 1 a 10 a los esclavos $e$ si asignamos el valor 1 a un esclavo muerto y 0 al vivo el numero del barril sale de $N=\dst\sum_1^{10} e_i2^(10-i)$

Edito.me corrijo levemente si los numero del 1 al 1024 hay que sumarle 1 a la formula
$N=[\dst\sum_1^{10} e_i2^(10-i)]+1$

o numerar los barriles del 0 al 1023 así si ninguno muere es el barril número 0 y si mueren todos el 1023

[Zorak]

Re: El barril envenenado

Di bastante vuelta, hasta que me acorde de unas cosas que di hace tiempo en álgebra 1

Ocultar contenido

Mostrar solución Ocultar solución

\Para llegar a la respuesta lo plantee usando análisis combinatorio.Usando la formula de combinaciones sin repetición $\frac{n!}{r!(n-r)! }$. Donde n es el numero de elementos que se puede elegir , en este caso son 10 (la cantidad de esclavos), y r es la cantidad de esos elementos que eliges.

-Si hacemos que cada esclavo tome un barril diferente n=10 y r=1 esto da 10 brarriles.
-Si hacemos grupos de a 2 ( osea que cada esclavo comparta un barril con otro) n=10 y r=2  serian 45 barriles.
-Si hacemos grupos de a 3 (que cada esclavo comparta un barril con otros 2) n=10 y r=3 da 120 barriles.

...si seguimos así hasta llegar a r=10 y sumamos todas las combinaciones nos da 1023, por cada combinación que tenemos le corresponde un barril , en este caso podríamos elegir solo 1000 de esas combinaciones, así que para saber cual es el barril basta con saber todas las combinaciones y ver cual es la que se muere, y el barril que le corresponde.

[Fortuna]

Re: El barril envenenado

$\log_2(1000)=9.96\approx 10$

El problema es equivalente a adivinar un número del 1 al 1000. Eso se puede hacer con 10 preguntas binarias.

[angel relativamente]

Re: El barril envenenado

¡Enhorabuena a los que habéis sacado conclusiones! En efecto Alriga es un problema muy bonito, y al principio parece antiintuitivo pensar que puede solucionarse, sobre todo si buscas una solución como la del rey. Dejo aquí dos soluciones similares a las que ya se han sacado que he intentado formalizer un poco

Ocultar contenido

Mostrar solución Ocultar solución

El objetivo es etiquetar los barriles de forma que la etiqueta deje claro los esclavos que beben y los que no, y que luego en función de los muertos se pueda determinar unívocamente el barril envenenado. Dos posibilidades:

1) Sea $E=\{1,\cdots , 10 \}$ el conjunto de esclavos. Queremos etiquetar los barriles de forma que cada uno lo pruebe una combinación distinta de esclavos. El número de subconjuntos de $E$ es $2^{10}=1024$ (en general, el número de subconjuntos de un conjunto finito $F$, entre los que se incluye el vacío y el total, es $2^{| F | \}$). Por tanto si etiquetas todos los barriles con 1000 de los 1024 subconjuntos de $E$, cada barril lo probarán los esclavos que pertenezcan al subconjunto que marca cada etiqueta y el barril envenenado sera aquel que tenga por etiqueta el subconjunto cuyos elementos son los esclavos muertos.

2) Otra forma de plantearlo es la binaria. El día 30 me encontraré con una serie de esclavos vivos y muertos. Si llamamos 0 a los vivos y 1 a los muertos podemos simplificar el problema a obtener una secuencia de 0s y 1s de longitude 10. Es también sencillo observar que el número de secuencias de longitude 10 que alteren 0s y 1s es $2^{10}=1024$, o dicho de otro modo, los números binarios del $0_{10}$ al $1023_{10}$ son de 10 cifras o menos. Si etiquetamos los barriles con los números binarios (añadiendo 0s a la izquierda hasta completer 10 cifras) desde el 0 hasta el 999, cada barril tendrá asociada una secuencia de longitud 10 de 0s y 1s, donde 0 indica que el esclavo en esa posición no bebe y 1 que sí. Al final según la secuencia de vivos y muertos que obtengamos podremos determinar el barril.