Prisioneros y permutaciones

Cómo incrementar las probabilidades de éxito cuando todo parece en contra.

DANIEL UZQUIANO

Hace poco más de un año discutíamos un problema de coordinación entre varios prisioneros a quienes se les ofrecía una oportunidad para liberarse [véase «Los prisioneros y la bombilla», por G. Uzquiano; Investigación y Ciencia; marzo de 2011]. Hoy trataremos un problema del mismo género, popularizado por Peter Winkler.

En esta ocasión, 100 prisioneros son llevados a una habitación en la que hay un fichero con 100 cajones, cada uno de los cuales contiene el nombre de uno de los reclusos. Uno por uno, los prisioneros pueden acceder al fichero y abrir hasta un máximo de 50 cajones, para luego dejar todo como estaba. Al igual que en el caso anterior, tendrán prohibido comunicarse entre sí una vez que haya empezado el proceso. Para salir libres, cada recluso deberá encontrar su nombre en alguno de los cajones que abra; si eso no ocurre, todos serán ejecutados. El problema consiste en formular una estrategia que les permita incrementar hasta más del 30 por ciento las probabilidades de éxito.

Mientras los prisioneros discuten qué método adoptar, el guarda, que no puede escuchar las deliberaciones, intentará sabotear el plan. Para ello, intercambiará sus nombres una vez que los reclusos hayan acordado su estrategia. Eso sí, el guarda no podrá realizar ningún otro cambio después de que haya entrado el primer prisionero.

Puedes obtener el artículo en...

¿Tienes acceso a la revista?

Los boletines de Investigación y Ciencia

Elige qué contenidos quieres recibir.

Responsable: Prensa Científica, S.A. Finalidad: enviarle por correo electrónico los boletines que haya solicitado recibir. Derechos: tiene derecho a acceder, rectificar y suprimir sus datos, así como a otros derechos, como se explica en la información adicional y detallada que puede consultar en nuestra Política de Privacidad.