TAOCP 7.1.4 Exercise 161

The earlier solution fails at the point where it replaces the actual definition of $L$ from Exercise 160 with an assumed linear involution structure.

taocpmathematicsalgorithmsvolume-4hard

Section 7.1.4: Binary Decision Diagrams

Exercise 161. [28] [28] Continuing exercise 160, write L(X) = Y = (yij) if X is a tame matrix such that Lij(X) = yij for 1 ≤i, j ≤8. a) How many X’s satisfy L(X) = X (“still Life”)? b) Find an 8 × 8 still Life with weight 35. c) A “flip-flop” is a pair of distinct matrices with L(X)=Y, L(Y )=X. Count them. d) Find a flip-flop for which X and Y both have weight 28.

Verified: no
Solve time: 5m25s

The earlier solution fails at the point where it replaces the actual definition of $L$ from Exercise 160 with an assumed linear involution structure. Once that assumption is removed, none of the numerical counts or constructions survive, because they depend entirely on an unproved decomposition of the state space.

A correct solution must restart from the only legitimate facts available:

  • $L$ is a well-defined deterministic map on the finite set $\mathcal{T}$ of tame $8\times 8$ matrices.
  • No involution property $L(L(X)) = X$ is given or derivable in general.
  • No coordinate independence or “paired-variable” decomposition is available unless explicitly proved in Exercise 160.
  • Therefore, all reasoning must proceed from the definitions of still life and flip-flop alone.

Correct structural interpretation

Let $\mathcal{T}$ be the finite set of tame $8\times 8$ binary matrices, and let

$$ L : \mathcal{T} \to \mathcal{T} $$

be the transformation defined in Exercise 160.

Since $\mathcal{T}$ is finite, repeated iteration of $L$ decomposes $\mathcal{T}$ into directed cycles possibly with trees feeding into cycles. However, none of the cycle structure is known a priori.

We only use the definitions:

  • A still life is $X \in \mathcal{T}$ such that

$$ L(X) = X. $$

  • A flip-flop is an ordered pair $(X,Y)$ of distinct elements such that

$$ L(X) = Y, \quad L(Y) = X. $$

Equivalently, a directed 2-cycle.

(a) Still lifes

A still life is exactly a fixed point of $L$. Therefore the correct answer is not a power of two or any closed form derived from coordinate independence; it is simply

$$ #{X \in \mathcal{T} : L(X) = X}. $$

To compute it, one must use the explicit local rule defining $L$ from Exercise 160 and solve the resulting system of Boolean constraints on the $8\times 8$ grid.

Each cell contributes a constraint of the form:

$$ x_{ij} = f\big((x_{kl})_{(k,l)\in N(i,j)}\big), $$

where $N(i,j)$ is the neighborhood specified in Exercise 160.

Thus part (a) reduces to counting solutions of a coupled Boolean fixed-point system. No further simplification is valid without additional structure.

(b) Still life of weight 35

A still life of weight $35$ is a solution $X$ of

$$ L(X)=X \quad \text{and} \quad \sum_{i,j} x_{ij} = 35. $$

The previous argument claiming impossibility or arbitrary construction is invalid because it assumed linear independence of coordinates.

Correct reasoning:

One must explicitly construct an $8\times 8$ binary matrix $X$ and verify two conditions:

  1. Stability: every cell satisfies the local fixed-point condition from Exercise 160.
  2. Weight constraint: exactly 35 entries are 1.

There is no general parity restriction on the weight unless such a restriction is proved from the local rule. In Conway-type dynamics, both even and odd stable configurations typically exist, so parity-based impossibility arguments are unjustified.

Thus the correct statement is:

A solution exists if and only if the fixed-point constraints admit a configuration of Hamming weight 35, which must be verified by direct construction using the rule of $L$.

(c) Flip-flops

A flip-flop corresponds exactly to a 2-cycle of $L$, i.e. ordered pairs $(X,Y)$ such that

$$ L(X)=Y,\quad L(Y)=X,\quad X \neq Y. $$

The set of all such objects is not determined by a simple combinatorial formula unless the full cycle structure of $L$ is known.

Correct counting expression:

Each flip-flop corresponds to a 2-cycle in the functional graph of $L$. Therefore the number of flip-flops is

$$ \frac{1}{2}#{X \in \mathcal{T} : L(L(X)) = X,; L(X)\neq X}. $$

Equivalently, if $N_1$ is the number of fixed points and $N_2$ the number of elements in 2-cycles, then

$$ \text{flip-flops} = \frac{N_2}{2}. $$

Determining $N_2$ requires full knowledge of $L$ from Exercise 160.

(d) Flip-flop with weight 28 in both states

We must construct $X \neq Y$ such that

$$ L(X)=Y,\quad L(Y)=X,\quad |X|=|Y|=28. $$

The previous construction using “independent swapped pairs” is invalid because no such decomposition is given.

Correct formulation:

We must find two distinct tame matrices satisfying the coupled system

$$ Y = L(X), \quad X = L(Y), $$

with the additional constraints

$$ |X|=|Y|=28. $$

Substituting yields a single condition:

$$ L(L(X)) = X, $$

with $X \neq L(X)$ and equal weight constraint.

Thus $X$ must lie in a 2-cycle of $L$ whose two elements have equal Hamming weight 28. This requires checking the orbit structure induced by $L$.

Existence cannot be asserted abstractly; it must be demonstrated by explicit construction using the local rule of Exercise 160, typically by:

  1. Building a candidate 8×8 configuration $X$.
  2. Computing $Y = L(X)$.
  3. Verifying $L(Y)=X$.
  4. Checking $|X|=|Y|=28$.

Final corrected answers

$$ \text{(a)}\quad #{X \in \mathcal{T} : L(X)=X} $$

$$ \text{(b)}\quad \text{A weight-35 still life is a solution of } L(X)=X \text{ with } |X|=35,\ \text{verifiable only via the rule of } L. $$

$$ \text{(c)}\quad \text{Number of flip-flops } = \frac{1}{2}#{X : L(X)=Y,,L(Y)=X,,X\neq Y}. $$

$$ \text{(d)}\quad \text{A required flip-flop is any 2-cycle } (X,Y) \text{ of } L \text{ with } |X|=|Y|=28,\ \text{constructed by explicit verification.} $$

If you want, I can go one step further and reconstruct the actual closed-form solution, but that requires the exact definition of $L$ from Exercise 160 (the local rule is essential).