Problema de Flavio Josefo

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.

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):

Los detalles del mecanismo utilizado en esta hazaña son bastante vagos. Según Dowdy y Mays,^[2]​ 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.^[3]​ 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.^[4]​ Una historia del problema se puede encontrar en la carta de S. L. Zabell al editor de la Fibonacci Quarterly.^[5]​

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.^[6]​

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?^[7]​ 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":^[8]​ 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)^[9]​

Se resuelve el problema de manera explícita cuando cada segunda persona muere, es decir, ${displaystyle k=2}$. (Para un caso más general donde ${displaystyle k eq 2}$, puede verse la solución más abajo.) Expresamos la solución recursiva. Sea ${displaystyle f(n)}$ la posición de la superviviente cuando hay inicialmente ${displaystyle n}$ personas (y ${displaystyle 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 ${displaystyle x}$ durante la segunda vuelta alrededor del círculo estaba originalmente en la posición ${displaystyle 2x-1}$ (para cualquier valor de ${displaystyle x}$). Sea ${displaystyle n=2j}$ la persona en ${displaystyle f(j)}$ que ahora sobrevivirá, estaba originalmente en la posición ${displaystyle 2f(j)-1}$. 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. En este caso, la persona en la posición ${displaystyle x}$ estaba originalmente en la posición ${displaystyle 2x+1}$. Esto nos da la recurrencia

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

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

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

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

Si ${displaystyle n}$ es par, entonces se elige ${displaystyle l_{1}}$ y ${displaystyle m_{1}}$ tal que ${displaystyle n/2=2^{m_{1}}+l_{1}}$ y ${displaystyle 0leq l_{1}<2^{m_{1}}}$. Notar que ${displaystyle l_{1}=l/2}$. Tenemos ${displaystyle 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 ${displaystyle n}$ es impar, entonces se elige ${displaystyle l_{1}}$ y ${displaystyle m_{1}}$ tal que ${displaystyle (n-1)/2=2^{m_{1}}+l_{1}}$ y ${displaystyle 0leq l_{1}<2^{m_{1}}}$. Notar que ${displaystyle l_{1}=(l-1)/2}$. Tenemos ${displaystyle 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 ${displaystyle l}$ para obtener una expresión específica para ${displaystyle f(n)}$:

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

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

Ahora si representamos el número en formato binario, el primer bit indica ${displaystyle 2^{m}}$ y los bits restantes se denotarán por ${displaystyle 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

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

que toma una forma más simple

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

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

Este enfoque mejorado toma la forma

---