problema de Josefo

Pregunta de conteo matemático

La interpretación de Claude Gaspar Bachet de Méziriac del problema de Josefo con 41 soldados y un tamaño de paso de 3, que muestra que los lugares 16 y 31 son los últimos en morir; el tiempo avanza hacia adentro a lo largo de la espiral, los puntos verdes indican soldados vivos, soldados grises muertos , y cruza asesinatos

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 conteo . Estos juegos se utilizan para seleccionar a una persona de un grupo, por ejemplo, eeny, meeny, miny, moe .

Un dibujo de la secuencia del problema de Josefo para 500 personas y un valor de omisión de 6. El eje horizontal es el número de la persona. El eje vertical (de arriba a abajo) es el tiempo (el número de ciclo). Una persona viva se dibuja en verde, una muerta se dibuja en negro. ^[1]

En el particular juego de contar que da lugar al problema de Josefo, varias personas están paradas en círculo esperando 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 omitir un número específico de personas, se ejecuta a la siguiente persona. El procedimiento se repite con las personas restantes, empezando por la siguiente, yendo en la misma dirección y saltando el mismo número de personas, hasta que solo quede una persona, que es 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.

Historia

El problema lleva el nombre de Flavio Josefo , un historiador 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 quedaron atrapados en una cueva por soldados romanos . Eligieron el suicidio antes que la captura y optaron por un método en serie para suicidarse mediante 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 de sí mismo en tercera persona ):

Sin embargo, en esta extrema angustia, no carecía de su habitual sagacidad; pero confiando en la providencia de Dios, puso su vida en peligro [de la siguiente manera]: "Y ahora", dijo, "ya que entre vosotros está decidido que moriréis, vamos, comprometámonos mutuamente muertes a determinación por suerte Aquel a quien le toca la suerte primero, que sea matado por el que tiene la segunda suerte, y así la fortuna progresará a través de todos nosotros, ni ninguno de nosotros perecerá por su propia mano derecha; Sería injusto que, cuando los demás se hayan ido, alguien se arrepintiera y se salvara". Esta propuesta les pareció muy justa; y cuando los hubo persuadido para que determinaran este asunto por sorteo, echó también una de las suertes para él. El que tuvo la primera suerte puso al descubierto su cuello al que tuvo la siguiente, como suponiendo que el general moriría entre ellos inmediatamente; porque pensaban que la muerte, si Josefo podía morir con ellos, era más dulce que la vida; sin embargo, estaba con otro dejado para el final, ya sea que debamos decir que sucedió por casualidad o por la providencia de Dios. Y como deseaba mucho no ser condenado por la suerte ni, si lo dejaban para el último, embeber su mano derecha en la sangre de sus compatriotas, lo persuadió a confiarle su fidelidad y a vivir. así como él mismo.

—  Josefo sf, pág. 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 disponer a los hombres en 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) tienen a Josefo y 39 camaradas parados en un círculo y uno de cada siete hombres es eliminado. ^[4] Se puede encontrar una historia del problema en la carta de SL Zabell al editor del Fibonacci Quarterly . ^[5]

En cuanto a la intencionalidad, Josefo preguntó: "¿Lo atribuiremos a la divina providencia o simplemente a la suerte?" ^[6] Pero el manuscrito eslavo superviviente de Josefo cuenta una historia diferente: que él “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 entonces era encontrar los lugares de los dos últimos supervivientes (cuya conspiración aseguraría su supervivencia). Se alega que se ubicó a sí mismo y al otro hombre en el lugar 31 y 16 respectivamente (para k = 3 a continuación). ^[8]

Variantes y generalizaciones

Variante del problema de Josefo con 30 personas y un tamaño de paso de 9: el tiempo avanza hacia adentro a lo largo de la espiral, los puntos verdes indican soldados vivos, soldados grises muertos y cruces asesinadas.

Una versión medieval del problema de Josefo involucra a 15 turcos y 15 cristianos 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 paran en círculo y cada novena persona será arrojada al mar. Los cristianos necesitan determinar dónde situarse para garantizar que sólo los turcos sean expulsados. ^[9] En otras versiones se intercambian los roles de turcos y cristianos.

Graham, Knuth y Patashnik 1989, pág. 8 describe y estudia una variante "estándar": determine dónde se encuentra el último superviviente si hay n personas para comenzar y se elimina una de cada dos personas ( k = 2 a continuación).

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 el superviviente. Si se agregan x personas al círculo, entonces el sobreviviente está en la posición p + mx -ésima si es menor o igual que n + x . Si x es el valor más pequeño para el cual p + mx > n + x , entonces el superviviente está en la posición ( p + mx ) − ( n + x ) . ^[10]

Solución

Lugares penúltimo (rosa) y último (ultramarino) en el problema de Josefo para varios tamaños de grupo, n y tamaños de paso, k . En el archivo SVG, coloque el cursor sobre los valores para mostrar el orden completo de eliminación.

A continuación, denota el número de personas en el círculo inicial y denota el recuento de cada paso, es decir, se omiten las personas y se ejecuta el -ésimo. Las personas en el círculo están numeradas desde hasta , siendo la posición inicial y el conteo inclusivos . ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle k-1}$ ${\displaystyle k}$ ${\displaystyle 1}$ ${\displaystyle n}$ ${\displaystyle 1}$

k = 2

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

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 (para cada elección de x ). Dejar . La persona que ahora sobrevivirá estaba originalmente en el puesto . Esto produce la recurrencia ${\displaystyle 2x-1}$ ${\displaystyle n=2j}$ ${\displaystyle f(j)}$ ${\displaystyle 2f(j)-1}$

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

Si el número inicial de personas era impar , entonces se puede considerar que la persona 1 muere al final de la primera vuelta al círculo. Nuevamente, durante la segunda vuelta al círculo, la nueva segunda persona muere, luego la nueva cuarta persona, etc. En este caso, la persona en la posición x estaba originalmente en la posición . Esto produce la recurrencia ${\displaystyle 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): ${\displaystyle n}$ ${\displaystyle f(n)}$

Esto sugiere que es una secuencia impar creciente que se reinicia siempre que el índice n es una potencia de 2 . Por lo tanto, si m y l se eligen 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 quedan personas y pasa a la primera persona. Esta persona debe ser el superviviente. Entonces . A continuación se da una prueba por inducción . ${\displaystyle f(n)}$ ${\displaystyle f(n)=1}$ ${\displaystyle n=2^{m}+l}$ ${\displaystyle 0\leq l<2^{m}}$ ${\displaystyle f(n)=2l+1}$ ${\displaystyle 2^{m}}$ ${\displaystyle 2l+1}$ ${\displaystyle f(n)=2l+1}$

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

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

Si n es par, entonces elija y tal que y . Tenga en cuenta que . se tiene donde la segunda igualdad se deriva de la hipótesis de inducción. ${\displaystyle l_{1}}$ ${\displaystyle m_{1}}$ ${\displaystyle n/2=2^{m_{1}}+l_{1}}$ ${\displaystyle 0\leq l_{1}<2^{m_{1}}}$ ${\displaystyle 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 tal que y . Tenga en cuenta que . se tiene donde la segunda igualdad se deriva de la hipótesis de inducción. Esto completa la prueba. ${\displaystyle l_{1}}$ ${\displaystyle m_{1}}$ ${\displaystyle (n-1)/2=2^{m_{1}}+l_{1}}$ ${\displaystyle 0\leq l_{1}<2^{m_{1}}}$ ${\displaystyle 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 deduce 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}\dots b_{m}}$ ${\displaystyle f(n)=b_{1}b_{2}b_{3}\dots b_{m}1}$ ${\displaystyle 2^{m}+l}$ ${\displaystyle f(n)}$

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

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

norte = 1 0 1 0 0 12 metros = 1 0 0 0 0 0l = 0 1 0 0 1

/** * @param n el número de personas paradas en el círculo * @return la posición segura quién 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 . mayorUnBit ( n ); devolver 2 * valorDeL + 1 ; }              

Bit a bit

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

norte = 1 0 1 0 0 1norte = 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 . mayorUnBit ( n * 2 ) & (( n << 1 ) | 1 ); // ---------------------- --- | ------------ // Obtener el primer bit establecido | | Mayús a la izquierda n y volteando el último bit // y tomando su complemento | | // | | // Multiplica n por 2 | // Bit a bit Y para copiar bits existe en ambos operandos. }                

k = 3

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 \approx 0.8111...}$

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

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

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

${\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 esto se ha redondeado hacia abajo)

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

Esto se puede verificar observando cada paso sucesivo 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

El caso general

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 que se desplaza desde la primera persona está en la posición , donde n es el número total de personas. Denotemos la posición del superviviente. Después de matar a la -ésima persona, queda un círculo y el siguiente conteo se inicia con la persona cuyo número en el problema original era . La posición del superviviente en el círculo restante sería si el conteo se iniciara en ; cambiar esto para tener en cuenta el hecho de que el punto de partida es produce la recurrencia ^[12] ${\displaystyle s}$ ${\displaystyle ((s-1){\bmod {n}})+1}$ ${\displaystyle f(n,k)}$ ${\displaystyle k}$ ${\displaystyle n-1}$ ${\displaystyle (k{\bmod {n}})+1}$ ${\displaystyle f(n-1,k)}$ ${\displaystyle 1}$ ${\displaystyle (k{\bmod {n}})+1}$

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

que toma la forma más simple

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

si las posiciones están numeradas desde hasta . ${\displaystyle 0}$ ${\displaystyle n-1}$

Este enfoque tiene tiempo de ejecución , pero para pequeños y grandes existe otro enfoque. El segundo enfoque también utiliza programación dinámica pero tiene tiempo de ejecución . Se basa en considerar matar a k -ésima, 2 k -ésima, ..., -ésima gente como un paso y luego cambiar la numeración. ^{[ cita necesaria ]} ${\displaystyle O(n)}$ ${\displaystyle k}$ ${\displaystyle 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}}}$

Referencias

Citas

1. R. Ugalde, Laurence. "Problema de Josephus en el lenguaje de programación Fōrmulæ". Fórmulas . Consultado el 26 de julio de 2021 .
2. Dowdy y Mays 1989, pág. 125.
3. Bachet 1612, pag. 174.
4. Herstein y Kaplansky 1974, págs. 121-126.
5. Zabell 1976, págs.48, 51.
6. Cohen, Richard. Haciendo historia: los narradores que dieron forma al pasado , p. 54 (Simon y Schuster 2022).
7. https://gustavus.edu/mcs/max/concrete-abstractions-pdfs/chapter3.pdf
8. Despertar bola 1905, pag. 19.
9. Newman 1988, págs. 2403-2405.
10. Robinson 1960, págs. 47–52.
11. "Problema de Josephus al utilizar la operación bit a bit (Java)". GitHub . 7 de enero de 2018 . Consultado el 7 de enero de 2018 .
12. Parque y Teixeira 2018, págs. 1–7.

Fuentes

• Bachet, CG (1612). Problemes Plaisants ed Delectables qui se font par les Nombres (en francés).
• Graham, RL; Knuth, DE ; Patashnik, O. (1989). Matemáticas concretas: una base para la informática . Addison Wesley. ISBN 978-0-201-14236-5.
• Herstein, IN; Kaplansky, I. (1974). Asuntos Matemáticos . Harper y Row. ISBN 9780060428037.
• Josefo, Flavio (sin fecha). Las obras de Flavio Josefo: en tres volúmenes; con ilustraciones. Traducido por William Whiston. Londres: George Routledge & Sons.
• Newman, JR (1988). El mundo de las matemáticas . vol. 4. Tempus.
• Park, Jang Woo; Teixeira, Ricardo (2018). "Problema de Josefo de ejecución en serie". Coreano J. Matemáticas . 26 (1): 1–7. doi :10.11568/kjm.2018.26.1.1.
• Robinson, WJ (1960). "El problema de Josefo". Matemáticas. Gaz . 44 (347): 47–52. doi :10.2307/3608532. JSTOR  3608532. S2CID  125735054.
• Bola de Rouse, WW (1905). Recreaciones y ensayos matemáticos (2ª ed.). Londres: Macmillan.
• Zabell, SL (1976). «Carta al editor» (PDF) . Fibonacci trimestral . 14 : 48–51.

Otras lecturas

• Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001). "Capítulo 14: Aumento de las estructuras de datos". Introducción a los algoritmos (Segunda ed.). MIT Press y McGraw-Hill. pag. 318.ISBN​ 0-262-03293-7.
• Desaliñado, James; Mays, Michael E. (1989). "Permutaciones de Josefo". Revista de Matemática Combinatoria y Computación Combinatoria . 6 : 125-130.
• Halbeisen, L.; Hungerbühler, N. (1997). "El problema de Josefo". J. Théor. Nombres Burdeos . 9 (2): 303–318. doi : 10.5802/jtnb.204 .
• Jakóbczyk, F. (1973). "Sobre el problema generalizado de Josefo". Matemáticas de Glasgow. J.​ 14 (2): 168-173. doi : 10.1017/S0017089500001919 . S2CID  122980022.
• Lloyd, Errol L. (1983). "Un algoritmo O (n logm) para el problema de Josefo". J. Algor . 4 (3): 262–270. doi :10.1016/0196-6774(83)90025-1.
• Odlyzko, Andrew M.; Wilf, Herbert S. (1991). "Iteración funcional y el problema de Josefo". Matemáticas de Glasgow. J.​ 33 (2): 235–240. doi : 10.1017/S0017089500008272 . S2CID  123160551.
• Ruskey, Frank; Williams, Aarón (2010). "El problema del felino Josefo". Lectura. No. comp. Ciencia . Apuntes de conferencias sobre informática. 6099 : 343–354. Código Bib : 2010LNCS.6099..343R. doi :10.1007/978-3-642-13122-6_33. ISBN 978-3-642-13121-9.DIVERSIÓN2010
• Ruskey, Frank; Williams, Aarón (2012). "El problema del felino Josefo". Computación teórica. Sistema . 50 : 20–34. CiteSeerX  10.1.1.157.2956 . doi :10.1007/s00224-011-9343-6. S2CID  2273820.
• Sullivan, Shaun; Insko, Erik (2018). "Una variante del problema del felino Josefo". arXiv : 1803.11340 [matemáticas.CO].
• Theriault, Nicolas (2001). "Generilizaciones del problema de Josefo". Útil. Matemáticas. (58): 161-173. CiteSeerX  10.1.1.164.2015 .
• Woodhouse, David (1973). "El problema extendido de Josefo". Rev. Mat. Hisp.-Amer . 33 (4): 207–218.

enlaces externos

• Juego Josephus Flavius ​​(Java Applet) para cortar el nudo que permite la selección de cada ^ené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