Flavio Josefo y el juego del puisi-nanoq

Un hecho histórico de hace 20 siglos desembocó en un problema matemático que aún hoy da bastante que hablar: el problema de los judíos. En él se combinan los algoritmos recursivos, las permutaciones, la aritmética modular y los procesos de eliminación de los elementos de un conjunto.

(Esta entrada participa en la Edición 5.X Sofia Kovalévskaya del Carnaval de Matemáticas, cuyo anfitrión es el blog ::ZTF News.)
PRIMERA PARTE
La entrenadora de la selección de Groenlandia está muy preocupada. Este fin de semana se juegan la clasificación para los Juegos Olímpicos de Río de Janeiro, y tiene un problema muy serio con su capitana.
Existe en el equipo la tradición de echar a suertes quién debe tirar los penaltis, entre las distintas jugadoras que quieran lanzarlos.
El problema es que, desde hace un tiempo, todos los lanza la capitana, y ésta lleva fallados los últimos 10 que ha tirado.
Pipaluk, la seleccionadora,  ha decidido llamar a su amigo Pepe Vitruvio, para ver si le ayuda a resolver este misterio, y así poder afrontar el próximo partido con las máximas garantías.
Pepe acepta la invitación de Pipaluk, y ésta va a recibirle al aeropuerto de Nuuk.

- Hola Pepe, estoy encantada de que hayas venido a ayudarme.
- No hay de qué. Cuéntame cuál es el problema.
- Será mejor que lo veas con tus propios ojos. Te invito al entrenamiento de mañana.
- Vale, allí nos vemos.
Al día siguiente, Pepe acude al estadio, y observa la curiosa forma de elegir a la persona que tirará el penalti.
- ¿Qué es eso que hacen cuando van a tirar un penalti? ¿Por qué se ponen todas en círculo?
- Es su forma de elegir quién de ellas lo lanzará: realizan el juego del puisi-nanoq (que significa foca-osa en groenlandés).
- ¿Y eso qué es?
- Pues se colocan en un círculo todas las jugadoras dispuestas a chutar el penalti, y se van eliminando de la siguiente forma. Empiezan a contar desde una de ellas, diciendo: puisi-nanoq-puisi-nanoq... (foca-osa-foca-osa...) Y todas a las que les toca la osa, quedan eliminadas. La última ‘foca’ será la que tire el penalti.
- ¿Cómo?

- Sí, es muy sencillo, aquí se juega desde la guardería. Se comienza a contar desde una de ellas (le asignaremos el número 1, de tal forma que esta primera jugadora, a la que le corresponde una foca, se queda en el círculo, y la segunda (osa) es eliminada. La tercera (foca) se queda en el círculo, y la cuarta (osa) es eliminada. Y así van haciendo, eliminando una jugadora de cada dos, y cada vez se va estrechando más el círculo, hasta que sólo queda una, que será quien tire el penalti.

- Pues no veo donde está el problema. Los tres penaltis que han lanzado los ha tirado una jugadora distinta. Según he visto, varía el número de jugadoras que se ofrecen a tirar el penalti de una vez para otra. Y además, cada vez se ordenan de forma distinta al formar el círculo, y comienzan a contar por una jugadora distinta.
- Sí, así es en los entrenamientos. Pero en los partidos oficiales, la capitana tiene el derecho de ser ella quien haga el recuento, y de empezar por la jugadora que ella quiera. Y curiosamente, en las diez últimas ocasiones siempre ha sido ella la elegida para tirar los penaltis.
- Esto no sería un problema si los tirase bien. Pero es la peor de todas en esa faceta del juego, y ya hemos perdido algún partido por este motivo. El sábado nos jugamos la clasificación para las Olimpiadas, y no quiero que nos pase lo mismo. Ella dice que no hace trampas, que todo se debe a la suerte. ¿Es realmente así, Pepe?

SEGUNDA PARTE
- Una pregunta, Pipaluk: ¿la capitana és matemàtica?
- No, qué va. Es licenciada en Historia por la Universidad de Nuuk.
- Bueno, eso también explicaría su habilidad. Seguro que conoce la historia de Flavio Josefo.
- ¿Quién es ese?
- Bueno, se trata de una historia muy antigua, del siglo I d.C., cuando Roma dominaba todo el Mediterráneo. Los judíos se habían sublevado contra el Imperio, pero el ejército romano era muy poderoso.

- Al frente del ejército de Galilea estaba Flavio Josefo, que era descendiente de una familia de sacerdotes ligada a la monarquía del pueblo de Israel. Llevaban unos meses defendiéndose de las legiones romanas en la fortaleza inexpugnable de Jotapata, pero ya no podían resistir más el cerco romano.

- Al ver que iban a ser capturados, decidieron suicidarse antes que entregarse deshonrosamente al ejército enemigo. Pero como la ley judía les prohibía el suicidio, adoptaron un curioso procedimiento para llevar a cabo su propósito, que se conoce en Matemáticas y en Ciencias de la Computación como el problema de los judíos .
- Los 41 soldados judiós que aún quedaban vivos formaron un círculo, al igual que hacen tus jugadoras. En su caso, iban contando de 3 en 3, de forma que al soldado señalado en tercer lugar le mataba su compañero de la derecha. Y así siguieron contando hasta que sólo quedó Flavio Josefo, el cual sí debía suicidarse, según  habían acordado. Pero no lo hizo, sino que se entregó a las tropas romanas.
- Fue enviado a Roma como esclavo de la familia imperial Flavia, de la que adoptó su nombre. Gracias a su formación académica y a sus dotes diplomáticas, fue finalmente liberado por el emperador Vespasiano, desarrollando una amplia labor en Roma como historiador y literato. Entre sus obras, encontramos la narración de este suceso que marcó su vida.
- Hay quien piensa que se salvó de casualidad, o gracias a la Divina Providencia, como él afirmaba,  pero está claro que sabía dónde colocarse para librarse del fatal desenlace.
- Y eso mismo es lo que ocurre con tu capitana. Ella es la que va contando quién se salva y quién se elimina. Así que sabe de sobra cómo hacer para ser ella quien tire el penalti.
- Sí, pero ella es la primera en colocarse en el círculo. No sabe cómo van a colocarse el resto de jugadoras ni cuántas serán.
- Es verdad, pero también es quién decide por dónde empezar a contar. Y ahí reside el truco. Ella sabe en qué posición debe estar respecto de la primera jugadora en la que empieza a contar, para así ser la última eliminada.
- ¡Ah! ¿Y cómo lo hace?
- Te lo voy a explicar con un grupo de 6 jugadoras. Les vamos a poner un número, empezando por la de arriba, y siguiendo el orden de las agujas del reloj.

- Y ahora vamos a empezar a jugar a vuestro juego del foca-osa-foca-osa. Empezamos por la jugadora número 1, a la que le corresponde una foca. A la 2 le corresponde una osa, y la eliminamos. A la 3 le toca la foca y se salva, y la 4 es osa y queda también eliminada.
- Ya sólo quedan 4 jugadoras en el círculo. Continuamos con la 5 (foca), que se salva, y eliminamos a la número 6 (osa). Seguimos dando la vuelta, de forma que a la 1 le corresponde otra vez la foca. La 3 es osa, así que la eliminamos. La 5 es foca, y se libra, y ahora la 1 es osa y queda eliminada. Será la número 5 la que tire el penalti.
- Ya sabemos que con 6 jugadoras, la elegida será la número 5. Si seguimos este procedimiento con distintos números de jugadoras, tendremos los siguientes resultados:

- Ahora lo entiendo, lo que ha hecho la capitana ha sido aprenderse toda esta secuencia de números, para saber en qué posición se tiene que colocar en función de la cantidad de jugadoras que forman el círculo, ¿verdad?
- Puede ser, aunque no es necesario aprendérselos de memoria. Podemos encontrar una fórmula.
- ¿Y cómo sería?
- Si nos fijamos en la tabla, veremos que cuando el número de jugadoras es potencia de 2 (1, 2, 4, 8, 16, 32), la jugadora que se salva es la número 1, es decir, la jugadora por la cual empezamos el juego.

- Pues sí, es verdad.
- Esto es fácil de entender si lo analizamos un poco. Pongamos que tenemos 16 jugadoras (16 es potencia de 2: 2⁴ = 16).
- En la primera vuelta al círculo, se eliminarán todas las jugadoras que ocupen posiciones pares, y nos quedarán la mitad de las jugadoras.

- Seguimos con el juego, y nuevamente se eliminan todas las que ocupan posiciones pares en la segunda vuelta.

- Damos la tercera vuelta al círculo, y nuevamente la número 1 se libra de la eliminación. Y finalmente, cuando quedan sólo 2 jugadoras (la número 1 y la número 9), también se elimina la segunda. Así que la 1 se salva en todas las vueltas. Y esto ocurrirá siempre que el número de jugadoras sea potencia de 2, porque tras cada vuelta siempre quedan un número par de jugadoras.

- Sí, pero ¿qué hacemos cuando no es potencia de 2?
- Entonces hemos de tener la habilidad de calcular las jugadoras que han de eliminarse hasta que queden un número que sea potencia de 2, de tal forma que en ese momento nos encontremos justo en el lugar que ocuparía el número 1 de ese nuevo círculo que se forma tras eliminar a la última de las jugadoras que exceden de la potencia de 2.
- ¿Cómo dices?
- Supongamos que hay 11 jugadoras en vez de 8. Tenemos que conseguir estar en la posición número 1 cuando queden sólo 8, para así poder aplicar el método que hemos visto antes, ya que 8 es potencia de 2 (2³ = 8).
- Así que tenemos que contar hacia atrás desde nuestra posición, de forma que haya 3 'osas' antes que nosotros. Y de esta manera obtenemos que debemos colocarnos en la posición número 7, para que así ocupemos la posición número 1 del nuevo círculo de 8 jugadoras que se forma tras las tres primeras eliminaciones del grupo de 11.
- Si queremos generalizar el procedimiento, deberemos tener en cuenta el número total de jugadores, que llamaremos n (en nuestro caso 11). Luego calcularemos en qué cantidad k excede este número de la potencia de 2 inmediatamente inferior:
k = n - 2^m, siendo m un número natural positivo tal que 2^m < n < 2^m+1
(en nuestro ejemplo k = 11 - 2³ = 3, ya que 2³ < 11 < 2⁴)
- Y nuestra posición óptima (p) en el círculo vendrá dada por la fórmula:
p = 2 · k + 1

(en nuestro caso p = 2 · 3 + 1 = 7)
- Y esto es lo que hace tu capitana, situarse en el séptimo lugar del círculo. O lo que es lo mismo, empezar a contar por la séptima jugadora que queda a su derecha.
- ¿Y cómo podríamos evitarlo? ¿Y si en vez de ir eliminarse con saltos de 2 en 2, lo hacen de 3 en 3 (foca-foca-osa-foca-foca-osa...), o con cualquier otro número?

- Dará igual, aunque con números más altos resulta más complejo su cálculo, al menos de cabeza. Con un ordenador a mano, podemos ver la solución en varias páginas como ésta o ésta otra.
- Y tampoco serviría de nada encargarle el cometido a otra jugadora, porque más pronto o más tarde aprendería el algoritmo.
- Pues sólo os queda cambiar el sistema de elección. Podríais elegir a la jugadora que tenga la mejor estadística de penaltis marcados, aunque esto también puede generar controversias, como ocurría en la historia de Y ahora, ¿quién tira el penalti?

- No, eso nunca. El juego del puisi-nanoq es toda una tradición en nuestra tierra.

- Creo que hay una solución. Y es la siguiente:
- Después de hacer la primera pareja foca-osa, de forma que la capitana pueda eliminar a la persona que peor los lanza, habrá de mirar el número que luce la jugadora descartada en su espalda, y utilizará ese número para llegar a la siguiente ‘osa’ a eliminar. Así, si es un 5, deberá contar foca-foca-foca-foca-osa.
- Si la siguiente eliminada lleva el número 7, contará seis focas y una osa, y así. De esta forma le resultará casi imposible averiguar quién será la última 'foca', aunque el juego esté determinado desde la primera elección.

- Pero, ¿y si es capaz de calcular mentalmente y de forma rápida quién será la última, ya que conoce los dorsales de todas las jugadoras?
- Aún así, en numerosas ocasiones le será imposible encontrar una combinación ganadora que le permita ser a ella la última.
- Supongamos, por ejemplo, que en el círculo se colocan las jugadores con los dorsales 5, 6, 7, 8 y 9, en ese mismo orden, y que la capitana tiene el número 5, veamos qué ocurriría con nuestro juego con las nuevas reglas que hemos impuesto.

- Podemos comprobar que la ganadora final depende de quién se elimine en primer lugar, pero que en ninguno de los casos quedarán últimas la dorsal número 5 ni la número 7, y que sin embargo, las jugadoras 6 y 9 contarán con más probabilidades de ser las elegidas.
- Pues me gusta bastante esta variante que has inventado. Seguro que con ella evitaremos por fin que la capitana tire siempre los penaltis, y así podremos llegar a los Juegos Olímpicos. Muchas gracias por tu ayuda, Pepe.

- Estoy seguro de que lo conseguiréis, Pipaluk. ¡Buena suerte con la clasificación!

Si te apetece profundizar más sobre los temas tratados en esta historia, puedes visitar cualquiera de estas estupendas páginas: Pito, pito, gorgorito..., Aritmética modular, ¿A quién recatamos el último?, ¿Qué es la aritmética modular?, Soluciones al problema de Flavio Josefo, Problema de Flavio Josefo.
No os olvidéis de dar una vuelta por el Carnaval de Matemáticas y votar la historia que más os guste. Allí encontraréis unos excelentes artículos matemáticos de los que disfrutaréis con su lectura.
Y si te ha gustado la historia, puedes votar por ella en menéame y divoblogger o compartirla en alguna de las siguientes redes sociales (no es necesario que lo hagas en todas, me conformaré con que la compartas en sólo cuatro o cinco de ellas ;-)
           
Además, si se te ocurre alguna otra forma de jugar al puisi-nanoq en la que la capitana no pueda elegir de antemano quién será la ganadora, la puedes compartir escribiendo un comentario más abajo.