El problema de Josephus - Fórmula

Hoy en la tarde surgió una pregunta, “¿cómo harías la fórmula para resolver éste problema?”, refiriénsode al “Problema de Flavio Josefo”.

Para ello, aquí el párrafo de dicho problema (extraído de Wikipedia):

El problema de Flavio Josefo es un problema teórico que se encuentra en matemática y ciencias de la computación. El nombre hace referencia a Flavio Josefo, un historiador judío que vivió en elsiglo 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, aunque sabía que no era así.

 

Planteamiento

El problema plantea lo siguiente:

Hay n personas paradas en un círculo esperando a ser ejecutadas. Después de que ejecutan a la primera persona, saltean a k − 1 personas y la persona número k es ejecutada. Entonces nuevamente, saltean a k − 1 personas y la persona número k es ejecutada. La eliminación continúa alrededor del círculo (que se hace cada vez más pequeño a medida que más personas son eliminadas del mismo) hasta que sólo queda la última, que es liberada.

El objetivo es escoger el lugar inicial en el círculo para sobrevivir (es el último que queda), dados n y k.

 

En nuestro caso en particular, el orden de las muertes serían de 2 en 2, es decir, saltando 1 para cada muerte: ejm, si eran 6 las personas, el orden sería:

2, 4, 6, 3, 1, quedando último el 5º

Lo interesante era que dicho resultado vendría a ser una operación binaria de rotación por la izquierda (ROL), es decir:

Si era 6, en binario es 110, al hacer un ROL (operación en Assembler), la rotación de dichos bits quedaría : 101, que en el sistema decimal es 5.

Rotate Left

 El objetivo que planteamos, era la de realizar una fórmula cuyo valor ingresado sea el número de personas, y el resultado sea precísamente la última persona.

El encontrar el resultado era muy sencillo, bastaba con realizar dichas operaciones binarias, sin embargo, en las matemáticas utilizando fórmulas no era tan sencillo a simple vista.

Del ejemplo mostrado, del número de personas 6, quedaba el 5º tan sólo bastaba con realizar una rotación binaria, pero para convertirlo a una función, era necesario realizar los siguientes pasos:

Tenemos el valor 6 en binario: 

110

a ello le debíamos recorrer a la izquierda en un bit

1100

finalmente el bit más significativo (posición 4 desde la derecha) debíamos colocarlo en lugar del 0 en la primera posición, quedando

101

recordando aquellas veces que programa en segmentos de memoria para gráficos en assembler, se me vino a la mente que el multiplicar por 2 en binario, tan sólo resulta ser el recorrer los bits a la izquierda en uno tal como se hizo arriba, por tanto ya teníamos una parte de la fórmula:

6x2 = 12 (en binario 1100)

luego para eliminar el bit 4 desde la derecha (el primero desde la izquierda), debíamos restarle por 1000 binario (en decimal 8), es decir

1100-
1000
———
0100 (4 en el sistema decimal) 

a cuyo resultado tan sólo faltaba agregarle 1, dando como resultado

101 (5 en sistema decimal), el cual es el resultado de rotación que proponíamos inicialmente.

La parte interesante estaba en poder ubicar cada valor binario potencia de 2, es decir: 1,2,4,8,16,32,…,2^n

osea 1, 10,100,1000,10000, en binario.

Por tanto, cada valor doblado (6x2 del ejemplo) podamos quitarle el bit más significativo.

Preguntando, para encontrar ese valor recurrí a la potencia de 2 elevado al máximo entero de log en base 2 de X + 1, que serviría para encontrar dichas cotas, 1, 10,100,… (1,2,4,…), que corresponden para cada valor, dónde 6 del ejemplo sería

esto obtendrá cada valor binario con un bit activo (00000001,00000010,00000100,00001000,…etc), donde x sería el número de personas, osea

si x = 6, entonces resultaría 8, siendo en binario 1000, mayor próximo de 6, y como hacemos un desplazamiento a la izquierda de 1 bit, resultaría ser 12 en lugar de 6, siendo este último mayor que 8, exáctamente representando el bit que deseamos eliminar.

Quedando como resultado la fórmula:

Eso sería todo.