Problema de Flavio Josefo
La cuenta comienza en un punto y dirección específica del círculo.
Según el relato del asedio de Yodfat de Josefo, él y sus 40 soldados quedaron atrapados en una cueva por los soldados romanos.
Eligieron el suicidio durante la captura, y establecieron un método para suicidarse en serie por sorteo.
Josefo afirma que, por suerte o, posiblemente de la mano de Dios, él y otro hombre se mantuvieron hasta el final y se rindieron a los romanos en lugar de matarse a sí mismos.
Según Dowdy y Mays,[3] en 1612 Bachet sugirió que el mecanismo específico fue disponer a los hombres en un círculo y contar de tres en tres para determinar el orden de eliminación.
[4] Esta historia se ha repetido con frecuencia y los detalles específicos varían considerablemente de una fuente a otra.
[6] Josefo tenía un cómplice; el problema era entonces encontrar los lugares de los dos últimos supervivientes (de cuya conspiración aseguraría sus supervivencias).
Alega que se colocó junto al otro hombre en las posiciones 31 y 16 respectivamente.
Los 30 se disponen en un círculo y cada novena persona ha de ser arrojada al mar.
¿Dónde deben los cristianos colocarse para garantizar que solo los turcos se lanzan?
[8] En otras versiones los roles de los turcos y los cristianos están intercambiados.
En Matemáticas concretas: Una Fundación de Ciencias Informáticas, Graham, Knuth y Patashnik describen y estudian una variante "estándar":[9] determinan dónde se disponen los últimos supervivientes si hay n personas inicialmente y cada segunda persona (k menor o igual a 2) es eliminada.
Suponemos que cada m-ésima persona será ejecutada de un grupo de tamaño n, en el cual la n-ésima persona es la superviviente.
Si hay una adición de x personas al círculo, entonces el superviviente está en la (p + mx)-ésima posición si es menor o igual a (p + mx) − (n + x)[10] Se resuelve el problema de manera explícita cuando cada segunda persona muere, es decir,
).En la primera vuelta alrededor del círculo, todas las personas en posición par mueren.
; es como si no existiera primera vez alrededor del círculo.
Si el número inicial de la gente es par, entonces la persona en la posición
durante la segunda vuelta alrededor del círculo estaba originalmente en la posición
Esto nos da la recurrencia Si el número inicial de la gente es impar, entonces pensamos que la persona en la posición primera morirá al final de la primera vuelta alrededor del círculo.
Una vez más, durante la segunda vuelta alrededor del círculo, la nueva segunda persona muere, después la nueva 4.ª persona, etc.
, siempre que el índice n sea una potencia de 2.
Por lo tanto, si elegimos m y l de manera que
: La expresión más elegante recurre a la representación binaria de tamaño
Por ejemplo, cuando n = 41, su representación binaria es n = 1 0 1 0 0 1 2m = 1 0 0 0 0 0 l = 0 1 0 0 1La forma más sencilla de resolver este problema en el caso general usando la programación dinámica mediante la realización de la primera etapa y luego utilizando la solución del problema restante.
se desplaza desde donde está la primera persona en la posición
, donde n es el número total de personas.
La posición del superviviente en el círculo restante sería
que toma una forma más simple si numeramos las posiciones de
El segundo enfoque también utiliza la programación dinámica, pero tiene tiempo de ejecución
Está basado en que se considera matar a la k-ésima, 2k-ésima,...,
