Autor: Nicolas Kovensky

Hola! Acá y acá van a encontrar unos apuntes que armamos sobre algunas cosas de la guía 2 que discutimos en la práctica estas últimas dos clases, y también sobre algunas otras para las que no nos dio el tiempo.

Buenas! Simplemente para confirmar que mañana habrá clases, tanto teórica como práctica, todo en el horario normal.

Ya que estamos, les planteo el siguiente problema de los 100 prisioneros, relacionado con lo que vamos a estar discutiendo en la práctica.

Hay 100 prisioneros, numerados del 1 al 100. En una habitación separada hay 100 cajas, también numeradas del 1 al 100. Dentro de cada caja hay una hoja con un número del 1 al 100, y cada número aparece exactamente una vez (sin repeticiones).

Cada prisionero, uno por uno, entra solo en la habitación y puede abrir hasta 50 cajas para buscar el papel con su propio número. Si lo encuentra, se considera que ha tenido éxito. Después de su turno, se vuelve a cerrar todo como estaba antes de ingresar (y luego es el turno del prisionero siguiente).

Para que todos sean liberados, los 100 prisioneros deben encontrar su propio número en sus respectivos turnos.
Si alguno falla, todos pierden.

Los prisioneros no pueden comunicarse entre sí una vez que comienza el proceso, pero pueden planear una estrategia juntos antes de que todo comience.

¿Cuál es la probabilidad de que los prisioneros logren ser liberados si buscan su número abriendo cajas al azar? El resultado probablemente no sea muy alentador…
¿Se les ocurre una mejor estrategia?