- Problema de Flavio Josefo
-
Problema de Flavio Josefo
El problema de Flavio Josefo es un problema teórico que se encuentra en matemática y ciencias de la computación.
Contenido
Planteo
El problema plantea lo siguiente:
Hay n personas paradas en un círculo esperando a ser ejecutadas. Después de que ejecutan a la primera persona, saltean a k − 1 personas y la persona número k es ejecutada. Entonces nuevamente, saltean a k − 1 personas y la persona número k es ejecutada. La eliminación continúa alrededor del círculo (que se hace cada vez más pequeño a medida que más personas son eliminadas del mismo) hasta que sólo queda la última, que es liberada.
El objetivo es escoger el lugar inicial en el círculo para sobrevivir (es el último que queda), dados n y k.
Historia
El nombre hace referencia a Flavio Josefo, un historiador judío que vivió en el siglo I. Según lo que cuenta Josefo, él y 40 soldados camaradas se encontraban atrapados en una cueva, rodeados de romanos. Prefirieron suicidarse antes que ser capturados y decidieron que echarían a suertes quién mataba a quién. Los últimos que quedaron fueron él y otro hombre. Entonces convenció al otro hombre que debían entregarse a los romanos en lugar de matarse entre ellos. Josefo atribuyó su supervivencia a la suerte o a la Providencia, aunque sabía que no era así.[1]
Referencias
- ↑ La guerra de los judíos, 3.387-391
Enlaces externos
- Josephus Flavius game (Java Applet) at cut-the-knot.
Categorías: Combinatoria | Problemas computacionales | Permutaciones
Wikimedia foundation. 2010.
