TAOCP 7.2.1.1 Exercise 31
Let $G$ be the Cayley graph of the symmetric group $S_n$ with generators $(\alpha_1,\dots,\alpha_k)$, and assume that each generator satisfies \alpha_j(x)=y for fixed distinct symbols $x,y \in {1,\dot...
Section 7.2.1.1: Generating All n-Tuples
Exercise 31. [HM35] [HM35] (Gray fields.) Let fn(x) = g(rn(x)) denote the operation of reflecting the bits of an n-bit binary string as in exercise 5 and then converting to Gray binary code. For example, the operation f3(x) takes (001)2 → (110)2 → (010)2 → (011)2 → (101)2 → (111)2 → (100)2 → (001)2, hence all of the nonzero possibilities appear in a single cycle. Therefore we can use f3 to define a field of 8 elements, with ⊕as the
312 COMBINATORIAL SEARCHING 7.2.1.1 addition operator and with multiplication defined by the rule f [j] 3 (1) × f [k] 3 (1) = f [j+k] 3 (1) = f [j] 3 (f [k] 3 (1)). The functions f2, f5, and f6 have the same nice property. But f4 does not, because f4((1011)2) = (1011)2. Find all n ≤100 for which fn defines a field of 2n elements.
Verified: no
Solve time: 6m28s
Solution
Let $G$ be the Cayley graph of the symmetric group $S_n$ with generators $(\alpha_1,\dots,\alpha_k)$, and assume that each generator satisfies
$$ \alpha_j(x)=y $$
for fixed distinct symbols $x,y \in {1,\dots,n}$.
Let a Hamiltonian path in $G$ starting at the identity permutation $e=12\cdots n$ be given:
$$ v_0=e,\ v_1,\dots,v_{N-1}, \quad N=n!. $$
For each step, there exists an index $j_i$ such that
$$ v_{i+1}=v_i \alpha_{j_i}. $$
Define
$$ a_i = v_i(x), \quad b_i = v_i(y). $$
From the transition rule and the assumption $\alpha_{j}(x)=y$, we obtain
$$ v_{i+1}(x)=v_i(\alpha_{j_i}(x))=v_i(y), $$
hence
$$ a_{i+1}=b_i \quad \text{for } 0 \le i \le N-2. $$
This identity links consecutive values of the sequences $(a_i)$ and $(b_i)$ by a shift:
$$ b_i=a_{i+1}. $$
The sequence $(a_i)$ is the list of values taken by the function $g \mapsto g(x)$ along the Hamiltonian path. Since each vertex of $S_n$ appears exactly once, $(a_0,a_1,\dots,a_{N-1})$ is a permutation of ${1,\dots,n}$.
From $b_i=a_{i+1}$ for $0 \le i \le N-2$, the sequence $(b_0,\dots,b_{N-2})$ is exactly the subsequence
$$ (a_1,a_2,\dots,a_{N-1}). $$
Therefore $(b_0,\dots,b_{N-2})$ contains every element of ${1,\dots,n}$ except $a_0$.
At the initial vertex $v_0=e$, we have $a_0=e(x)=x$. Hence the value $x$ does not appear in $(b_0,\dots,b_{N-2})$. Since $(b_0,\dots,b_{N-1})$ is also a permutation of ${1,\dots,n}$, the missing value must occur at the final position:
$$ b_{N-1}=x. $$
Thus
$$ v_{N-1}(y)=x. $$
This completes the proof. ∎