31 octubre 2016

El problema de Josephus



El problema de Flavio Josefo es un problema teórico que se encuentra en matemáticas y ciencias informáticas.

El nombre hace referencia a Flavio Josefo, un historiador judío que vivió en el siglo I. Según lo que cuenta Josefo, él y 40 soldados camaradas se encontraban atrapados en una cueva, rodeados de romanos. Prefirieron suicidarse antes que ser capturados y decidieron que echarían a suertes quién mataba a quién. Los últimos que quedaron fueron él y otro hombre. Entonces convenció al otro hombre que debían entregarse a los romanos en lugar de matarse entre ellos. Josefo atribuyó su supervivencia a la suerte o a la Providencia. 
 
El planteamiento general del problema, presupone cualquier número de soldados, n,  y un valor k que indica el salto en cada "asesinato". Por ejemplo, si empieza en el número 1 y k = 3, el primero en desaparecer sería el número 4.
 
Es un clásico problema que se resuelve en los estudios de Programación en cualquier lenguaje.
 
La forma general de atacar el problema consiste en saber dónde debe colocarse Josephus para salvarse (caso general, que dependerá del número n de soldados, del valor de k,  del inicio del proceso y de la posición de Josephus).
 
Si n = 41, k = 3, el resultado final nos dice que Josephus debería ponerse en posicion 31, como puede verse en el siguiente gráfico:



Hay varias versiones  (barca con personas de diferentes religiones...). El juego es bueno para programación y tiene un alto interés y aplicabilidad en el aula

Si quieres ver una simulación interactiva con geogebra,  en la que puedes modificar n y k, visita la siguiente web (de la que he tomado la imagen anterior).



No hay comentarios: