Problema de Flavio Josefo

Busto de Flavio Josefo quién vivió en la región de Alejandría, en el primer siglo de la era común. A dicho personaje se le atribuye la historia que dio origen al problema que lleva su nombre.

Gráfico de la evolución del problema de Flavio Josefo para 500 personas y un valor de salto de 6. El eje horizontal es el número de persona. El eje vertical (de arriba hacia abajo) es el tiempo (el número de ciclo). Una persona viva es representada como un punto verde, una muerta como un punto negro.​

En matemáticas y en las ciencias de la computación, el problema de Flavio Josefo (o permutación de Josefo) es un problema teórico relacionado con un cierto problema de echar suertes.

Hay gente de pie en un círculo a la espera de ser ejecutada. La cuenta comienza en un punto y dirección específica del círculo. Después de que se haya salteado a un número determinado de personas, la siguiente persona es ejecutada. El procedimiento se repite con las personas restantes, a partir de la siguiente persona, que va en la misma dirección y omitiendo el mismo número de personas, hasta que solo una persona permanece y se libra.

El problema (dado el número de personas, punto de partida, dirección, y el número de personas a saltar) es elegir la posición en el círculo inicial para evitar la ejecución.

Historia

El problema recibe el nombre de Flavio Josefo, historiador judío que vivió en el siglo I. 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. Esta es la historia dada en el libro 3, capítulo 8, parte 7 de La Guerra de los Judíos de Josefo (escritura de sí mismo en tercera persona):

Sin embargo, en esta angustia extrema, él no estaba desprovisto de su sagacidad habitual; pero confiando a sí mismo a la providencia de Dios, puso su vida en peligro: "Y ahora," dijo él, "ya que se resuelve entre nosotros que vamos a morir, vamos, encomendemos nuestras mutuas muertes a la determinación por suertes. Aquel a quien el azar caiga primero, que sea degollado por quien reciba el segundo azar, y por lo tanto la fortuna hará su progreso a través de todos nosotros; y ninguno de nosotros será asesinado por su propias manos, porque no sería justo si, cuando el resto haya muerto, alguien se arrepintiese y se salvase". Esta propuesta les pareció muy justa; y cuando él se había impuesto con ellos para determinar este asunto por azar, participó en la rifa también. El que obtuvo la primera suerte puesta en su cuello desnudo por quien obtuvo la siguiente, como supuso que el general iba a morir entre ellos, de inmediato pensó que la muerte, si Josefo moría entre ellos, sería más dulce que la vida; sin embargo, fue con el compañero de su izquierda hasta el final. Digamos que tal cosa ocurrió por casualidad, o por la providencia de Dios. Y como él estaba muy deseoso de no ser condenado por la suerte y de no de empapar su mano derecha con la sangre de sus compatriotas, lo convenció a confiar en él, y en vivir para él como a sí mismo.​

Los detalles del mecanismo utilizado en esta hazaña son bastante vagos. Según Dowdy y Mays,​ 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.​ Esta historia se ha repetido con frecuencia y los detalles específicos varían considerablemente de una fuente a otra. Por ejemplo, Herstein y Kaplansky (1974) tienen a Josefo y a sus 39 compañeros colocados en círculo con cada séptimo hombre eliminado.​ Una historia del problema se puede encontrar en la carta de S. L. Zabell al editor de la Fibonacci Quarterly.​

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.​

Variantes y generalizaciones

Una versión medieval del problema de Josefo involucra a 15 cristianos y a 15 turcos a bordo de un barco en una tormenta que se hundirá a menos que la mitad de los pasajeros sean arrojados por la borda. 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?​ 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":​ 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.

Una generalización del problema es la siguiente. 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)​

Solución

Se resuelve el problema de manera explícita cuando cada segunda persona muere, es decir, $k=2$. (Para un caso más general donde $k\neq 2$, puede verse la solución más abajo.) Expresamos la solución recursiva. Sea $f(n)$ la posición de la superviviente cuando hay inicialmente $n$ personas (y $k=2$).En la primera vuelta alrededor del círculo, todas las personas en posición par mueren. En la segunda vuelta al círculo, la nueva segunda persona muere, después la nueva 4.ª persona, etc .; 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 $x$ durante la segunda vuelta alrededor del círculo estaba originalmente en la posición $2x-1$ (para cualquier valor de $x$). Sea $n=2j$ la persona en $f(j)$ que ahora sobrevivirá, estaba originalmente en la posición $2f(j)-1$. Esto nos da la recurrencia

$f(2j)=2f(j)-1\;.$

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. En este caso, la persona en la posición $x$ estaba originalmente en la posición $2x+1$. Esto nos da la recurrencia

$f(2j+1)=2f(j)+1\;.$

Cuando contabilizamos los valores de $n$ and $f(n)$, vemos el patrón:

$n$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
$f(n)$	1	1	3	1	3	5	7	1	3	5	7	9	11	13	15	1

Esto sugiere que $f(n)$ es una secuencia creciente impar que retorna con $f(n)=1$, siempre que el índice n sea una potencia de 2. Por lo tanto, si elegimos m y l de manera que $n=2^{m}+l$ y $0\leq l<2^{m}$, entonces $f(n)=2\cdot l+1$. Está claro que los valores de la tabla satisfacen esta ecuación. O podemos pensar que después de que $l$ personas hayan muerto, solo hay $2^{m}$ personas y nos vamos a la $2l+1$-ésima persona. Él debe ser el sobreviviente. De tal modo que $f(n)=2l+1$. A continuación, damos una demostración por inducción.

Teorema: Si $n=2^{m}+l$ y $0\leq l<2^{m}$, entonces $f(n)=2l+1$.

Prueba: Usamos la inducción sobre $n$. El caso base $n=1$ es correcto. Consideramos separadamente los casos cuando $n$ es par y cuando $n$ es impar.

Si $n$ es par, entonces se elige $l_{1}$ y $m_{1}$ tal que $n/2=2^{m_{1}}+l_{1}$ y $0\leq l_{1}<2^{m_{1}}$. Notar que $l_{1}=l/2$. Tenemos $f(n)=2f(n/2)-1=2((2l_{1})+1)-1=2l+1$, donde la segunda igualdad se deduce de la hipótesis de inducción.

Si $n$ es impar, entonces se elige $l_{1}$ y $m_{1}$ tal que $(n-1)/2=2^{m_{1}}+l_{1}$ y $0\leq l_{1}<2^{m_{1}}$. Notar que $l_{1}=(l-1)/2$. Tenemos $f(n)=2f((n-1)/2)+1=2((2l_{1})+1)+1=2l+1$, donde la segunda igualdad se deduce de la hipótesis de inducción. Esto completa la demostración.

La podemos resolver para $l$ para obtener una expresión específica para $f(n)$:

$f(n)=2(n-2^{\lfloor \log _{2}(n)\rfloor })+1$

La expresión más elegante recurre a la representación binaria de tamaño $n$: $f(n)$ se pueden obtener por un desplazamiento cíclico de un bit a la izquierda de $n$ por sí solo. Si representamos $n$ en binario como $n=1b_{1}b_{2}b_{3}\dots b_{m}$, entonces la solución está dada por$f(n)=b_{1}b_{2}b_{3}\dots b_{m}1$. La prueba de esto se desprende de la representación de $n$ como $2^{m}+l$ o de la expresión de arriba para $f(n)$.

Implementación: Si n indica el número de personas, la posición de seguridad está dada por la función $f(n)=2l+1$ ,donde $n=2^{m}+l$ y $0\leq l<2^{m}$.

Ahora si representamos el número en formato binario, el primer bit indica $2^{m}$ y los bits restantes se denotarán por $l$. Por ejemplo, cuando n = 41, su representación binaria es

n = 1 0 1 0 0 1

2^m = 1 0 0 0 0 0

l = 0 1 0 0 1

    /**
	 * 
	 * el parámetro n el número de personas en el círculo
	 * devuelve la posición de aquellos que sobrevivirán la ejecución
	 *   f(N) = 2L + 1 donde N =2^M + L y 0 <= L < 2^M
	 */
	public int getSafePosition(int n) {
		// find value of L for the equation
		int valueOfL = n - Integer.highestOneBit(n);
		int safePosition = 2 * valueOfL  + 1;
		
		return safePosition;
	}

El caso general

La 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. Cuando el índice comienza desde 1, la persona en la posición $s$ se desplaza desde donde está la primera persona en la posición $((s-1){\bmod {n}})+1$, donde n es el número total de personas. Sea $f(n,k)$ la posición del superviviente, después de que la $k$-ésima persona haya muerto, nos quedamos con un círculo de $n-1$ personas, y se inicia el siguiente conteo con la persona cuyo número en la situación original fue $(k{\bmod {n}})+1$. La posición del superviviente en el círculo restante sería $f(n-1,k)$ si empezamos a contar en $1$; cambiando al hecho de que estamos a partir de $(k{\bmod {n}})+1$, se obtiene la recurrencia.

$f(n,k)=((f(n-1,k)+k-1){\bmod {n}})+1,{\text{ con }}f(1,k)=1\,,$

que toma una forma más simple

$g(n,k)=(g(n-1,k)+k){\bmod {n}},{\text{ con }}g(1,k)=0$

si numeramos las posiciones de $0$ a $n-1$ en su lugar.

Esta aproximación tiene un tiempo de ejecución $O(n)$, pero para una $k$ pequeña y una $n$ grande, hay otra aproximación. El segundo enfoque también utiliza la programación dinámica, pero tiene tiempo de ejecución $O(k\log n)$. Está basado en que se considera matar a la k-ésima, 2k-ésima,..., $(\lfloor n/k\rfloor k)$-ésima persona una a una, e ir cambiando la numeración.

Este enfoque mejorado toma la forma

$g(n,k)={\begin{cases}0&{\text{si }}n=1\\(g(n-1,k)+k){\bmod {n}}&{\text{si }}1<n<k\\\left\lfloor {\frac {k((g(n',k)-n{\bmod {k}}){\bmod {n}}')}{k-1}}\right\rfloor {\text{donde }}n'=n-\left\lfloor {\frac {n}{k}}\right\rfloor &{\text{si }}k\leq n\\\end{cases}}$

Enlaces externos

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, y Clifford Stein (2001). «Capítulo 14: Aumentar estructuras de datos». Introducción a los algoritmos (Segunda edición). MIT Press and McGraw-Hill. p. 318. ISBN 0-262-03293-7. 
• Bogomolny, Alexander. «El juego de Flavio Josefo». Interactive Mathematics Miscellany and Puzzles (en inglés).  (inglés)
• Armin Shams-Baragh Formulando el problema extendido de Josefo (inglés)
• El problema de Josefo en la enciclopedia MathWorld (inglés)
• Daniel Erman (28 de octubre de 2016). «El problema de Josefo - Numberphile» (video). YouTube: Brady Haran. Consultado el 29 de octubre de 2016.  (inglés)

• Datos: Q1064357