El problema de Josefo

El problema se resuelve explícitamente cuando una de cada dos personas muere (cada persona mata a la persona que está a su izquierda o derecha), es decir${\displaystyle k=2}$. (Para el caso más general${\displaystyle k\neq 2}$(A continuación se describe una solución). La solución se expresa recursivamente . Sea${\displaystyle f(n)}$denotan la posición del superviviente cuando inicialmente hay n personas (y${\displaystyle k=2}$). La primera vuelta al círculo, mueren todas las personas con número par . La segunda vuelta al círculo, muere la nueva segunda persona, luego la nueva cuarta persona, etc.; es como si no hubiera habido una primera vuelta al círculo.

Si el número inicial de personas era par, entonces la persona en la posición x durante la segunda vuelta al círculo estaba originalmente en la posición${\displaystyle 2x-1}$(para cada elección de x ). Sea${\displaystyle n=2j}$La persona en${\displaystyle f(j)}$quien ahora sobrevivirá estaba originalmente en posición${\displaystyle 2f(j)-1}$Esto produce la recurrencia$${\displaystyle f(2j)=2f(j)-1.}$$

Si el número inicial de personas era impar , entonces se puede pensar que la persona 1 muere al final de la primera vuelta al círculo. Nuevamente, durante la segunda vuelta al círculo, muere la nueva 2.ª persona, luego la nueva 4.ª persona, etc. En este caso, la persona en la posición x estaba originalmente en la posición${\displaystyle 2x+1}$Esto produce la recurrencia $${\displaystyle f(2j+1)=2f(j)+1.}$$

Cuando se tabulan los valores de${\displaystyle n}$y${\displaystyle f(n)}$Se observa un patrón ( OEIS : A006257  , también la columna de números azules más a la izquierda en la figura anterior):

Esto sugiere que${\displaystyle f(n)}$es una secuencia extraña creciente que se reinicia con${\displaystyle f(n)=1}$siempre que el índice n sea una potencia de 2. Por lo tanto, si m y l se eligen de manera que${\displaystyle n=2^{m}+l}$y${\displaystyle 0\leq l<2^{m}}$, entonces${\displaystyle f(n)=2l+1}$. Es evidente que los valores de la tabla satisfacen esta ecuación. O se puede pensar que después de que l personas mueren, solo quedan l.${\displaystyle 2^{m}}$gente, y va a la${\displaystyle 2l+1}$primera persona. Esta persona debe ser la superviviente. Entonces${\displaystyle f(n)=2l+1}$A continuación se presenta una demostración por inducción .

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

Prueba: Se utiliza la inducción fuerte sobre n . El caso base${\displaystyle n=1}$Es cierto. Los casos se consideran por separado cuando n es par y cuando n es impar.

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

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

l se puede resolver para obtener una expresión explícita para${\displaystyle f(n)}$: $${\displaystyle f(n)=2(n-2^{\lfloor \log _{2}(n)\rfloor })+1.}$$

La forma más elegante de la respuesta implica la representación binaria de tamaño n :${\displaystyle f(n)}$se puede obtener mediante un desplazamiento cíclico a la izquierda de un bit de n mismo. Si n se representa en binario como${\displaystyle n=1b_{1}b_{2}b_{3}\dots b_{m}}$, entonces la solución viene dada por${\displaystyle f(n)=b_{1}b_{2}b_{3}\dots b_{m}1}$. La prueba de esto se deduce de la representación de n como${\displaystyle 2^{m}+l}$o de la expresión anterior para${\displaystyle f(n)}$.

Implementación: Si n denota el número de personas, la posición segura viene dada por la función${\displaystyle f(n)=2l+1}$, dónde ${\displaystyle n=2^{m}+l}$y${\displaystyle 0\leq l<2^{m}}$.

Ahora bien, si el número se representa en formato binario, el primer bit indica${\displaystyle 2^{m}}$y los bits restantes denotarán l . Por ejemplo, cuando${\displaystyle 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

/** * @param n el número de personas que se encuentran en el círculo * @return la posición segura que sobrevivirá a la ejecución * f(N) = 2L + 1 donde N = 2^M + L y 0 <= L < 2^M */ public int getSafePosition ( int n ) { // encuentra el valor de L para la ecuación int valueOfL = n - Integer . highestOneBit ( n ); return 2 * valueOfL + 1 ; }

n = 1 0 1 0 0 1 f(n) = 0 1 0 0 1 1

/** * @param n (41) el número de personas que se encuentran en el círculo * @return la posición segura que sobrevivirá a la ejecución */ public int getSafePosition ( int n ) { return ~ Integer . highestOneBit ( n * 2 ) & (( n << 1 ) | 1 ); // ---------------------- --- | ------------ // Obtener el primer bit activado | | Desplazar n a la izquierda y voltear el último bit // y tomar su complemento | | // | | // Multiplicar n por 2 | // AND bit a bit para copiar los bits que existen en ambos operandos. }

En 1997, Lorenz Halbeisen y Norbert Hungerbühler descubrieron una forma cerrada para el caso${\displaystyle k=3}$Demostraron que existe una cierta constante.

${\displaystyle \alpha \approx 0.8111...}$

que se puede calcular con precisión arbitraria. Dada esta constante, elija m como el mayor entero tal que${\displaystyle \operatorname {round} (\alpha \cdot (3/2)^{m})\leq n}$(esto será o${\displaystyle m^{\prime }=\operatorname {round} (\log _{3/2}n/\alpha )}$o${\displaystyle m^{\prime }-1}$). Entonces, el último superviviente es

${\displaystyle f(n)=3(n-\operatorname {round} (\alpha \cdot (3/2)^{m}))+(2}$si se redondea hacia arriba de lo contrario${\displaystyle 1)}$

a pesar de${\displaystyle n\geq 5}$.

Como ejemplo de cálculo, Halbeisen y Hungerbühler dan${\displaystyle n=41,k=3}$(que en realidad es la formulación original del problema de Josefo). Calculan:

${\displaystyle m^{\prime }\approx \operatorname {round} (\log _{3/2}41/0.8111)\approx \operatorname {round} (9.68)=10}$

${\displaystyle \operatorname {round} (\alpha \cdot (3/2)^{m^{\prime }})\approx \operatorname {round} (0.8111\cdot (3/2)^{10})=47}$y por lo tanto${\displaystyle m=9}$

${\displaystyle \operatorname {round} (0.8111\cdot (3/2)^{9})\approx \operatorname {round} (31.18)=31}$(tenga en cuenta que este valor se ha redondeado a la baja)

${\displaystyle f(n)=3(41-31)+1=31}$

Esto se puede verificar observando cada pasada sucesiva sobre los números.1 a41 :

1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 22, 23, 25, 26, 28, 29, 31, 32, 34, 35, 37, 38, 40, 41

2, 4, 7, 8, 11, 13, 16, 17, 20, 22, 25, 26, 29, 31, 34, 35, 38, 40

2, 4, 8, 11, 16, 17, 22, 25, 29, 31, 35, 38

2, 4, 11, 16, 22, 25, 31, 35

2, 4, 16, 22, 31, 35

4, 16, 31, 35

16, 31

31

La programación dinámica se utiliza para resolver este problema en el caso general realizando el primer paso y luego utilizando la solución del problema restante. Cuando el índice comienza desde uno, entonces la persona en${\displaystyle s}$cambia desde la primera persona está en posición${\displaystyle ((s-1){\bmod {n}})+1}$donde n es el número total de personas. Sea${\displaystyle f(n,k)}$denotan la posición del superviviente. Después de la${\displaystyle k}$La persona número -es asesinada, un círculo de${\displaystyle n-1}$permanece, y el siguiente conteo se inicia con la persona cuyo número en el problema original era${\displaystyle (k{\bmod {n}})+1}$. La posición del superviviente en el círculo restante sería${\displaystyle f(n-1,k)}$si el conteo se inicia en${\displaystyle 1}$; cambiando esto para tener en cuenta el hecho de que el punto de partida es${\displaystyle (k{\bmod {n}})+1}$produce la recurrencia ^{[ 12 ]}$${\displaystyle f(n,k)={\big (}[f(n-1,k)+k-1]{\bmod {n}}{\big )}+1,{\text{ with }}f(1,k)=1,}$$ que adopta la forma más sencilla $${\displaystyle g(n,k)=[g(n-1,k)+k]{\bmod {n}},{\text{ with }}g(1,k)=0}$$ si las posiciones están numeradas desde${\displaystyle 0}$a${\displaystyle n-1}$en cambio.

Este enfoque tiene tiempo de ejecución${\displaystyle O(n)}$pero para los pequeños${\displaystyle k}$y grande${\displaystyle n}$Existe otro enfoque. El segundo enfoque también utiliza programación dinámica, pero tiene un tiempo de ejecución.${\displaystyle O(k\log n)}$. Se basa en considerar matar al k -ésimo, 2k - ésimo, ...,${\displaystyle (\lfloor n/k\rfloor k)}$-personas como un paso, luego cambiando la numeración.

Este enfoque mejorado toma la forma $${\displaystyle g(n,k)={\begin{cases}0&{\text{if }}n=1,\\(g(n-1,k)+k){\bmod {n}}&{\text{if }}1<n<k,\\{\begin{Bmatrix}g\left(n-\left\lfloor {\frac {n}{k}}\right\rfloor ,k\right)-n{\bmod {k}}+n&{\text{if }}g\left(n-\left\lfloor {\frac {n}{k}}\right\rfloor ,k\right)<n{\bmod {k}}\\\left\lfloor {\dfrac {k\left(g\left(n-\left\lfloor {\frac {n}{k}}\right\rfloor ,k\right)-n{\bmod {k}}\right)}{k-1}}\right\rfloor &{\text{if }}g\left(n-\left\lfloor {\frac {n}{k}}\right\rfloor ,k\right)\geq n{\bmod {k}}\end{Bmatrix}}&{\text{if }}k\leq n.\\\end{cases}}}$$