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 .
La gente está parada en un círculo esperando ser ejecutada. 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 omite un número específico de personas, se ejecuta la siguiente persona. El procedimiento se repite con el resto de personas, comenzando por la siguiente, yendo en la misma dirección y saltando el mismo número de personas, hasta que solo queda una persona y se libera.
El problema, dado el número de personas, el punto de partida, la dirección y el número que se debe omitir, es elegir la posición en el círculo inicial para evitar la ejecución.
Historia
El problema lleva el nombre de Flavius Josephus , un historiador judío que vivió en el siglo I. Según el relato de Josefo sobre el sitio de Yodfat , él y sus 40 soldados fueron atrapados en una cueva por soldados romanos . Eligieron el suicidio antes que la captura y se decidieron por un método en serie de 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 da 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 estaba desprovisto de su sagacidad habitual; pero confiando en la providencia de Dios, arriesgó su vida [de la siguiente manera]: "Y ahora", dijo, "ya que entre vosotros está resuelto que moriréis, vamos, cometamos nuestro mutuo Muertes a la determinación por sorteo. Aquel a quien le corresponda la suerte primero, que lo mate 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, porque sería injusto si, cuando el resto se haya ido, alguien se arrepienta y se salve ". Esta propuesta les pareció muy justa; y cuando hubo vencido con ellos para resolver este asunto por sorteo, echó también uno de los sorteos para él. El que tenía la primera suerte le mostró el cuello al que tenía la siguiente, como suponiendo que el general moriría entre ellos inmediatamente; porque pensaban que la muerte, si Josefo pudiera morir con ellos, era más dulce que la vida; sin embargo, él estaba con otro dejado para el último, ya sea que digamos que sucedió por casualidad, o por la providencia de Dios. Y como estaba muy deseoso de no ser condenado por sorteo, ni, si se le había dejado para el último, de impregnar su mano derecha en la sangre de sus compatriotas, lo persuadió de que confiara en él su fidelidad y viviera. así como a él mismo.
- Josefo sf , pág. 579, Guerras de los Judíos, Libro III, Cap. 8, párr. 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 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 camaradas formen un círculo con cada séptimo hombre eliminado. [4] Se puede encontrar una historia del problema en la Carta de SL Zabell al editor del Fibonacci Quarterly . [5]
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 lugar 31 y 16 respectivamente (para k = 3 a continuación). [6]
Variantes y generalizaciones
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 caigan por la borda. Los 30 forman un círculo y cada novena persona debe ser arrojada al mar. Los cristianos deben determinar dónde pararse para asegurarse de que solo se arroje a los turcos. [7] En otras versiones, los roles de turcos y cristianos se intercambian.
Graham, Knuth y Patashnik 1989 , pág. 8 describe y estudia una variante "estándar": determina dónde se encuentra el último superviviente si hay n personas para comenzar y se elimina cada segunda persona ( k = 2 a continuación).
Una generalización de este problema es la siguiente. Se supone que cada m persona será ejecutada de un grupo de tamaño n , en el que la p ésima persona es la superviviente. Si hay una adición de x personas al círculo, entonces el superviviente 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 ) . [8]
Solución
En el siguiente, denota el número de personas en el círculo inicial, y denota el recuento de cada paso, es decir, la gente se salta y el -th se ejecuta. Las personas en el círculo están numeradas desde a , siendo la posición inicial y el conteo es inclusivo .
k = 2
El problema se resuelve explícitamente cuando cada segunda persona muere, es decir . (Para el caso más general, a continuación se describe una solución). La solución se expresa de forma recursiva. Dejar denotar la posición del superviviente cuando inicialmente hay gente y ). La primera vez que se da la vuelta al círculo, todas las personas pares mueren. La segunda vez alrededor del círculo, la nueva segunda persona muere, luego la nueva cuarta persona, etc .; es como si no hubiera una primera vuelta al círculo.
Si el número inicial de personas era par, entonces la persona en posición durante la segunda vuelta al círculo estaba originalmente en posición (para cada elección de ). Dejar. La persona en quien sobrevivirá ahora estaba originalmente en posición . Esto produce la recurrencia
Si el número inicial de personas era impar, entonces se puede pensar que la persona 1 está muriendo 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 posición estaba originalmente en posición . Esto produce la recurrencia
Cuando se tabulan los valores de y emerge un patrón: OEIS : A006257
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | dieciséis | |
1 | 1 | 3 | 1 | 3 | 5 | 7 | 1 | 3 | 5 | 7 | 9 | 11 | 13 | 15 | 1 |
Esto sugiere que es una secuencia cada vez más extraña que se reinicia con siempre que el índice n es una potencia de 2. Por lo tanto, si m y l se elige de manera que y , luego . Está claro que los valores de la tabla satisfacen esta ecuación. O se puede pensar que después la gente esta muerta solo hay gente y va a la a persona. Esta persona debe ser la sobreviviente. Entonces. A continuación, se da una prueba por inducción.
Teorema: Si y , luego .
Prueba: la inducción fuerte se utiliza en. El caso basees verdad. Los casos se consideran por separado cuando es par y cuando es impar.
Si es par, luego elige y tal que y . Tenga en cuenta que. se tiene donde la segunda igualdad se sigue de la hipótesis de inducción.
Si es extraño, entonces elige y tal que y . Tenga en cuenta que. se tiene donde la segunda igualdad se sigue de la hipótesis de inducción. Esto completa la prueba.
se puede resolver para obtener una expresión explícita para :
La forma más elegante de la respuesta implica la representación binaria del tamaño : puede obtenerse mediante un desplazamiento cíclico de un bit a la izquierda de sí mismo. Si se representa en binario como , entonces la solución viene dada por . La prueba de esto se deriva de la representación de como o de la expresión anterior para .
Implementación: si n denota el número de personas, la posición segura viene dada por la función, dónde y .
Ahora, si el número está representado en formato binario, el primer bit denota y los bits restantes denotarán . 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
/ ** * * @param n el número de personas paradas en el círculo * @return la posición segura que sobrevivirá 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 ); int safePosition = 2 * valueOfL + 1 ;return safePosition ; }
Bit a bit
La forma más sencilla de encontrar la posición segura es utilizando operadores bit a bit. En este enfoque, cambiar el bit de conjunto más significativo de n al bit menos significativo devolverá la posición segura. [9] La entrada debe ser un número entero positivo.
n = 1 0 1 0 0 1
n = 0 1 0 0 1 1
/ ** * * @param n (41) el número de personas paradas en el círculo * @return la posición segura que sobrevivirá a la ejecución * ~ Integer.highestOneBit (n * 2) * Multiplica n por 2, obtén el primer conjunto bit y tomar su complemento * ((n << 1) | 1) * Left Shift ny voltear el último bit * ~ Integer.highestOneBit (n * 2) & ((n << 1) | 1) * Bitwise And to los bits de copia existen en ambos operandos. * / public int getSafePosition ( int n ) { return ~ Integer . más altoOneBit ( n * 2 ) & (( n << 1 ) | 1 ); }
k = 3
En 1997, Lorenz Halbeisen y Norbert Hungerbühler descubrieron una forma cerrada para el caso . Demostraron que hay una cierta constante
que se puede calcular con precisión arbitraria. Dada esta constante, elija ser el mayor entero tal que (esto será o ). Entonces, el sobreviviente final es
- si lo demás está redondeado
para todos .
Como ejemplo de cálculo, Halbeisen y Hungerbühler dan (que es en realidad la formulación original del problema de Josefo). Ellos calculan:
- y por lo tanto
- (tenga en cuenta que esto se ha redondeado hacia abajo)
Esto se puede verificar observando cada pase sucesivo de los números. mediante :
El caso general
La programación dinámica se usa para resolver este problema en el caso general realizando el primer paso y luego usando la solución del problema restante. Cuando el índice comienza desde uno, entonces la persona en cambios de la primera persona está en posición , donde n es el número total de personas. Dejardenotar la posición del superviviente. Después de la-a persona muere, un círculo de permanece, y el siguiente recuento 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 inicia en ; cambiando esto para tener en cuenta el hecho de que el punto de partida esproduce la recurrencia [10]
que toma la forma más simple
si las posiciones están numeradas desde a en lugar de.
Este enfoque tiene tiempo de ejecución , pero para pequeños y largo hay otro enfoque. El segundo enfoque también usa programación dinámica pero tiene tiempo de ejecución. Se basa en considerar matar k -th, 2 k -th, ...,-th personas como un paso, luego cambiando la numeración. [ cita requerida ]
Este enfoque mejorado toma la forma
Referencias
Citas
- ^ Problema de Josefo . Una solución al problema de la tarea Josefo en el Código Rosetta , escrito en Fōrmulæ. La wiki de Fōrmulæ . Consultado el 19 de septiembre de 2019.
- ^ Dowdy y Mays 1989 , p. 125.
- ^ Bachet 1612 , pág. 174.
- ^ Herstein y Kaplansky 1974 , págs. 121-126.
- ^ Zabell 1976 , págs.48, 51.
- ↑ Rouse Ball , 1905 , pág. 19.
- ^ Newman 1988 , págs. 2403-2405.
- ^ Robinson 1960 , págs. 47-52.
- ^ "Problema de Josefo utilizando la operación bit a bit (Java)" . GitHub . 7 de enero de 2018 . Consultado el 7 de enero de 2018 .
- ^ Park 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). Materias Matemáticas . Harper y Row.
- Josefo (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 . 4 . Tempus.
- Park, Jang-Woo; Teixeira, Ricardo (2018). "Ejecución en serie Problema de Josefo". Coreano J. Math . 26 (1): 1–7. doi : 10.11568 / kjm.2018.26.1.1 .
- Robinson, WJ (1960). "El problema de Josefo". Matemáticas. Gaceta . 44 (347): 47–52. doi : 10.2307 / 3608532 . JSTOR 3608532 .
- Rouse Ball, WW (1905). Recreaciones y ensayos matemáticos (2ª ed.). Londres: Macmillan.
- Zabell, SL (1976). "Carta al editor" (PDF) . Fibonacci Quarterly . 14 : 48–51.
Otras lecturas
- Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001). "Capítulo 14: Aumentar las estructuras de datos". Introducción a los algoritmos (Segunda ed.). MIT Press y McGraw-Hill. pag. 318. ISBN 0-262-03293-7.
- Dowdy, 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 Bordeaux . 9 (2): 303–318. doi : 10.5802 / jtnb.204 .
- Jakóbczyk, F. (1973). "Sobre el problema generalizado de Josefo". Glasow Math. J . 14 (2): 168-173. doi : 10.1017 / S0017089500001919 .
- 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 .
- Ruskey, Frank; Williams, Aaron (2010). "El problema felino de Josefo". Lect. No. Comp. Sci . Apuntes de conferencias en informática. 6099 : 343–354. Código Bibliográfico : 2010LNCS.6099..343R . doi : 10.1007 / 978-3-642-13122-6_33 . ISBN 978-3-642-13121-9. FUN2010
- Ruskey, Frank; Williams, Aaron (2012). "El problema felino de Josefo". Computación teórica. Sistemas . 50 : 20–34. doi : 10.1007 / s00224-011-9343-6 . S2CID 2273820 .
- Sullivan, Shaun; Insko, Erik (2018). "Una variante del problema felino de Josefo". arXiv : 1803.11340 [ math.CO ].
- Shams-Baragh, Armin (2002). "Formulación del problema extendido de Josefo" (PDF) . Archivado desde el original (PDF) el 30 de julio de 2018.
- Theriault, Nicolas (2001). "Generilaciones del problema de Josefo". Util. Matemáticas. (58): 161-173.CiteSeer x : 10.1.1.164.2015
- Woodhouse, David (1973). "El problema extendido de Josefo". Rev. Mat. Hisp.-Amer . 33 (4): 207–218.
enlaces externos
- Josephus Flavius juego (Java Applet) en el corte-el-nudo que permite la selección de cada enésimo de 50 (máximo).
- Weisstein, Eric W. "Problema de Josefo" . MathWorld .
- El problema de Josefo - Numberphile en YouTube