Flavio Josefo fue un historiador judío que vivió en el siglo I. Según cuenta Josefo, él y cuarenta soldados camaradas fueron capturados por los romanos después de la caída de Jotapata. Antes que rendirse, decidieron acabar ellos mismos con sus vidas. Para hacerlo, se dispusieron en un círculo y acordaron que irían contando de tres en tres, de forma que cada tercer soldado sería ejecutado por la persona de su izquierda. El último hombre que quedara con vida tendría que suicidarse. Según cuenta la leyenda, Josefo calculó rápidamente cuál sería la posición del último hombre en morir para colocarse allí, y una vez hubieron muerto sus compatriotas, se entregó a los romanos.
Otra versión dice que el orden de ejecución fue determinado por sorteo y que, por azar, los últimos que quedaron al finalizar el proceso fueron él y su mejor amigo, entonces Josefo tuvo un cambio repentino de opinión y convenció a su amigo para entregarse a los romanos en lugar de matarse entre ellos. Esta sabia e interesada decisión permitió que Josefo sobreviviera y que su problema trascendiera en el tiempo.
El problema de Flavio Josefo, en versión general, propone que m personas están en un círculo y son eliminadas en orden contando cada n personas. Se trata de averiguar cuál será el superviviente.
Por ejemplo, con m=12 y n=3, el sobreviviente es la persona 10. Veamos el proceso:
Para probar en diferentes situaciones, el siguiente enlace contiene un applet que permite jugar con el tema. El jugador selecciona una posición y presiona uno de los botones para observar la secuencia en la que se va a morir la gente. El objetivo del juego, por supuesto, es mantenerse vivo eligiendo el lugar adecuado.
La solución general del problema no es trivial. Se puede atacar el problema en el caso sencillo de que n sea 2, o sea, que una de cada dos personas sea eliminada por orden. Si designamos como J(n) a la posición de la persona salvada en función de n, que es el número total de personas, obtenemos la siguiente tabla:
|
n |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
|
J(n) |
1 |
1 |
3 |
1 |
3 |
5 |
1 |
3 |
5 |
7 |
1 |
3 |
5 |
7 |
9 |
1 |
De ella se puede deducir que sólo se salva la primera persona en el caso de que haya un número total que sea una potencia de 2. Y en general J(2k + r) = 2r + 1 donde 0 ≤ r < 2k, esto es, r es la posición en que se encuentra m entre dos potencias de 2 consecutivas.
Para los interesados aquí tenéis la solución general del problema de Josefo, junto con una introducción histórica y algún problema abierto como el siguiente: supongamos que Josefo se encuentra en una posición dada j, ¿se puede elegir el parámetro de eliminación m para que pueda salvarse?
¡Mates, Mates! 