Problema de Josefo

Enunciado

Se dan los números naturales $n$ y $k$. Todos los números naturales de $1$ a $n$ se escriben en un círculo. Primero, se cuenta el $k$-ésimo número empezando desde el primero y se elimina. Luego se cuentan $k$ números empezando desde el siguiente y de nuevo se elimina el $k$-ésimo, y así sucesivamente. El proceso se detiene cuando queda un solo número. Se pide hallar el último número.

Esta tarea la planteó Flavio Josefo (Flavius Josephus) en el siglo I (aunque en una formulación algo más estrecha: para $k = 2$).

Este problema se puede resolver modelando el procedimiento. El modelado por fuerza bruta funciona en $O(n^{2})$. Usando un Árbol de Segmentos, podemos mejorarlo a $O(n \log n)$. Sin embargo queremos algo mejor.

Modelar una solución $O(n)$

Intentaremos hallar un patrón que exprese la respuesta del problema $J_{n, k}$ a través de la solución de los problemas anteriores.

Usando modelado por fuerza bruta podemos construir una tabla de valores, por ejemplo la siguiente:

$$\begin{array}{ccccccccccc}n\setminus k& 1& 2& 3& 4& 5& 6& 7& 8& 9& 10\\ 1& 1& 1& 1& 1& 1& 1& 1& 1& 1& 1\\ 2& 2& 1& 2& 1& 2& 1& 2& 1& 2& 1\\ 3& 3& 3& 2& 2& 1& 1& 3& 3& 2& 2\\ 4& 4& 1& 1& 2& 2& 3& 2& 3& 3& 4\\ 5& 5& 3& 4& 1& 2& 4& 4& 1& 2& 4\\ 6& 6& 5& 1& 5& 1& 4& 5& 3& 5& 2\\ 7& 7& 7& 4& 2& 6& 3& 5& 4& 7& 5\\ 8& 8& 1& 7& 6& 3& 1& 4& 4& 8& 7\\ 9& 9& 3& 1& 1& 8& 7& 2& 3& 8& 8\\ 10& 10& 5& 4& 5& 3& 3& 9& 1& 7& 8\end{array}$$$$\begin{array}{ccccccccccc} n\setminus k & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \ 2 & 2 & 1 & 2 & 1 & 2 & 1 & 2 & 1 & 2 & 1 \ 3 & 3 & 3 & 2 & 2 & 1 & 1 & 3 & 3 & 2 & 2 \ 4 & 4 & 1 & 1 & 2 & 2 & 3 & 2 & 3 & 3 & 4 \ 5 & 5 & 3 & 4 & 1 & 2 & 4 & 4 & 1 & 2 & 4 \ 6 & 6 & 5 & 1 & 5 & 1 & 4 & 5 & 3 & 5 & 2 \ 7 & 7 & 7 & 4 & 2 & 6 & 3 & 5 & 4 & 7 & 5 \ 8 & 8 & 1 & 7 & 6 & 3 & 1 & 4 & 4 & 8 & 7 \ 9 & 9 & 3 & 1 & 1 & 8 & 7 & 2 & 3 & 8 & 8 \ 10 & 10 & 5 & 4 & 5 & 3 & 3 & 9 & 1 & 7 & 8 \ \end{array}$$

Y aquí podemos ver claramente el siguiente patrón:

$$J_{n,k} = \left( (J_{n-1,k} + k - 1) \bmod n \right) + 1$$

$$J_{1,k} = 1$$

Aquí, la indexación desde uno da una fórmula un tanto desordenada; si en cambio se numeran las posiciones desde 0, se obtiene una fórmula muy elegante:

$$J_{n,k} = (J_{n-1,k} + k) \bmod n$$

Así, hallamos una solución al problema de Josefo, que trabaja en $O(n)$ operaciones.

Implementación

Implementación recursiva sencilla (con indexación desde uno)

int josephus(int n, int k) {
    return n > 1 ? (josephus(n-1, k) + k - 1) % n + 1 : 1;
}

Forma no recursiva:

int josephus(int n, int k) {
    int res = 0;
    for (int i = 1; i <= n; ++i)
  	  res = (res + k) % i;
    return res + 1;
}

Esta fórmula también se puede hallar analíticamente. De nuevo aquí asumimos indexación desde cero. Después de eliminar el primer número, nos quedan $n-1$ números. Cuando repetimos el procedimiento, empezaremos con el número que originalmente tenía el índice $k \bmod n$. $J_{n-1, k}$ sería la respuesta para el círculo restante, si empezamos a contar en $0$, pero como en realidad empezamos con $k$ tenemos $J_{n, k} = (J_{n-1,k} + k) \ \bmod n$.

Modelar una solución $O(k \log n)$

Para $k$ relativamente pequeño podemos idear una solución mejor que la solución recursiva anterior en $O(n)$. Si $k$ es mucho menor que $n$, entonces podemos eliminar varios números ($\lfloor \frac{n}{k} \rfloor$) en una pasada sin dar la vuelta. Después nos quedan $n - \lfloor \frac{n}{k} \rfloor$ números, y empezamos con el $(\lfloor \frac{n}{k} \rfloor \cdot k)$-ésimo número. Así que tenemos que desplazar esa cantidad. Podemos notar que $\lfloor \frac{n}{k} \rfloor \cdot k$ es simplemente $-n \bmod k$. Y como eliminamos cada $k$-ésimo número, tenemos que sumar el número de números que eliminamos antes del índice resultado. Lo cual podemos calcular dividiendo el índice resultado por $k - 1$.

También necesitamos manejar el caso en que $n$ se vuelve menor que $k$. En este caso, la optimización anterior causaría un bucle infinito.

Implementación (por conveniencia con indexación desde cero):

int josephus(int n, int k) {
    if (n == 1)
        return 0;
    if (k == 1)
        return n-1;
    if (k > n)
        return (josephus(n-1, k) + k) % n;
    int cnt = n / k;
    int res = josephus(n - cnt, k);
    res -= n % k;
    if (res < 0)
        res += n;
    else
        res += res / (k - 1);
    return res;
}

Estimemos la complejidad de este algoritmo. Nótese de inmediato que el caso $n < k$ se analiza con la solución antigua, que en este caso trabajará en $O(k)$. Ahora consideremos el algoritmo en sí. De hecho, después de cada iteración, en lugar de $n$ números, nos quedan $n \left( 1 - \frac{1}{k} \right)$ números, así que el número total de iteraciones $x$ del algoritmo se puede hallar de forma aproximada a partir de la siguiente ecuación:

$$n \left(1 - \frac{1}{k} \right) ^ x = 1,$$

al tomar logaritmo en ambos lados, obtenemos:

$$\ln n + x \ln \left(1 - \frac{1}{k} \right) = 0,$$ $$x = - \frac{\ln n}{\ln \left(1 - \frac{1}{k} \right)},$$

usando la descomposición del logaritmo en serie de Taylor, obtenemos una estimación aproximada:

$$x \approx k \ln n$$

Así, la complejidad del algoritmo es de hecho $O (k \log n)$.

Solución analítica para $k = 2$

En este caso particular (en el que esta tarea la planteó Flavio Josefo) el problema se resuelve mucho más fácil.

En el caso de $n$ par obtenemos que todos los números pares se tacharán, y luego quedará un problema restante para $\frac{n}{2}$, entonces la respuesta para $n$ se obtendrá de la respuesta para $\frac{n}{2}$ multiplicando por dos y restando uno (desplazando posiciones):

$$J_{2n, 2} = 2 J_{n, 2} - 1$$

De manera similar, en el caso de un $n$ impar, se tacharán todos los números pares, luego el primer número, y quedará el problema para $\frac{n-1}{2}$, y teniendo en cuenta el desplazamiento de posiciones, obtenemos la segunda fórmula:

$$J_{2n+1,2} = 2 J_{n, 2} + 1$$

Podemos usar esta dependencia recurrente directamente en nuestra implementación. Este patrón se puede traducir a otra forma: $J_{n, 2}$ representa una secuencia de todos los números impares, “reiniciándose” desde uno siempre que $n$ resulte ser una potencia de dos. Esto se puede escribir como una sola fórmula:

$$J_{n, 2} = 1 + 2 \left(n-2^{\lfloor \log_2 n \rfloor} \right)$$

Solución analítica para $k > 2$

A pesar de la forma sencilla del problema y de un gran número de artículos sobre este y problemas relacionados, todavía no se ha hallado una representación analítica simple de la solución del problema de Josefo. Para $k$ pequeño se derivan algunas fórmulas, pero al parecer todas son difíciles de aplicar en la práctica (por ejemplo, véase Halbeisen, Hungerbuhler “The Josephus Problem” y Odlyzko, Wilf “Functional iteration and the Josephus problem”).