Problema de Flavio Josefo

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

El problema de Flavio Josefo es un problema teórico que se encuentra en matemática y ciencias de la computación. 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.[1]

Planteamiento[editar]

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, evitan a k-1 personas y la persona número k es ejecutada. Entonces nuevamente, evitan 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.

Variantes[editar]

Si Josefo tenía un cómplice, el problema consistía en encontrar los lugares de los dos últimos sobrevivientes (aquellos cuya conspiración aseguraría su supervivencia).[2]

Referencias[editar]

  1. La guerra de los judíos, 3.387-391
  2. Graham, Ronald; Donald Knuth y Oren Patashnik (1994). Concrete Mathematics: A Foundation for Computer Science, sección 1.3

Enlaces externos[editar]