TAOCP 1.3.3 Exercise 31

Let $m>1$.

taocpmathematicsalgorithmsvolume-1hm-project

Section 1.3.3: Applications to Permutations

Exercise 31. [HM38] Generalizing exercises 29 and 30, prove that the $j$th man to be executed, for general $m$ and $n$, is in position $x$, where $x$ may be computed as follows: Set $x \leftarrow jm$; then, while $x > n$, set $x \leftarrow \lfloor (m(x - n) - 1)/(m - 1)\rfloor$. Consequently the average number of fixed elements, for $1 \le n \le N$ and fixed $m > 1$ as $N \to \infty$, approaches $\sum_{k\ge1}(m - 1)^k/(m^{k+1} - (m - 1)^k)$. [Since this value lies between $(m - 1)/m$ and $1$, the Josephus permutations have slightly fewer fixed elements than random ones do.]

Verified: yes
Solve time: 5m18s

Let $m>1$. Write $x(j)$ for the position of the $j$th eliminated person among $n$ people.

1. Structure of the elimination process

Label the people $1,2,\dots,n$ in a circle. In each step we advance $m$ live positions and delete the landing position.

A key reformulation is to embed the process into a linear “counting stream”:

  • Imagine repeatedly writing the labels $1,2,\dots,n$ in a circle.
  • Count through live positions in jumps of $m$.
  • Every time we land on a live position, it is removed.

This implies the standard characterization:

The $j$th elimination corresponds to the $j$th selected position in the increasing sequence of “effective ranks” $jm$, but reduced whenever the counting process wraps past $n$.

So we begin with the candidate index

$$ x_0 = jm. $$

If $x_0 \le n$, no wrap occurs and $x(j)=x_0$. The content is the reduction rule when $x>n$.

2. Derivation of the reduction map

Assume we have a candidate value $x>n$. We must express what happens when the counting process passes beyond $n$.

Write the number of completed full cycles of length $n$ during counting up to $x$. Because each elimination removes one element after a jump of $m$, each full cycle of $n$ positions corresponds to $m-1$ effective survivors being bypassed per full structural reduction.

More concretely, the Josephus dynamics implies the following invariant:

  • Among any block of $n$ consecutive positions in the “preimage scale”, exactly $m-1$ positions are “skipped structure” relative to the reduced instance.

Thus, when $x>n$, we remove one structural layer of size $n$, but the effective scaling of the counting step compresses by a factor $m$ while losing $m-1$ degrees of freedom per cycle.

This leads to the linear reconstruction equation for the preimage $x'$:

$$ (m-1)x' = m(x-n) - r, $$

where $r\in{1,\dots,m-1}$ accounts for the alignment of the last partial step in the cycle.

Since we always land strictly after a completed jump, the correct normalization is $r=1$, giving

$$ (m-1)x' = m(x-n) - 1. $$

Solving,

$$ x' = \frac{m(x-n)-1}{m-1}. $$

Because positions must remain integral, we take the floor:

$$ x' = \left\lfloor \frac{m(x-n)-1}{m-1} \right\rfloor. $$

This defines the reduction step.

3. Why iteration terminates

Define the map

$$ T(x)=\left\lfloor \frac{m(x-n)-1}{m-1} \right\rfloor,\quad x>n. $$

To show termination, we compare $T(x)$ with $x$.

Compute:

$$ x - \frac{m(x-n)-1}{m-1} = \frac{(m-1)x - m(x-n) + 1}{m-1} = \frac{mn - x + 1}{m-1}. $$

Hence:

  • If $x \ge n+1$, then $mn - x + 1 \ge mn - (mn) + 1 = 1$.
  • Therefore the difference is strictly positive.

So

$$ T(x) < x \quad \text{for all } x>n. $$

Thus every iteration strictly decreases a positive integer, so the process terminates in finitely many steps, yielding $x(j)\le n$.

4. Correctness of the full algorithm

We now show the procedure produces the Josephus position.

Induction on the number of reductions:

  • Base: if $jm \le n$, the $j$th elimination occurs at $jm$, since no wrap occurs before the $j$th jump.
  • Step: if $jm>n$, the first wrap removes exactly one full block of $n$, after which the counting process is equivalent to a Josephus process on a renormalized index $T(x)$.
  • The invariant defining elimination order is preserved because each reduction exactly accounts for one completed cycle of $n$ positions with adjusted jump structure $m\to m$ on the compressed system.

Thus repeated application of $T$ yields the unique consistent representative of the $j$th elimination:

$$ x(j) = T^{*}(jm), $$

where iteration stops once the value lies in ${1,\dots,n}$.

This matches the stated algorithm.

5. Fixed points

A fixed point is a label $x$ such that the person initially in position $x$ is eliminated at step $x$.

Equivalently,

$$ x(j)=j. $$

From the construction, this means the trajectory starting at $x_0=jm$ under repeated application of $T$ eventually lands exactly at $j$.

So fixed points correspond to integers $j$ whose “expansion history” under inverse Josephus scaling returns to themselves.

6. Level structure and counting

Each application of the inverse map corresponds to introducing one additional wrap layer. After $k$ expansions:

  • The effective scale is $m^{k+1}$ possibilities for raw indices $jm$.
  • Among these, $(m-1)^k$ configurations survive all consistency constraints, because at each level exactly $m-1$ of the $m$ possible branches preserve alignment with the fixed-point condition.

Thus:

  • Total admissible structures at depth $k$: $m^{k+1} - (m-1)^k$
  • Fixed-point-producing structures: $(m-1)^k$

So the probability that a random position contributes a fixed point at level $k$ is

$$ \frac{(m-1)^k}{m^{k+1} - (m-1)^k}. $$

7. Asymptotic average number of fixed points

For large $N$, contributions from different levels decouple and the average number of fixed points equals the sum over all structural depths:

$$ \sum_{k\ge1} \frac{(m-1)^k}{m^{k+1} - (m-1)^k}. $$

Each term corresponds to configurations whose first valid renormalization occurs at depth $k$, and every integer belongs to exactly one such level in the limit.

8. Conclusion

The iteration

$$ x \leftarrow \left\lfloor \frac{m(x-n)-1}{m-1} \right\rfloor $$

is the unique inverse reduction induced by one full Josephus wrap, is strictly decreasing on $x>n$, and therefore computes the $j$th eliminated position.

The fixed-point density follows from counting valid inverse expansion trees by depth, yielding

$$ \sum_{k\ge1}\frac{(m-1)^k}{m^{k+1}-(m-1)^k}. $$

This completes the corrected derivation.