Parece un juego cruel que solo puede resolverse simulando eliminaciones una por una. Pero el círculo tiene memoria binaria: cuando desaparecen los pares, el problema vuelve a empezar con otro nombre.
El círculo de Josefo
Enunciado
Hay 41 personas colocadas en círculo, numeradas del 1 al 41.
Se empieza por la persona 1.
La persona 1 se salva por ahora, la persona 2 queda eliminada, la persona 3 se salva por ahora, la persona 4 queda eliminada, y así sucesivamente alrededor del círculo: una persona se salva, la siguiente queda eliminada.
El proceso continúa hasta que queda una sola persona.
¿En qué posición debes colocarte para sobrevivir?
Ver solución
Solución
La posición segura es la 19.
La idea no es simular las 40 eliminaciones, sino mirar cómo se renombra el círculo después de cada barrido.
Llamemos $J(n)$ a la posición que sobrevive con $n$ personas cuando se salva la primera, se elimina la segunda, se salva la tercera, se elimina la cuarta, y así sucesivamente.
Si $n=2m$ es par, la primera vuelta elimina todas las posiciones pares:
Quedan las impares:
El mismo juego continúa sobre esas $m$ posiciones. Si en el círculo reducido sobrevive la posición $J(m)$, en el círculo original corresponde a:
Por tanto:
Si $n=2m+1$ es impar, la primera vuelta elimina de nuevo todas las posiciones pares, pero después de salvar la posición $2m+1$ la siguiente eliminada es la posición 1. Quedan:
El juego vuelve a empezar sobre $m$ posiciones. Si en el círculo reducido sobrevive la posición $J(m)$, en el círculo original corresponde a:
Así que:
Ahora aplicamos esto a 41:
Necesitamos $J(20)$. Como:
obtenemos:
Finalmente:
La fórmula compacta dice lo mismo: si $n=2^m+\ell$, con $0\leq\ell<2^m$, entonces:
Como:
queda:
Respuesta: debes colocarte en la posición 19.