PROBLEMA DE FLAVIO JOSEFO Y LA PREDICCION AUSTRALIANA

 

SALVADO POR LAS MATEMÁTICAS

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 el siglo I. Según lo que cuenta Josefo, durante la rebelión judía contra Roma en el siglo I d.C., 40 judíos se encontraron acorralados en una cueva. Para evitar ser atrapados y convertirse en esclavos, prefirieron la muerte y decidieron formar un círculo, matarse entre ellos: el primero mataba al segundo y pasaba el arma al tercero, quien mataba al siguiente, y así sucesivamente, hasta que quedara uno solo, quien se suicidaría. Los últimos que quedaron fueron Josefo y otro hombre. Entonces; Josefo no cumplió su promesa; convenció al otro hombre que debían entregarse a los romanos en lugar de matarse entre ellos. Josefo además de no cumplir su pacto no sabía matemáticas y atribuyó su supervivencia a la suerte o a la Providencia.

Matemáticamente el problema plantea lo siguiente:

Hay n personas permanecen en un círculo esperando a ser ejecutadas. Después de que ejecutan a la primera persona, se cuentan k − 1 personas y la persona número k es ejecutada. Entonces nuevamente, Se cuentan 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 que sobrevive a las ejecuciones), dados n y k.

Un problema de matemáticas recreativas semejante; dado por Sam Loyd es:

TRECE RATONES PARA UN GATO

Los trece ratones que rodean al gato Josefo están condenados a ser devorados por él. Pero el gato Josefa ha decidido comerlos en cierto orden. Comenzando por uno de ellos, cuenta trece en el sentido de las manecillas del reloj. Se come al que ocupa el lugar trece y sigue la cuenta. Por donde habrá de comenzar a contar para en último lugar comer al ratón blanco.

Con una baraja de cartas puede simularse el problema de Josefo mediante la llamada mezcla australiana, que ilustraremos con el siguiente efecto de magia:

  PREDICCIÓN A LA AUSTRALIANA

1. Entregar a un espectador ocho cartas cualesquiera o elegir las cartas del as al ocho, para que las mezcle. Con la excusa de comprobar si están bien mezcladas, echa un vistazo (sin que nadie te vea) a la carta superior y escríbela en una hoja de papel. Anuncia que vas a realizar una predicción.
2. Devuelve las cartas al espectador y pídele que realice la llamada mezcla australiana, que consiste en lo siguiente:
• Con las cartas cara abajo, se pasa la carta superior a la parte inferior del paquete.
• La actual carta superior se deja sobre la mesa.
• Se repiten los dos pasos anteriores, carta superior a la parte inferior, carta siguiente sobre la mesa.
• El proceso termina cuando queda en la mano una sola carta.
  [Observa la similitud de este proceso con el utilizado por Flavio Josefo y sus compañeros.]

Al final, muestra la predicción y comprueba que coincide con la única carta que al final tiene el espectador.

El juego puede repetirse con un número diferente de cartas. Pero debes practicar bien antes de realizarlo pues requiere algunas operaciones mentales.

El juego consiste en lo siguiente:

1. Busca una baraja de cartas y pide a un espectador que nombre un número arbitrario. Dicho número corresponderá a la cantidad de cartas con las que va a realizarse el juego.
2. Cuenta, una a una sobre la mesa, caras arriba, tantas cartas como el número que ha seleccionado el espectador. Mientras tanto, debes hacer las siguientes operaciones secretas:
• Busca el equivalente en notación binaria del número elegido por el espectador (pongamos por ejemplo 13, que se escribe como 1101).
• Traslada la primera cifra a la última posición (quedaría en nuestro ejemplo 1011).
• Calcula la representación decimal del número obtenido (en este caso 1011 corresponde a 11).
• Recuerda la carta que ocupa dicho lugar en el montón de cartas que vas dejando sobre la mesa. Esta será la carta que adivinarás.
3. Recoge el montón de cartas. Anuncia que harás una predicción y escribe en una hoja de papel la carta que has recordado durante el proceso anterior.
4. Realiza la llamada mezcla australiana, que consiste en lo siguiente:
• Con las cartas caras abajo, se pasa la carta superior a la parte inferior del paquete.
• La actual carta superior se deja sobre la mesa.
• Se repiten los dos pasos anteriores, carta superior a la parte inferior, carta siguiente sobre la mesa.
• El proceso termina cuando queda en la mano una sola carta.

Comprueba que la carta de la mano es la carta que habías predicho anteriormente. 

Nota: Un método más sencillo para saber la carta que debes recordar es el siguiente:

·         Calcula la diferencia entre el número indicado por el espectador y la potencia de dos más próxima a dicho número (en el ejemplo citado, 13 - 8 = 5).

·         Multiplica por dos dicho número y suma uno al resultado (con lo que se obtiene 5 · 2 + 1 = 11). Dicho valor corresponde a posición de la carta que debes recordar.

·         Si el número indicado por el espectador ya es una potencia de dos, la primera carta será la que debes recordar.

Una explicación matemática de este juego de mezcla australiana es la siguiente:

SOLUCIÓN

Se puede probar fácilmente que, si el número de personas es 2ⁿ, la primera de ellas será la última en eliminarse. Basta observar que, en la primera fase, se eliminan todas las personas que ocupan un lugar par. Al renumerar las restantes, se obtiene un grupo con 2^n-1 personas a las que se puede aplicar el mismo proceso anterior. Cuando sólo quedan dos personas, es evidente que se elimina la número dos y queda la primera.

Una sencilla variación de este argumento permite demostrar que, si se trata de un grupo de 2ⁿ + k personas, eliminamos en primer lugar las colocadas en las posiciones 2, 4, ..., 2k, para llegar a un grupo con 2ⁿ personas y ahora la primera de ellas es la que ocupaba inicialmente el lugar 2k + 1.

En nuestro caso, como 40 = 2⁵ + 8, la posición que debe ocupar el superviviente será 2 x 8 + 1 = 17.