Hace poco me encontré con un interesante rompecabezas lógico durante un desafío en una competición de programación. Ninguna de las personas del equipo de dos personas que completaba ese desafío pudo averiguar una respuesta que funcionara en todos los escenarios, y tampoco pudieron hacerlo las demás personas del equipo de la escuela.
El problema se describió de la siguiente manera:
Eres un hombre rico y sin escrúpulos que posee diez esclavos. Dentro de seis horas va a celebrar una gran cena en la que pretende servir mil barriles de vino.
Desgraciadamente, exactamente uno de los barriles está envenenado. Sabes que el veneno hace efecto entre 30 minutos y cinco horas después de la ingestión, variando de persona a persona.
Decides utilizar a tus esclavos para averiguar qué barril contiene el veneno antes de la cena.
Trabajando bajo los supuestos de que no se puede cancelar la cena, y de que no hay límite en la cantidad de vino que puede beber un esclavo, proponga una forma de averiguar qué barril está envenenado antes de que comience la parte de la cena.
La solución más obvia era utilizar un algoritmo de "divide y vencerás": asignar 100 barriles a cada uno de los 10 esclavos, luego asignar los 9 esclavos sanos/vivos restantes a los 100 barriles que incapacitaron a un esclavo, y repetir.
Mientras que este enfoque funciona asumiendo que el veneno actúa en 30 minutos (o en un periodo de tiempo corto), falla asumiendo cualquier cosa cercana al peor caso de tiempo de 5 horas.
¿Existe algún método que permita determinar qué barrica contiene el vino envenenado en las 6 horas previas a la cena?
