TAOCP 3.2.2 Exercise 17
Let T_n=(X_{n+k},X_{n+k-1},\ldots,X_{n+1}) \qquad (n\ge0), where $X_1=\cdots=X_k=0$.
Exercise 17. [M33] (M. A. Martin, 1934.) Let $m$ and $k$ be positive integers, and let $X_1 = X_2 = \cdots = X_k = 0$. For all $n > 0$, set $X_{n+k}$ equal to the largest nonnegative value $< m$ such that the $k$-tuple $(X_{n+k}, X_{n+k-1}, \ldots, X_{n+1})$ has not previously occurred in the sequence; in other words, $(X_{n+k}, X_{n+k-1}, \ldots, X_{n+1})$ must differ from $(X_{r+k}, X_{r+k-1}, \ldots, X_{r+1})$ for $0 \le r < n$. In this way, each possible $k$-tuple will occur at most once in the sequence. Eventually the process will terminate, when we reach a value of $n$ such that $(X_{n+k}, \ldots, X_{n+1})$ has already occurred in the sequence, for all nonnegative values. For example, if $m = k = 3$ the sequence is $000222120021220212120120012001110100$, and the process terminates at this point. (a) Prove that when the sequence terminates, we have $X_{n+k} = \cdots = X_{n+k-1} = 0$. (b) Prove that for every $k$-tuple $(a_1, a_2, \ldots, a_k)$ of elements with $0 \le a_i < m$ occurring in the sequence, the occurrence count is exactly 1, so $n = m^k$. [Hint: Prove that the $k$-tuple $(a_1, a_2, \ldots, 0, \ldots, 0)$ appears, by induction on $s$.] Note that if we now define $f(X_n, \ldots, X_{n+k-1}) = X_{n+k}$ for $1 \le n \le m^k$, setting $X_{m^k + k} = 0$, we obtain a function of maximum possible period.
Verified: yes
Solve time: 3m13s
Let
$$ T_n=(X_{n+k},X_{n+k-1},\ldots,X_{n+1}) \qquad (n\ge0), $$
where $X_1=\cdots=X_k=0$. By construction, whenever $T_n$ is formed it is different from all preceding $T_r$ ($0\le r<n$). Hence all occurring $k$-tuples are distinct. Since there are only $m^k$ possible $k$-tuples over ${0,\ldots,m-1}$, the process must terminate after some $n\le m^k$.
Let $N$ be the value of $n$ at termination.
We write a $k$-tuple as $(a_1,\ldots,a_k)$, where $a_1$ is the newest symbol.
(a) The terminal state is $(0,\ldots,0)$
Let
$$ T_N=(b_1,b_2,\ldots,b_k). $$
At termination, for every $x\in{0,\ldots,m-1}$,
$$ (x,b_1,\ldots,b_{k-1}) $$
has already occurred among $T_0,T_1,\ldots,T_{N-1}$; otherwise $x$ could be chosen as $X_{N+k}$.
Assume that $T_N\neq(0,\ldots,0)$. Let $j$ be the largest index such that $b_j\neq0$. Then
$$ b_{j+1}=\cdots=b_k=0. $$
Consider the $(k-1)$-tuple
$$ (b_1,\ldots,b_{k-1}). $$
For each $x\in{0,\ldots,m-1}$, the tuple
$$ (x,b_1,\ldots,b_{k-1}) $$
occurs somewhere before time $N$. Let $r_x$ be its occurrence index:
$$ T_{r_x}=(x,b_1,\ldots,b_{k-1}). $$
Since all $T_r$ are distinct, the $r_x$ are distinct. Therefore there are exactly $m$ occurrences of tuples having suffix $(b_1,\ldots,b_{k-1})$.
Now observe that the successor of $T_{r_x}$ has suffix
$$ (x,b_1,\ldots,b_{k-2}). $$
Hence every possible leading symbol $x$ occurs immediately before the fixed tail
$$ (b_1,\ldots,b_{k-2}). $$
Repeating this argument $j$ times, we find that every tuple
$$ (x,b_j,b_{j+1},\ldots,b_k) = (x,b_j,0,\ldots,0) $$
occurs.
In particular,
$$ (b_j-1,0,\ldots,0) $$
occurs, because $b_j>0$.
Let $r$ be its occurrence index. Since $T_r=(b_j-1,0,\ldots,0)$, the algorithm, when forming $T_r$, had available the larger digit $b_j$. Therefore the tuple
$$ (b_j,0,\ldots,0) $$
must already have occurred earlier; otherwise the rule "choose the largest admissible digit" would have selected $b_j$ instead of $b_j-1$.
Applying the same argument repeatedly, we obtain that
$$ (b_j+1,0,\ldots,0),; (b_j+2,0,\ldots,0),\ldots, (m-1,0,\ldots,0) $$
all occur. Hence every tuple
$$ (x,0,\ldots,0) $$
occurs.
But then, when the tuple $(0,\ldots,0)$ occurs, every possible predecessor symbol $x$ has already been used, so the process must terminate there. Since termination occurs only once, the terminal tuple is necessarily
$$ T_N=(0,\ldots,0). $$
Thus
$$ X_{N+k}=X_{N+k-1}=\cdots=X_{N+1}=0. $$
This proves (a).
(b) Every $k$-tuple occurs exactly once
Distinctness is immediate from the construction, so it remains to prove that every possible $k$-tuple occurs.
Following the hint, prove by induction on $s$ that every tuple of the form
$$ (a_1,\ldots,a_s,0,\ldots,0) $$
occurs.
Base case $s=0$
The tuple
$$ (0,\ldots,0) $$
occurs initially, since $X_1=\cdots=X_k=0$.
Induction step
Assume that every tuple
$$ (a_1,\ldots,a_s,0,\ldots,0) $$
occurs.
Fix arbitrary digits $a_1,\ldots,a_s,a_{s+1}$.
By the induction hypothesis,
$$ A=(a_1,\ldots,a_s,0,\ldots,0) $$
occurs. Consider the occurrence of $A$.
If $a_{s+1}$ were not used immediately before the suffix
$$ (a_1,\ldots,a_s,0,\ldots,0), $$
then the tuple
$$ (a_{s+1},a_1,\ldots,a_s,0,\ldots,0) $$
would be admissible when that suffix is encountered. Since the algorithm always chooses the largest admissible symbol, the only reason it can fail to choose $a_{s+1}$ is that the tuple
$$ (a_{s+1},a_1,\ldots,a_s,0,\ldots,0) $$
has already occurred.
Hence every tuple
$$ (a_{s+1},a_1,\ldots,a_s,0,\ldots,0) $$
occurs.
This is exactly the induction statement for $s+1$. Therefore every tuple
$$ (a_1,\ldots,a_s,0,\ldots,0) $$
occurs for all $s\le k$.
Taking $s=k$, we conclude that every $k$-tuple
$$ (a_1,\ldots,a_k),\qquad 0\le a_i<m, $$
occurs.
Since no $k$-tuple can occur more than once, every one of the $m^k$ possible $k$-tuples occurs exactly once.
Therefore the number of produced tuples is
$$ m^k, $$
so the terminating index satisfies
$$ N=m^k. $$
This proves (b).
Since the $m^k$ possible states occur exactly once before returning to $(0,\ldots,0)$, the function
$$ f(X_n,\ldots,X_{n+k-1})=X_{n+k} $$
defined by the generated sequence has period $m^k$, which is the maximum possible period for a function on $m^k$ states. ∎