<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[12pt,a4paper]{article}
\usepackage[utf8]{inputenc}
\usepackage[spanish]{babel}
\usepackage{anysize}
\usepackage{amsthm}
\usepackage{multicol}
\newcommand{\noun}[1]{\textsc{#1}}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{graphicx}
\title{Sobre el problema de Flavio Josefo}
\author{VÃ­ctor Arnaiz, Pedro Ãngel Castillejo, Ãlvaro GonzÃ¡lez}
\date{9 de abril de 2010}

\newtheorem{problema}{Problema}
\newtheorem{prop}{ProposiciÃ³n}
\newtheorem{definicion}{DefiniciÃ³n}
\newtheorem{observacion}{ObservaciÃ³n}

\marginsize{3cm}{3cm}{2cm}{2cm}


\begin{document}
\maketitle
\section*{IntroducciÃ³n}
El origen del problema se remonta a las llamadas guerras judeo-romanas, durante el siglo I. SegÃºn cuenta el historiador judÃ­o Flavio Josefo, Ã©l y cuarenta soldados camaradas fueron capturados por los romanos despuÃ©s de la caÃ­da de Jotapata. Antes que rendirse, decidieron acabar ellos mismos con sus vidas. Para hacerlo, se dispusieron en un cÃ­rculo y acordaron que irÃ­an contando de tres en tres, de forma que cada tercer soldado serÃ­a ejecutado por la persona de su izquierda. El Ãºltimo hombre que quedara con vida tendrÃ­a que suicidarse. SegÃºn cuenta la leyenda, Josefo calculÃ³ rÃ¡pidamente cuÃ¡l serÃ­a la posiciÃ³n del Ãºltimo hombre en morir para colocarse allÃ­, y una vez hubieron muerto sus compatriotas, se entregÃ³ a los romanos. Josefo, sin embargo, en su obra \textit{Las Guerras de los JudÃ­os}, Libro III, CapÃ­tulo 8, dice que el orden de ejecucciÃ³n fue determinado por sorteo, y que Ã©l y su mejor amigo se salvaron tal vez por azar, o quizÃ¡s por la divina intervenciÃ³n en el sorteo. 

El problema que nos ocuparÃ¡ reaparece en la Edad Media, en la obra de Abraham ben Meir ibn Ezra (1092-1167), mÃ¡s conocido como Rabbi Ben Ezra, uno de tantos escolares judÃ­os que vivieron y estudiaron en el Califato de CÃ³rdoba.

Otras versiones del problema aparecen en la matemÃ¡tica oriental. Un ejemplo es el libro datado en 1627, del matemÃ¡tico japonÃ©s Yoshida Koyu llamado \textit{Tratado sobre los grandes y pequeÃ±os nÃºmeros}, en que se explica la versiÃ³n japonesa del problema de Josefo. En Ã©sta se ve involucrada una familia con 30 hijos, la mitad de ellos del primer matrimonio del padre, y la segunda de su segunda mujer. Para elegir al heredero de las propiedades de sus padres, se disponen los treinta en un cÃ­rculo y se empieza a contar de diez en diez, de forma que el dÃ©cimo de cada tanda es eliminado. La madre del primer matrimonio dispone a sus hijos de forma que los quince primeros eliminados sean los de la otra mujer, pero cuando ya han sido eliminados 14, el padre decide cambiar el sentido de giro. AsÃ­, todavÃ­a hay una oportunidad para el hijo del segundo matrimonio que no ha sido eliminado. El problema es hallar la posiciÃ³n que debe ocupar.

\section*{El problema clÃ¡sico}

\begin{problema}
Se tienen $n$ personas numeradas entorno a un cÃ­rculo esperando ser ejecutadas. Empezando por la persona nÃºmero 1, se saltan $m-1$ personas y se mata a la $m$-Ã©sima. A continuaciÃ³n se saltan otras $m-1$ personas y se ejecuta a la siguiente, y asÃ­ hasta que sÃ³lo quede una.

El objetivo es encontrar el lugar inicial en el cÃ­rculo para sobrevivir $J(n,m)$, dados $n$ y $m$.
\end{problema}

\subsection*{El caso $m=2$}

Si la eliminaciÃ³n se hace de dos en dos, en la primera vuelta son eliminados los nÃºmeros pares. Si en principio habÃ­a $2n$ personas, tras matar las $n$ primeras se obtiene otro cÃ­rculo de $n$ personas, de forma que la persona $i$-Ã©sima 
de este nuevo cÃ­rculo se corresponde con la $2i-1$ del primero. En otro caso, si al principio tenÃ­amos $2n+1$, tras la muerte de $n+1$ personas obtenemos otro cÃ­rculo de $n$ personas, y ahora la persona $i$-Ã©sima de Ã©ste se corresponde con la $2i+1$ del cÃ­rculo de partida. Se establece asÃ­ la recurrencia siguiente:
$$\begin{array}{rcl}
J(1) &amp; = &amp; 1 \\
J(2n) &amp; = &amp; 2J(n)-1 \\
J(2n+1) &amp; = &amp; 2J(n)+1
\end{array}$$

Ahora ya podemos construir rÃ¡pidamente una tabla de valores para $J(n,2)$:

\begin{center}
\begin{tabular}{|c|c|cc|cccc|cccccccc|c}
\hline $n$ &amp; 1 &amp; 2 &amp; 3 &amp; 4 &amp; 5 &amp; 6 &amp; 7 &amp; 8 &amp; 9 &amp; 10 &amp; 11 &amp; 12 &amp; 13 &amp; 14 &amp; 15 &amp; 16 \\ 
\hline $J(n)$ &amp; 1 &amp; 1 &amp; 3 &amp; 1 &amp; 3 &amp; 5 &amp; 7 &amp; 1 &amp; 3 &amp; 5 &amp; 7 &amp; 9 &amp; 11 &amp; 13 &amp; 15 &amp; 1 \\ 
\hline 
\end{tabular} 
\end{center}

Se demuestra por inducciÃ³n la fÃ³rmula explÃ­cita $$J(2^m+l,2)=2l+1$$ con $m\geq 0$ y $0\leq l&lt;2^m$. Esto lo podemos expresar Ãºnicamente en funciÃ³n de $n$ como $J(n)=1+2(n-2^{\lfloor\log_2n\rfloor})$.

Otra forma de ver $J(n,2)$ es poniendo $n$ en base 2. AsÃ­,
$$
\left.\begin{array}{rcl}
n &amp; = &amp; (1\,b_{m-1}\,b_{m-2}...b_1\,b_0)_2 \\
l &amp; = &amp; (0\,b_{m-1}\,b_{m-2}...b_1\,b_0)_2 \\
2l &amp; = &amp; (b_{m-1}\,b_{m-2}...b_1\,b_0\,0)_2\\
2l+1 &amp; = &amp; (b_{m-1}\,b_{m-2}...b_1\,b_0\,1)_2 \\
J(n) &amp; = &amp; (b_{m-1}\,b_{m-2}...b_1\,b_0\,b_m)_2
\end{array} \right.
$$
La Ãºltima igualdad se sigue de que $b_k=1$. Por tanto, hemos probado que,
$$ J((b_m\,b_{m-1}...b_1\,b_0)_2)=(b_{m-1}\,b_{m-2}...b_1\,b_0\,b_m)_2$$

\subsection*{El caso $m=3$}
En general, para todos $n$ y $m$ se cumple que 

\begin{equation}
J(n,m)\equiv{J(n-1,m)+m \pmod n}
\end{equation}

porque despuÃ©s de matar a la primera persona se obtiene un nuevo cÃ­rculo de $n-1$ personas, donde la primera se corresponde con la $1+m$ del anterior.

A partir de esta recurrencia obtenemos la tabla para los primeros valores de $J(n,3)$:

\begin{center}
\begin{tabular}{|c|ccccccccccccccc}
\hline $n$ &amp; 1 &amp; 2 &amp; 3 &amp; 4 &amp; 5 &amp; 6 &amp; 7 &amp; 8 &amp; 9 &amp; 10 &amp; 11 &amp; 12 &amp; 13 &amp; 14 \\ 
\hline $J(n)$ &amp; 1 &amp; 2 &amp; 2 &amp; 1 &amp; 4 &amp; 1 &amp; 4 &amp; 7 &amp; 1 &amp; 4 &amp; 7 &amp; 10 &amp; 13 &amp; 2  \\ 
\hline 
\end{tabular} 
\end{center}
Vemos que la sucesiÃ³n $J(n)$ aumenta de tres en tres hasta que sobrepasa a $n$ y entonces empieza de nuevo en 1 o en 2. Nos fijaremos ahora en la sucesiÃ³n $\mathcal{N}_k$ definida como 

$$
\lbrace \mathcal{N}_k \rbrace _{k=1} ^\infty = \lbrace n:\;J(n,3)\in \{1,2\} \rbrace
$$
\bigskip

Consideremos $\mathcal{N}_{k-1} \leq n &lt; \mathcal{N}_k$. Entonces, utilizando (1) vemos que

\begin{equation}
J(n) = J(\mathcal{N}_{k-1}) + 3(n - \mathcal{N}_{k-1}), 
\end{equation}

y para $n = \mathcal{N}_k$ se cumplirÃ¡
$$
\mathcal{N}_k + J(\mathcal{N}_k) = J(\mathcal{N}_{k-1}) + 3(\mathcal{N}_k - \mathcal{N}_{k-1}), 
$$
que reordenando queda como
$$
3\mathcal{N}_{k-1} - J(\mathcal{N}_{k-1}) = 2\mathcal{N}_k - J(\mathcal{N}_k) 
$$

Realizando una distinciÃ³n de casos, desarrollamos la recurrencia asÃ­:

$$
\left\lbrace \begin{array}{l}
J(\mathcal{N}_1)=J(1)=1 \\

\mbox{Si}\: \mathcal{N}_k \: \mbox{es impar}\:
\left\lbrace \begin{array}{l}
\displaystyle J(\mathcal{N}_k)=1\Rightarrow{J(\mathcal{N}_{k+1})=J \left( \frac{3\mathcal{N}_k+1}{2} \right)=2} \bigskip\\

\displaystyle J(\mathcal{N}_k)=2\Rightarrow{J(\mathcal{N}_{k+1})=J \left( \frac{3\mathcal{N}_k-1}{2} \right)=1}
\end{array} \right. \bigskip \\


\mbox{Si}\: \mathcal{N}_k \: \mbox{es par}\:
\left\lbrace \begin{array}{l}
\displaystyle J(\mathcal{N}_k)=1\Rightarrow{J(\mathcal{N}_{k+1})=J \left( \frac{3\mathcal{N}_k}{2} \right)=1} \bigskip \\

\displaystyle J(\mathcal{N}_k)=2\Rightarrow{J(\mathcal{N}_{k+1})=J \left( \frac{3\mathcal{N}_k}{2} \right)=2}.
\end{array} \right.
\end{array} \right.
$$

AdemÃ¡s, si escribimos los $\mathcal{N}_k$ en base 3, podemos ver la siguiente

\begin{observacion}
$$
\left. \begin{array}{ll}
\mathcal{N}_k\equiv 0 &amp;\pmod {3^l} \\
\mathcal{N}_k\equiv j\cdot3^l &amp;\pmod{3^{l+1}}
\end{array} \right\rbrace \Rightarrow J(\mathcal{N}_k)= \left\lbrace \begin{array}{lr}
j &amp; \mbox{si } l \mbox{ es par;} \\
3-j &amp; \mbox{si } l \mbox{ es impar,}
\end{array} \right.
$$
para todo $k$ con $l\geq0$ y $1\leq{j\leq2}$.
\end{observacion}
\bigskip

\begin{proof}
Procedemos por inducciÃ³n sobre $k$. Lo comprobamos para $\mathcal{N}_1=1$. Supongamos que es cierto para $\mathcal{N}_k$. Si $\mathcal{N}_k$ es par, entonces $\mathcal{N}_{k+1}=\frac{3}{2} \mathcal{N}_k$ y $J(\mathcal{N}_{k+1})=J(\mathcal{N}_k)$. Entonces
$$\mathcal{N}_k\equiv j\cdot3^l \pmod{3^{l+1}}\Rightarrow\mathcal{N}_{k+1}=\frac{3}{2}\mathcal{N}_k\equiv(3-j)\cdot3^{l+1}\pmod{3^{l+2}}.$$
Si $\mathcal{N}_k$ es impar, entonces
$$J(\mathcal{N}_k)=1\Rightarrow\mathcal{N}_{k+1}=\dfrac{3\mathcal{N}_k+1}{2}\equiv 2 \pmod 3;$$
$$J(\mathcal{N}_k)=2\Rightarrow\mathcal{N}_{k+1}=\dfrac{3\mathcal{N}_k-1}{2}\equiv 1 \pmod 3.$$\qedhere
\end{proof}

Busquemos una expresiÃ³n que nos determine la suma de los $m$ primeros tÃ©rminos  de $\lbrace \mathcal{N}_k \rbrace$. TenÃ­amos
$$ 3 \mathcal{N}_k - J(\mathcal{N}_k) = 2 \mathcal{N}_{k+1}- J(\mathcal{N}_{k+1}) $$
En particular, para $k=1$:
$$ 3\mathcal{N}_1 - J(\mathcal{N}_1) = 2\mathcal{N}_2 - J(\mathcal{N}_2)$$

Sumando $\mathcal{N}_2$ a los dos tÃ©rminos de la igualdad obtenemos 

$$ 3\mathcal{N}_1 + \mathcal{N}_2 - J(\mathcal{N}_1) = 3 \mathcal{N}_2 - J(\mathcal{N}_2) = 2\mathcal{N}_3 - J(\mathcal{N}_3)$$

$$\mathcal{N}_1 + \mathcal{N}_2 = 2\mathcal{N}_3 - J(\mathcal{N}_3) - 2\mathcal{N}_1 + J(\mathcal{N}_1)$$ 
siendo $\mathcal{N}_1=1$ y $J(\mathcal{N}_1)=1$. Aplicando inducciÃ³n sobre $k$ podemos expresar la suma de los $k$ primeros tÃ©rminos de $\lbrace \mathcal{N}_k \rbrace$ como sigue:

\begin{equation}
\mathcal{S}_k = \displaystyle\sum_{i=1}^{k} \mathcal{N}_i = 2\mathcal{N}_{k+1}- J(\mathcal{N}_{k+1}) - 1
\end{equation}
\bigskip

No olvidemos que nuestro objetivo es encontrar una expresiÃ³n que nos determine el tÃ©rmino general de $J(n, 3)$. Sigamos.

\begin{prop}
La sucesiÃ³n $ \mu_k= \displaystyle \frac{ \mathcal{N}_k}{ \left( \frac{3}{2} \right)^{k-1}} $ es convergente.
\end{prop}

\begin{proof}
Sea $t$ el menor natural tal que $\mathcal{N}_{k+t} \neq \frac{3}{2}\mathcal{N}_{k+t-1}$, entonces se verifica que $$\mu_{k+t}=\mu_k+\frac{1}{2(\frac{3}{2})^{k+t-1}},\:\: \mbox{o bien},\:\: \mu_{k+t}=\mu _k-\frac{1}{2(\frac{3}{2})^{k+t-1}}.$$

Esto quiere decir que podemos expresar $\{\mu_k\}$ como 
$$\mu_k = 1+ \frac{1}{2(\frac{3}{2})^{s_1}} - \frac{1}{2(\frac{3}{2})^{s_2}} +\ldots+(-1)^{t+1} \frac{1}{2(\frac{3}{2})^{s_t}}$$
donde $\{s_n\}$ es la subsucesiÃ³n de nÃºmeros naturales que cumplen que $\mathcal{N}_{s_{i+1}} \neq \frac{3}{2}\mathcal{N}_{s_i}$, es decir: 
$$\mathcal{N}_{s_n}=\frac{3\mathcal{N}_{s_n-1}+(-1)^{n+1}}{2}.$$

Cuando $m$ tiende a infinito, tenemos $$\lim_{k \to \infty} {\mu_k}=1+\frac{1}{2}\sum_{i=1}^\infty {(-1)^{i+1}\left(\frac{2}{3}\right)^{s_i}}$$
y esta serie es convergente, porque $\lvert(-1)^{i+1}\left(\frac{2}{3}\right)^{s_i}\rvert \rightarrow 0$.
\end{proof}

Aproximamos computacionalmente dicho lÃ­mite al que llamamos $\mu$:
$$\lim_{k \to \infty} \mu_k = \mu \approx 1,21670287712495\ldots$$

Podemos extender este resultado a las sumas $\mathcal{S}_k$, ya que:
$$\lim_{k \to \infty} \frac{\mathcal{S}_k}{2\left(\frac{3}{2}\right)^k-2}=\lim_{k\to\infty} \frac{2 \mathcal{N}_{k+1} - 1 - J(\mathcal{N}_{k+1})}{2\left(\frac{3}{2}\right)^k -2}=\lim_{k\to\infty} \frac{\mathcal{N}_{k+1}}{\left(\frac{3}{2}\right)^k}=\mu$$
\bigskip

A continuaciÃ³n, utilizaremos todo esto para obtener el tÃ©rmino general de $J(n,3)$. Recordemos (2), $$J(n)=J(\mathcal{N}_k)+3\left(n-\mathcal{N}_k\right)$$
donde $\mathcal{N}_k\leq n&lt;\mathcal{N}_{k+1}$. Ahora, por (3) tenemos 

$$\mathcal{S}_{k-1}=2(\mathcal{N}_k-1)-J(\mathcal{N}_k)+1\Rightarrow J(\mathcal{N}_k)=2\mathcal{N}_k-1-\mathcal{S}_{k-1}$$
y sustituyendo esto en (2) obtenemos
$$J(n) = 3n - 1 - \mathcal{S}_k$$

Entonces, un posible tÃ©rmino general para $J(n, 3)$ es 
\bigskip

$$
J(n)=3n-1-\left[2\mu\left(\left(\frac{3}{2}\right)^{\lfloor \log_{3/2}\frac{n}{\mu}\rfloor+1}-1\right) \right]
$$
\bigskip

Sin embargo, esta fÃ³rmula no es vÃ¡lida porque, como ya hemos visto, $\lbrace \mu_k \rbrace$ es una sucesiÃ³n oscilante. El problema es que cuando $\mu_k &lt; \mu$ se tiene que  
$$
\log_{3/2}\frac{ \mathcal{N}_k }{\mu} &lt; \log_{3/2}\frac{ \mathcal{N}_k}{\mu_k}  = k - 1
$$
y al aproximar hacia abajo obtenemos $k-2$ en vez de $k-1$.
\bigskip

Para arreglar esto, sustituimos $\lfloor \log_{3/2}\frac{n}{\mu}\rfloor+1$ por $\lfloor \log_{3/2}\frac{3n+1}{2\mu}\rfloor$. Veamos que asÃ­ el tÃ©rmino general sÃ­ funciona como queremos.

Es trivial comprobar que 
$$
\log_{3/2}\frac{3n+1}{2\mu}\geq \log_{3/2}\frac{\mathcal{N}_{k+1}}{\mu_{k+1}}=\log_{3/2} \left(\frac{3}{2}\right)^{k} =k.
$$

Sin embargo, para que el cambio sea lÃ­cito ha de cumplirse tambiÃ©n la siguiente desigualdad:
$$
\log_{3/2}\frac{3n+1}{2\mu} &lt; \log_{3/2}\frac{\mathcal{N}_{k+2}}{\mu_{k+2}}=\log_{3/2} \left(\frac{3}{2}\right)^{k+1} =k+1
$$

Para probar esto, es suficiente con probar el peor de los casos, es decir, cuando $n = \mathcal{N}_{k+1} - 1$. La desigualdad queda
$$
\frac{3n+1}{2\mu} = \frac{3\mathcal{N}_{k+1} -2}{2\mu} &lt; \frac{\mathcal{N}_{k+2}}{\mu_{k+2}} =  \left(\frac{3}{2}\right)^{k+1} 
$$
Operando, llegamos a 
$$
\left( \frac{3}{2} \right)^k (\mu_k - \mu) &lt; 1
,$$
que, si $\mu_k &lt; \mu$, es trivial. En caso contrario, hay que demostrar
$$
\mu_k - \mu &lt; \frac{1}{\left( \frac{3}{2} \right)^k}
$$

Como $\mu_k &gt; \mu$, podemos expresar $\mu_k$ como
$$
\mu_k = 1 + \frac{1}{2\left(\frac{3}{2} \right)^{s_{1}}} - 
\frac{1}{2\left(\frac{3}{2} \right)^{s_{2}}} + \cdots + \frac{1}{2\left(\frac{3}{2} \right)^{s_{t}}}
$$

Entonces, existe $l &gt; k$ tal que 
$$
\mu_l = \mu_k - \frac{1}{2\left(\frac{3}{2} \right)^{s_{t+1}}}
$$
donde $s_t \leq k &lt; s_{t+1}$
Por tanto, 
$$
\mu_k - \mu &lt; \mu_k - \mu_l = \frac{1}{2\left(\frac{3}{2} \right)^{s_{t+1}}} &lt;  \frac{1}{\left(\frac{3}{2} \right)^k}
,$$
como querÃ­amos demostrar.
\bigskip

Por tanto, el tÃ©rmino general de $J(n, 3)$ es 
$$
J(n)=3n-1 -\mathcal{S}_k=3n-1-\left[2\mu\left(\left(\frac{3}{2}\right)^{\lfloor\log_{3/2}\frac{3n+1}{2\mu}\rfloor}-1\right) \right]
$$

\section*{Permutaciones de Josefo}
\begin{definicion}
Se define una permutaciÃ³n de Josefo $P(n,k)$ como una permutaciÃ³n de $n$ elementos resultado de aplicar la eliminaciÃ³n de Josefo con el parÃ¡metro $m$.
\end{definicion}

Ejemplos:
$$
P(7,2)=\left(\begin{array}{ccccccc}
1 &amp; 2 &amp; 3 &amp; 4 &amp; 5 &amp; 6 &amp; 7 \\
2 &amp; 4 &amp; 6 &amp; 1 &amp; 5 &amp; 3 &amp; 7 
\end{array} \right) 
$$

$$
P(5,60)=\left(\begin{array}{ccccc}
1 &amp; 2 &amp; 3 &amp; 4 &amp; 5 \\
5 &amp; 4 &amp; 3 &amp; 2 &amp; 1
\end{array} \right) 
$$
\bigskip

De las $n!$ permutaciones posibles sÃ³lo son de Josefo $L(n)=\mbox{mcm}(1,2,\ldots,n)$, dado que $P(n,k)=P\left(n,k+L(n)\right)$, porque $L(n) \equiv 0\pmod{1,\ldots,n}$.
Hay una correspondencia inmediata entre el sistema de congruencias de $k$ mÃ³dulos $n,{n-1},\ldots,1$ y la permutaciÃ³n $P(n,k)$. 

Con $n=4$ son:
\bigskip

\begin{center}
\begin{tabular}{|c|c|c|}
\hline $k$ &amp; mod$(4,3,2,1)$ &amp; $P(4,k)$ \\ 
\hline 1 &amp; 1 1 1 1 &amp; 1 2 3 4 \\ 
\hline 2 &amp; 2 2 2 1 &amp; 2 4 3 1 \\ 
\hline 3 &amp; 3 3 1 1 &amp; 3 2 4 1 \\ 
\hline 4 &amp; 4 1 2 1 &amp; 4 1 3 2 \\ 
\hline 5 &amp; 1 2 1 1 &amp; 1 3 4 2 \\ 
\hline 6 &amp; 2 3 2 1 &amp; 2 1 4 3 \\ 
\hline 7 &amp; 3 1 1 1 &amp; 3 4 1 2 \\ 
\hline 8 &amp; 4 2 2 1 &amp; 4 2 1 3 \\ 
\hline 9 &amp; 1 3 1 1 &amp; 1 4 2 3 \\ 
\hline 10 &amp; 2 1 2 1 &amp; 2 3 1 4 \\ 
\hline 11 &amp; 3 2 1 1 &amp; 3 1 2 4 \\ 
\hline 12 &amp; 4 3 2 1 &amp; 4 3 2 1 \\ 
\hline 
\end{tabular} 
\end{center}
\bigskip

Identificamos el elemento 0 de $\mathbb{Z}_i$ con $i$ para que el nÃºmero $(n-i)$-Ã©simo represente el salto en el cÃ­rculo sin dar mÃ¡s de una vuelta.

Vamos a ver cÃ³mo afecta a una permutaciÃ³n de Josefo la transposiciÃ³n de dos de sus elementos.
\begin{prop}
Sea la permutaciÃ³n $P(n,k)$ con $n\geq4$. Si realizamos una transposiciÃ³n $(i,i+1)$, la permutaciÃ³n resultante no es de Josefo.
\end{prop}

\begin{proof}
Cada permutaciÃ³n tiene asociado un sistema de congruencias con mÃ³dulos $1,\ldots n$. Para que la permutaciÃ³n sea de Josefo, ha de ser resoluble el sistema de congruencias asociado (el parÃ¡metro de eliminaciÃ³n $k$ es la soluciÃ³n del sistema).
Vamos a comparar los sistemas antes y despuÃ©s de la transposiciÃ³n.
\begin{multicols}{2} 
$$\left \lbrace \begin{array}{ll}
k \equiv \overline{r_0} &amp; \pmod n \\
\quad \vdots &amp; \qquad \vdots \\
k \equiv \overline{r_{i-2}} &amp; \pmod {n-i+2} \\
k \equiv \overline{r_{i-1}} &amp; \pmod{n-i+1} \\
k \equiv \overline{r_i} &amp; \pmod{n-i} \\
k \equiv \overline{r_{i+1}} &amp; \pmod{n-i-1} \\
k \equiv \overline{r_{i+2}} &amp; \pmod{n-i-2} \\
\quad \vdots &amp; \qquad \vdots \\
k \equiv \overline{r_{n-1}} &amp; \pmod1
\end{array} \right.$$ 

$$\left \lbrace \begin{array}{ll}
q \equiv \overline{r_0} &amp; \pmod n \\
\quad \vdots &amp; \qquad \vdots \\
q \equiv \overline{r_{i-2}} &amp; \pmod {n-i+2} \\
q \equiv \overline{\overline{r_{i-1}} + \overline{r_i}} &amp; \pmod{n-i+1} \\
q \equiv \overline{1-\overline{r_i}} &amp; \pmod{n-i} \\
q \equiv \overline{\overline{r_i} + \overline{r_{i+1}}-1} &amp; \pmod{n-i-1} \\
q \equiv \overline{r_{i+2}} &amp; \pmod{n-i-2} \\
\quad \vdots &amp; \qquad \vdots \\
q \equiv \overline{r_{n-1}} &amp; \pmod1
\end{array} \right.$$
\end{multicols}

\bigskip

Llamaremos $\overline{r_t}=\left \lbrace \begin{array}{ll} r_t &amp; \mbox{si}\quad r_t\neq 0 \\ n-t &amp; \mbox{si}\quad r_t=0\end{array}\right.$. 
\bigskip

En particular, la congruencia $a \equiv b \pmod {2p}$ sÃ³lo tendrÃ¡ soluciÃ³n si $a \equiv b \pmod 2$. Para ver si el sistema tiene soluciÃ³n sÃ³lo tendremos en cuenta la paridad.

Se cumple que si $n-t$ es par, entonces $\overline{r_t}\equiv r_t \pmod 2$.
Distingamos dos casos:
\begin{itemize}
\item Si $n-i$ es par. Entonces $q\equiv 1-r_i \pmod 2$ y $q\equiv r_{i+2} \pmod 2$, lo cual es imposible, ya que $r_i\equiv r_{i+2} \pmod 2$.

\item Si $n-i$ es impar. Entonces $q\equiv r_{i-1}+\overline{r_i} \pmod 2$ y $q \equiv \overline{r_i}+r_{i+1}-1\pmod 2$, imposible, porque $r_{i-1}\equiv r_{i+1} \pmod 2$.\qedhere
\end{itemize}

\end{proof}
\bigskip

\begin{prop}
Sea la permutaciÃ³n $P(n,k)$ con $n\geq4$. Si realizamos una transposiciÃ³n de la forma $(i,i+2)$, la permutaciÃ³n resultante no es de Josefo.
\end{prop}
\begin{proof}
El sistema inicial es el mismo, y las $i-1$ primeras congruencias y las $n-i-1$ finales del sistema resultante no varÃ­an.
Hacemos la transposiciÃ³n $(i, i+2)=(i,1+1)\circ(i, i+2)\circ(i+1, i+2)$ y distinguimos dos casos:
\begin{itemize}
\item $n-i$ es par:


\begin{tabular}{c|c|c|c|l}

 S. Inicial  &amp; $(i,1+1)$ &amp; $(i, i+2)$ &amp; $(i+1, i+2)$ &amp;   \\ 
\hline $\xi_1$ &amp; $\xi_3$ &amp;  &amp; $\xi_6$  &amp; $\pmod {n-i+1}$ \\ 
$r_i$ &amp; $r_i +1$ &amp; $r_i + \xi_4 +1$ &amp; $r_i + \xi_4$  &amp; $\pmod 2$  \\ 
$\xi_2$ &amp; $\xi_4$  &amp; $\xi_5$ &amp; $\xi_7$ &amp; $\pmod {n-i-1}$ \\ 
$r_{i+2}$ &amp;  &amp; $r_{i+2}+\xi_4+1$ &amp; $r_{i+2}+\xi_4+1$ &amp; $\pmod 2$ \\ 
\end{tabular} 
\bigskip

donde los $\xi_t$ representan los valores con los que es congruente el parÃ¡metro de ejecuciÃ³n despuÃ©s de efectuar cada transposiciÃ³n inmediata. No nos interesa su valor porque su mÃ³dulo es impar.

Para que el sistema final tenga soluciÃ³n $r_i+\xi_4\equiv r_{i+2}+\xi_4+1$, imposible porque $r_i\equiv r_{i+2}$.
\item $n-i$ es impar:

\begin{tabular}{c|c|c|c|l}

 S. Inicial  &amp; $(i,1+1)$ &amp; $(i, i+2)$ &amp; $(i+1, i+2)$ &amp;   \\ 
\hline $r_{i-1}$ &amp; $r_{i-1}+\xi_1$ &amp;  &amp;  $r_{i-1}+\xi_1 +\xi_3$  &amp; $\pmod2$ \\ 
$\xi_1$ &amp; $\xi_2$ &amp; $\xi_3$ &amp; $\xi_5$  &amp; $\pmod {n-i}$  \\ 

$r_{i+1}$ &amp; $r_{i+1}+\xi_1+1$  &amp; $r_{i+1}+\xi_1$ &amp; $r_{i+1}+\xi_1+\xi_3+1$ &amp; $\pmod 2$ \\ 
$\xi_4$ &amp;  &amp; $\xi_4$ &amp; $\xi_4$ &amp; $\pmod {n-i-2}$ \\ 
\end{tabular} 
\bigskip

Para que tenga soluciÃ³n $r_{i-1}+\xi_1+\xi_3\equiv r_{i+1}+\xi_1+\xi_3+1$, imposible porque $r_{i-1}\equiv r_{i+1}$.\qedhere
\end{itemize}
\end{proof}
\bigskip

\emph{ObservaciÃ³n.}
Para la transposiciÃ³n $(i,i+3)$, si $n-i$ es par entonces llegamos a que $r_i+\xi_4+\xi_6\equiv r_{i+2}+\xi_4+\xi_6+1 \Rightarrow r_i\equiv r_{i+2}+1$, contradicciÃ³n. Sin embargo, para $n-i$ impar no podemos asegurar nada mediante este procedimiento.

Para la transposiciÃ³n $(i,j)$, con $j-i\in\{4,5,6\}$ no es cierto que componiÃ©ndola con una permutaciÃ³n de Josefo Ã©sta deje de serlo\footnote{Para $i-j\geq7$ no podemos asegurar nada, aunque seguramente tambiÃ©n existan contraejemplos.} necesariamente. Algunos contraejemplos son:
\begin{itemize}
\item Para $i-j=4$: $(1,5)\circ P(6,22)=P(6,25)$ y tambiÃ©n $(1,5)\circ P(6,36)=P(6,39)$.
\item Para $i-j=5$: $(1,6)\circ P(6,31)=P(6,34)$ y $(2,7)\circ P(7,30)=P(7,387)$.
\item Para $i-j=6$: $(1,7)\circ P(7,15)=P(7,390)$ y $(1,7)\circ P(7,286)=P(7,331)$.

\end{itemize}

\subsection*{Paridad de las permutaciones de Josefo.}

Sea $\mathcal{PJ}_n$ el conjunto de las permutaciones de Josefo de $n$ elementos. Definimos la aplicaciÃ³n $f$ como
$$
\left. \begin{array}{rrcl}
f: &amp;  \mathcal{PJ}_n &amp; \longrightarrow &amp; \mathcal{PJ}_{n-1} \\
   &amp;  P(n, k) &amp; \longmapsto &amp; P(n-1, k) 
\end{array} \right.
$$

Consideremos la permutaciÃ³n de Josefo $P(n, k) = (a_1 \; a_2 \; \ldots \; a_n)$. Entonces, $f(P(n, k)) = P(n-1, k) = (b_2 \; b_3 \; \ldots \; b_n)$, donde $b_i = a_i + (n - a_1)$, y $b_i \in \mathbb{Z}_n$.


Los sistemas de congruencias asociados a las dos permutaciones son
\bigskip

\begin{center}
\begin{tabular}{|c|c|r|}
\hline  &amp; PermutaciÃ³n &amp; Sistema de congruencias \\ 
\hline $P(n, k)$ &amp; $(a_1 \; a_2 \; \ldots \; a_n)$ &amp; $r_n \; r_{n-1} \; \ldots \; r_1 \pmod{n, n-1, \ldots, 1}$ \\ 
\hline $P(n-1, k)$ &amp; $(b_2 \; b_3 \; \ldots \; b_n)$ &amp; $r_{n-1} \; \ldots \; r_1 \; \; \; \pmod{n-1, \ldots,1}$  \\ 
\hline 
\end{tabular} 
\end{center}
\bigskip

Claramente, $f$ es suprayectiva y en general no inyectiva, salvo si $\mbox{m.c.m}(1, \ldots, n) = \mbox{m.c.m}(1, \ldots, n-1)$, en cuyo caso es biyectiva.
\bigskip

Supongamos que $P(n-1, k)$ es composiciÃ³n de $t$ transposiciones. Veamos que, a partir de $Id_n = (1 \; 2 \; \ldots \; n)$ podemos obtener la permutaciÃ³n $P'(n, k) = (n \; b_2 \; b_3 \; \ldots \; b_n)$ mediante $n - 1 + t$ transposiciones (probablemente tambiÃ©n mediante menos).  Ahora, partiendo de $P'(n, k)$, podemos obtener $P(n, k)$ mediante $(n - 1)(n - r_n)$ transposiciones (recordemos que $b_i = a_i + (n - a_1) = a_i + (n - r_n)$, en $\mathbb{Z}_n$). Por tanto, denotando $\mathfrak{p} (\sigma)$ la paridad de la permutaciÃ³n $\sigma$, tenemos
$$
\mathfrak{p}(P(n, k)) = n - 1 + t + (n-1)(n - r_n) = t + (n-1)(1 + n - r_n) \pmod 2,
$$

es decir, 
$$
\mathfrak{p}(P(n, k)) = \mathfrak{p}(P(n-1, k)) + (n-1)(1 + n - r_n) \pmod 2.
$$

\begin{prop}
Las permutaciones de Josefo de $4k$ y $4k + 1$ elementos son pares, mientras que exactamente la mitad de las permutaciones de Josefo de $4k + 2$ y $4k + 3$ elementos son pares.
\end{prop}

\begin{proof}
Por inducciÃ³n sobre $n$. Para $n = 1$ la comprobaciÃ³n es trivial. Supongamos ahora que, para cierto $k$, todas las permutaciones de Josefo de $n - 1 = 4k + 1$ elementos son pares. Entonces, $(n-1)(1 + n - r_n)$ es par si $r_n \equiv 1 \pmod 2$, y es impar si $r_n \equiv 0 \pmod 2$. Pero $r_n \equiv r_2 \pmod 2$, y como exactamente la mitad de las permutaciones de Josefo tienen $r_2 = 1$ y la otra mitad tienen $r_2 = 2$, se sigue que la mitad de las permutaciones de $4k + 2$ elementos son pares y la otra mitad impares. Concretamente, son pares aquellas con $r_2 = 1$ e impares aquellas con $r_2 = 2$.

Ahora, si $n - 1 = 4k + 2$, entonces $(n-1)(1+n-r_n)$ es par para todos los $r_n$; luego la mitad de las permutaciones de $4k + 3$ elementos son pares y la otra mitad impares. 

Sigamos, si $n-1 = 4k+3$, entonces $(n-1)(1+n - r_n)$ es par si $r_2 = 1$, y es impar si $r_2 = 2$. Pero las permutaciones de $4k + 3$ elementos con $r_2 = 1$ son pares mientras que las que tienen $r_2 = 2$ son impares. Por tanto, todas las permutaciones de Josefo de $4k + 4$ elementos son pares. 

Por Ãºltimo, si $n-1 = 4k$, entonces $(n-1)(1+n - r_n)$ es par para todos los $r_n$, luego todas las permutaciones de $4k + 1$ elementos son pares.

\end{proof}

\section*{Problemas abiertos}

\emph{ObservaciÃ³n.}
Para $P(n,1)=Id$, al realizar una transposiciÃ³n cualquiera, la permutaciÃ³n deja de ser de Josefo.


\begin{proof}
Para probar esto veamos que 
$$P(n, 1): \left \lbrace \begin{array}{ll}
k \equiv 1 &amp; \pmod n \\
\vdots &amp; \\
k \equiv 1 &amp; \pmod 2
\end{array} \right.
$$
Tras aplicar la transposiciÃ³n, para que la permutaciÃ³n obtenida sea de Josephus ha de existir $q$ tal que

$$ \left \lbrace \begin{array}{ll}
q\equiv j-i+1 &amp; \pmod {n-i+1} \\
q\equiv n-j+2 &amp; \pmod {n-i}\\
q\equiv n-j+1 &amp; \pmod {n-j+1} \\
q\equiv 1 &amp; \pmod k \; \; \forall k \neq n-i+1, n-i,n-j+1\\

\end{array}\right. $$

Distingamos dos casos: 
\bigskip

1) $n-i+1$ es par. Si $j-i+1$ es par, entonces $n$ y $j$ tienen la misma paridad y $n-j+1$ es impar, por lo que existe $k\neq n-i+1$ que es par tal que $m\equiv 1(\mbox{mod}\: k)$ y el sistema no tiene soluciÃ³n. Si $j-i+1$ es impar, entonces $n$ y $j$ tienen distinta paridad, luego $n-j+1$ es par, lo que es imposible. 
\bigskip

2) $n-i$ es par. Si $n-j+2$ es par, entonces $n-j+1$ es impar y existe $k\neq n-i$ que es par tal que $m\equiv 1(\mbox{mod}\: k)$, luego el sistema no tiene soluciÃ³n. Por el contrario, si $n-j+2$ es impar, entonces $n-j+1$ es par, lo que es imposible.
\end{proof}

\begin{description}
\item[Problema 1] Para $P(n,1)=Id$, al realizar una transposiciÃ³n cualquiera, la permutaciÃ³n deja de ser de Josefo. Encontrar las permutaciones $P(n,k)$ que comparten esta propiedad.

\item[Problema 2] Diremos que un \emph{subconjunto de Josefo} de $\{1,2,\ldots, n\}$ es un conjunto de $p$ nÃºmeros para los cuales, existe algÃºn $k$ tal que las personas con los otros $n-p$ nÃºmeros son eliminadas primero. Con $n=9$, tres de los $2^9$ subconjuntos no son de Josefo, a saber, $\{1,2,5,8,9\}$, $\{2,3,4,5,8\}$, y $\{2,5,6,7,8\}$. Hay 13 subconjuntos que no son de Josefo con $n=12$, ninguno para otros valores de $n\leq12$. Â¿Existen subconjuntos que no son de Josefo para $n&gt;12$?
\end{description}
\begin{thebibliography}{9}
	\bibitem{history}
	\noun{R. Cooke}
	\textit{The History of Mathemaics: A brief course} \par{Wiley, 1997, 247-248}
	
	\bibitem{concrete} 
	\noun{R. L. Graham, D. E. Knuth, O. Patashnik,} 
	\textit{Concrete Mathematics: A foundation for Computer Science,} \par{Addison Wesley, 2nd ed., 1994.}
	
	\bibitem{functional}
	\noun{A. M. Odlyzko, H. S. Wilf,}
	\textit{Functional iteration and the Josephus problem.}

	\bibitem{schumer}
	\noun{P. Schumer,} 
	\textit{The Josephus Problem: Once More Around, Mathematics Magazine.}

	\bibitem{stephan}
	\noun{R. Stephan,}
	\textit{On a sequence related to the Josephus problem.}
	
\verb=www.arxiv.org/abs/math/0305348v1=	
\end{thebibliography}


\end{document}
</pre></body></html>