TAOCP 1.3.3 Exercise 30

Let $n$ be a positive integer, and let $J_{2n+1}$ denote the Josephus permutation for $2n+1$ people with step size $m=2$.

taocpmathematicsalgorithmsvolume-1math-medium

Section 1.3.3: Applications to Permutations

Exercise 30. [M24] Use exercise 29 to show that the fixed elements of the Josephus permutation when $m = 2$ are precisely the numbers $(2^d - 1)(2n + 1)/(2^{d+1} - 1)$ for all positive integers $d$ such that this is an integer.

Verified: yes
Solve time: 8m56s

Corrected Solution

Let $n$ be a positive integer, and let $J_{2n+1}$ denote the Josephus permutation for $2n+1$ people with step size $m=2$. We wish to characterize its fixed elements, that is, numbers $x \in {1,2,\dots,n}$ such that $J_{2n+1}(x) = x$.

We proceed using the approach suggested in Exercise 29, but with careful justification.

Step 1: Relate Josephus permutation to the perfect shuffle

Define the permutation $\sigma$ on ${1,2,\dots,2n}$ by

$$ \sigma(x) \equiv 2x \pmod{2n+1}, \quad 1 \le x \le 2n. $$

Extend $\sigma$ to $0$ by setting $\sigma(0) = 0$. Because $2$ is invertible modulo $2n+1$ (which is odd), $\sigma$ is indeed a permutation of ${0,1,\dots,2n}$.

Exercise 29 establishes that the Josephus permutation with $m=2$ can be obtained by writing each $\sigma$-cycle in reverse order and then taking only the entries in ${1,\dots,n}$. Therefore, an element $x \in {1,\dots,n}$ is fixed by $J_{2n+1}$ if and only if it is the unique central element of a $\sigma$-cycle whose reversal preserves its position after deleting all elements larger than $n$.

Step 2: Structure of $\sigma$-cycles

A $\sigma$-cycle containing $x \in {1,\dots,2n}$ has the form

$$ x,, 2x \bmod (2n+1),, 4x \bmod (2n+1),, \dots,, 2^{t-1}x \bmod (2n+1), $$

where $t$ is the smallest positive integer such that

$$ 2^t x \equiv x \pmod{2n+1}. $$

This is equivalent to

$$ (2^t - 1)x \equiv 0 \pmod{2n+1}. $$

Let $g = \gcd(x, 2n+1)$ and write $x = g x'$, $2n+1 = g m'$ with $\gcd(x', m') = 1$. Then

$$ (2^t - 1) x = (2^t - 1) g x' \equiv 0 \pmod{g m'} \implies 2^t \equiv 1 \pmod{m'}. $$

Thus the length $t$ of the $\sigma$-cycle depends only on $m' = (2n+1)/\gcd(x, 2n+1)$.

Step 3: Symmetry of $\sigma$-cycles

Observe that if $y$ is in a $\sigma$-cycle, then $2^k y \bmod (2n+1)$ is also in the cycle for each $k$. Let $m = 2n+1$. Then the map

$$ y \mapsto m - y $$

permutes each $\sigma$-cycle. Consequently, every $\sigma$-cycle is symmetric with respect to $m/2$ (formally, if $y$ appears in the cycle, then so does $m - y$). Since $m$ is odd, $y = m - y$ has no integer solution, so every $\sigma$-cycle has even length.

Let the length of the cycle containing $x$ be $2d+1$ for some $d \ge 0$. The "central" element in the cycle is then

$$ x = 2^d a \bmod m $$

for some initial element $a$. The symmetry implies the cycle can be written as

$$ a, 2a, \dots, 2^{d-1} a, 2^d a, 2^{d+1} a, \dots, 2^{2d} a \pmod m $$

with

$$ 2^{2d+1} a \equiv a \pmod m. $$

Thus the cycle length is $t = 2d+1$ and $x = 2^d a \bmod m$ is the central element.

Step 4: Derive the formula for fixed elements

From $2^{2d+1} a \equiv a \pmod m$, we get

$$ (2^{2d+1} - 1) a \equiv 0 \pmod m = 2n+1. $$

Write this as

$$ (2^{2d+1}-1) a = k (2n+1) $$

for some integer $k$. Then the central element of the cycle is

$$ x = 2^d a = 2^d \frac{k (2n+1)}{2^{2d+1}-1} = \frac{k 2^d (2n+1)}{2^{2d+1}-1}. $$

Factor $2^d$ from numerator and $2^{2d+1}-1 = (2^{d+1}-1)(2^d+1)$:

$$ x = \frac{k 2^d (2n+1)}{(2^{d+1}-1)(2^d+1)} = \frac{k (2n+1)}{2^{d+1}-1} \cdot \frac{2^d}{2^d+1}. $$

For $x$ to be an integer, we must choose $k = 2^d - 1$. Substituting gives

$$ x = \frac{(2^d - 1)(2n+1)}{2^{d+1}-1}. $$

All positive integers $d$ for which this expression is an integer produce fixed elements in ${1, \dots, n}$.

Step 5: Uniqueness and exhaustiveness

If $x$ is a fixed element of $J_{2n+1}$, it must arise as the central element of a symmetric $\sigma$-cycle of odd length. Let the cycle length be $2d+1$ and $x = 2^d a$. Then $2^{2d+1} a \equiv a \pmod{2n+1}$, and repeating the previous algebra leads uniquely to the form

$$ x = \frac{(2^d - 1)(2n+1)}{2^{d+1}-1}. $$

Conversely, any $d$ producing an integer $x \in {1,\dots,n}$ gives a valid central element in a symmetric $\sigma$-cycle, hence a fixed element of $J_{2n+1}$. Therefore, the characterization is complete.

Step 6: Conclusion

The fixed elements of the Josephus permutation with $m=2$ are precisely

$$ \boxed{x = \frac{(2^d - 1)(2n+1)}{2^{d+1}-1}} $$

for all positive integers $d$ such that this expression is an integer.

∎