Problema de Josefo

En informática y matemáticas , el problema de Josefo (o permutación de Josefo ) es un problema teórico relacionado con un determinado juego de contar . Estos juegos se utilizan para elegir a una persona de un grupo, por ejemplo, eeny, meeny, miny, moe .

En el particular juego de contar que da origen al problema de Josefo, varias personas están de pie formando un círculo esperando a ser ejecutadas. El conteo comienza en un punto específico del círculo y continúa alrededor del círculo en una dirección específica. Después de que se salta un número específico de personas, se ejecuta a la siguiente persona. El procedimiento se repite con las personas restantes, comenzando con la siguiente persona, yendo en la misma dirección y saltando la misma cantidad de personas, hasta que solo quede una persona y sea liberada.

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

El problema recibe su nombre de Flavio Josefo , un historiador y líder judío que vivió en el siglo I. Según el relato de primera mano de Josefo sobre el asedio de Yodfat , él y sus 40 soldados fueron atrapados en una cueva por soldados romanos . Eligieron el suicidio en lugar de ser capturados y decidieron un método serial de cometer suicidio por sorteo. Josefo afirma que por suerte o posiblemente por la mano de Dios, él y otro hombre permanecieron hasta el final y se rindieron a los romanos en lugar de suicidarse. Esta es la historia que se cuenta en el Libro 3, Capítulo 8, parte 7 de La guerra judía de Josefo ( escribiendo sobre sí mismo en tercera persona ):

Pero en esta situación extrema no perdió su sagacidad habitual, sino que, confiando en la providencia de Dios, arriesgó su vida de la siguiente manera: «Y ahora -dijo-, ya que entre vosotros está decidido que vais a morir, vamos a poner nuestra muerte mutua a suerte. Aquel a quien le caiga primero, que muera el que le caiga después, y así la fortuna hará su progreso entre todos nosotros; y ninguno de nosotros morirá por su propia mano derecha, porque sería injusto que, cuando los demás hayan muerto, alguien se arrepienta y se salve». Esta propuesta les pareció muy justa, y cuando los convenció de que se decidiera por suertes, sacó una de las suertes para él también. El que había caído primero puso su cuello desnudo ante el que había caído después, suponiendo que el general moriría entre ellos inmediatamente, pues pensaban que la muerte, si Josefo podía morir con ellos, era más dulce que la vida. Sin embargo, quedó con otro hasta el final, ya sea que haya sucedido por casualidad o por la providencia de Dios. Y como no deseaba que la suerte lo condenara ni, si hubiera quedado hasta el final, manchar su mano derecha con la sangre de sus compatriotas, lo persuadió a que le confiara su fidelidad y viviera tan bien como él.

—  Josefo sf, p. 579, Guerras de los judíos, Libro III, Cap. 8, párrafo 7

Los detalles del mecanismo utilizado en esta hazaña son bastante vagos. Según James Dowdy y Michael Mays, ^[2] en 1612 Claude Gaspard Bachet de Méziriac sugirió el mecanismo específico de organizar 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 a menudo y los detalles específicos varían considerablemente de una fuente a otra. Por ejemplo, Israel Nathan Herstein e Irving Kaplansky (1974) hacen que Josefo y 39 compañeros se coloquen en un círculo y que cada séptimo hombre sea eliminado. ^[4] Se puede encontrar una historia del problema en la Carta de SL Zabell al editor de Fibonacci Quarterly . ^[5]

En cuanto a la intencionalidad, Josefo preguntó: “¿Debemos atribuirlo a la divina providencia o simplemente a la suerte?” ^[6] Pero el manuscrito eslavo superviviente de Josefo cuenta una historia diferente: que “contó los números astutamente y así logró engañar a todos los demás”. ^{[6] [7]} Josefo tenía un cómplice; el problema era entonces encontrar los lugares de los dos últimos supervivientes restantes (cuya conspiración aseguraría su supervivencia). Se alega que se colocó a sí mismo y al otro hombre en el puesto 31 y 16 respectivamente (para k = 3 a continuación). ^[8]

Una versión medieval del problema de Josefo involucra a 15 turcos y 15 cristianos a bordo de un barco en medio de una tormenta que se hundirá a menos que la mitad de los pasajeros sean arrojados por la borda. Los 30 se colocan en un círculo y cada novena persona debe ser arrojada al mar. Los cristianos deben determinar dónde pararse para asegurarse de que solo los turcos sean arrojados. ^[9] En otras versiones, los roles de turcos y cristianos se intercambian.

Graham, Knuth y Patashnik 1989, p. 8 describen y estudian una variante "estándar": determinar dónde se encuentra el último sobreviviente si hay n personas para comenzar y cada segunda persona ( k = 2 a continuación) es eliminada.

Una generalización de este problema es la siguiente. Se supone que cada m ésima persona será ejecutada de un grupo de tamaño n , en el que la p ésima persona es la sobreviviente. Si hay una adición de x personas al círculo, entonces la sobreviviente está en la p + mx -ésima posición si esta es menor o igual a n + x . Si x es el valor más pequeño para el cual p + mx > n + x , entonces la sobreviviente está en la posición ( p + mx ) − ( n + x ) . ^[10]

En lo sucesivo, denota el número de personas en el círculo inicial y denota el recuento para cada paso, es decir, se omiten personas y se ejecuta el -ésimo. Las personas en el círculo están numeradas de a , siendo la posición inicial y siendo el recuento inclusive . ${\estilo de visualización n}$${\estilo de visualización k}$${\estilo de visualización k-1}$${\estilo de visualización k}$${\estilo de visualización 1}$${\estilo de visualización n}$${\estilo de visualización 1}$

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

Si el número inicial de personas fuera par, entonces la persona en la posición x durante la segunda vuelta alrededor del círculo estaba originalmente en la posición (para cada elección de x ). Sea . La persona que ahora sobrevivirá estaba originalmente en la posición . Esto da como resultado la recurrencia${\estilo de visualización 2x-1}$${\estilo de visualización n=2j}$${\estilo de visualización f(j)}$${\estilo de visualización 2f(j)-1}$

${\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 . Esto produce la recurrencia ${\estilo de visualización 2x+1}$

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

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

Esto sugiere que es una secuencia impar creciente que se reinicia con siempre que el índice n sea una potencia de 2. Por lo tanto, si se eligen m y l de modo que y , entonces . Está claro que los valores de la tabla satisfacen esta ecuación. O se puede pensar que después de que mueren l personas solo hay personas y se llega a la st persona. Esta persona debe ser la sobreviviente. Entonces . A continuación, se da una prueba por inducción . ${\displaystyle f(n)}$${\displaystyle f(n)=1}$$Estilo de visualización n=2^{m}+l}$${\displaystyle 0\leq l<2^{m}}$${\displaystyle f(n)=2l+1}$${\estilo de visualización 2^{m}}$${\estilo de visualización 2l+1}$${\displaystyle f(n)=2l+1}$

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

Demostración: Se utiliza la inducción fuerte en n . El caso base es verdadero. Los casos se consideran por separado cuando n es par y cuando n es impar. ${\estilo de visualización n=1}$

Si n es par, entonces elija y tales que y . Nótese que . se tiene donde la segunda igualdad se sigue de la hipótesis de inducción. $estilo de visualización l_{1}}$$Estilo de visualización m_{1}$${\displaystyle n/2=2^{m_{1}}+l_{1}}$${\displaystyle 0\leq l_{1}<2^{m_{1}}}$$Estilo de visualización l_{1}=l/2$${\displaystyle f(n)=2f(n/2)-1=2((2l_{1})+1)-1=2l+1}$

Si n es impar, entonces elija y de manera que y . Nótese que . se cumple donde la segunda igualdad se sigue de la hipótesis de inducción. Esto completa la prueba. $estilo de visualización l_{1}}$$Estilo de visualización m_{1}$${\displaystyle (n-1)/2=2^{m_{1}}+l_{1}}$${\displaystyle 0\leq l_{1}<2^{m_{1}}}$$Estilo de visualización l_{1}=(l-1)/2}$${\displaystyle f(n)=2f((n-1)/2)+1=2((2l_{1})+1)+1=2l+1}$

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 del tamaño n : se puede obtener mediante un desplazamiento cíclico de un bit hacia la izquierda del propio n . Si n se representa en binario como , entonces la solución viene dada por . La prueba de esto se desprende de la representación de n como o de la expresión anterior para . ${\displaystyle f(n)}$${\displaystyle n=1b_{1}b_{2}b_{3}\puntos b_{m}}$${\displaystyle f(n)=b_{1}b_{2}b_{3}\puntos b_{m}1}$$Estilo de visualización 2^{m}+l}$${\displaystyle f(n)}$

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

Ahora bien, si el número se representa en formato binario, el primer bit denota y los bits restantes denotarán l . Por ejemplo, cuando ⁠ ⁠ , su representación binaria es: ${\estilo de visualización 2^{m}}$${\estilo de visualización n=41}$

n = 1 0 1 0 0 1
2m    = 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 . lowestOneBit ( n ); return 2 * valueOfL + 1 ; }    
	
	     
	      

La forma más sencilla de encontrar la posición segura es mediante el uso de operadores bit a bit . En este enfoque, desplazar el bit más significativo del conjunto n al bit menos significativo devolverá la posición segura. ^{[11] La entrada debe ser un} entero positivo .

n = 1 0 1 0 0 1
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 . lowestOneBit ( n * 2 ) & (( n << 1 ) | 1 ); // ---------------------- --- | ------------ // Obtener el primer bit del conjunto | | Desplazar n a la izquierda y voltear el último bit // y tomar su complemento | | // | | // Multiplicar n por 2 | // Bit a bit Y copiar bits existe en ambos operandos. }    
         
    
    
    
    
    
    

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

${\displaystyle \alpha \aprox 0,8111...}$

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

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

Para todos . ${\displaystyle n\geq 5}$

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

${\displaystyle m^{\prime }\approx \operatorname {redondo} (\log _{3/2}41/0,8111)\approx \operatorname {redondo} (9,68)=10}$

${\displaystyle \operatorname {redondo} (\alpha \cdot (3/2)^{m^{\prime }})\approx \operatorname {redondo} (0,8111\cdot (3/2)^{10})=47}$y por lo tanto${\estilo de visualización m=9}$

${\displaystyle \operatorname {redondo} (0,8111\cdot (3/2)^{9})\approx \operatorname {redondo} (31,18)=31}$(tenga en cuenta que este valor se ha redondeado hacia abajo)

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

Esto se puede verificar mirando cada pasada sucesiva de los números.1 a través de41 :

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

En el caso general, se utiliza programación dinámica para resolver este problema, realizando el primer paso y luego utilizando la solución del problema restante. Cuando el índice comienza en uno, entonces la persona en se desplaza desde la primera persona que está en la posición , donde n es el número total de personas. Sea la posición del sobreviviente. Después de que muere la -ésima persona, queda un círculo de y el siguiente conteo comienza con la persona cuyo número en el problema original era . La posición del sobreviviente en el círculo restante sería si el conteo comienza en ; desplazar esto para tener en cuenta el hecho de que el punto de inicio es produce la recurrencia ^[12]${\estilo de visualización s}$${\displaystyle ((s-1){\bmod {n}})+1}$${\displaystyle f(n,k)}$${\estilo de visualización k}$${\estilo de visualización n-1}$${\displaystyle (k{\bmod {n}})+1}$${\displaystyle f(n-1,k)}$${\estilo de visualización 1}$${\displaystyle (k{\bmod {n}})+1}$

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

que toma la forma más simple

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

si las posiciones están numeradas de a en su lugar. ${\estilo de visualización 0}$${\estilo de visualización n-1}$

Este enfoque tiene tiempo de ejecución , pero para los pequeños y grandes hay otro enfoque. El segundo enfoque también utiliza programación dinámica, pero tiene tiempo de ejecución . Se basa en considerar matar a las k -ésimas, 2 k -ésimas, ..., -ésimas personas como un solo paso, y luego cambiar la numeración. ^{[ cita requerida ]}${\displaystyle O(n)}$${\estilo de visualización k}$${\estilo de visualización n}$${\displaystyle O(k\log n)}$${\displaystyle (\lfloor n/k\rfloor k)}$

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(n-\left\lfloor {\frac {n}{k}}\right\rfloor ,k)-n{\bmod {k}}+n&{\text{if }}g(n-\left\lfloor {\frac {n}{k}}\right\rfloor ,k)<n{\bmod {k}}\\\lfloor {\frac {k(g(n-\left\lfloor {\frac {n}{k}}\right\rfloor ,k)-n{\bmod {k}})}{k-1}}\rfloor &{\text{if }}g(n-\left\lfloor {\frac {n}{k}}\right\rfloor ,k)\geq n{\bmod {k}}\end{Bmatrix}}&{\text{if }}k\leq n\\\end{cases}}}$

• Juego de Flavio Josefo (Applet de Java) en cut-the-knot que permite la selección de cada n- ^ésimo de 50 (máximo).
• Weisstein, Eric W. "El problema de Josefo". MundoMatemático .
• El problema de Josefo - Numberphile en YouTube
• Problema generalizado de Josefo