TAOCP 7.2.2.1 Exercise 76

Section 7.2.2.1: Dancing Links

Exercise 76. [21] [21] Modify the exact cover problem of exercise 75(d) in order to find the multiplication tables of (a) all idempotent gropes, gropes such that $x \circ x = x$ for all $x$; (b) all commutative gropes, gropes such that $x \circ y = y \circ x$ for all $x$ and $y$; (c) all gropes with the identity element $0$, gropes such that $0 \circ x = 0 = x \circ 0$ for all $x$.

Verified: no
Solve time: 3m21s

Solution

The exact cover formulation of exercise 75(d) already contains one option for each possible local consequence of the grope identity. A restriction on the class of gropes is obtained by deleting the options that violate the additional identities. The remaining exact covers are precisely the desired multiplication tables.

For idempotent gropes, the condition is

$x\circ x=x \qquad (0\leq x<n).$

The only options that affect a diagonal entry $xx$ are the options in which two of the three symbols in an option of type iii coincide. In an option

$xy\ yz\ zx \qquad (x<y\leq z),$

the case $y=z$ represents a non-idempotent diagonal value, because the corresponding diagonal entry is $y\circ y=x$ with $x<y$. Therefore all options

$xy\ yy\ yx \qquad (x<y<n)$

must be deleted. The options of type i and all options of type ii remain, and the options

$xy\ yz\ zx \qquad (x<y<z<n)$

remain. Every remaining option is compatible with $x\circ x=x$, and every idempotent grope avoids the deleted options.

For commutative gropes, the condition is

$x\circ y=y\circ x \qquad (0\leq x,y<n).$

An option of type iii with three distinct elements,

$xy\ yz\ zx \qquad (x<y<z<n),$

forces a directed 3-cycle among three different entries. It cannot occur in a commutative table, because commutativity would require the reverse pairs $yx$, $zy$, and $xz$ to have the same values as $xy$, $yz$, and $zx$. Hence all such options are deleted.

The remaining options of type iii are exactly those with $z=y$,

$xy\ yy\ yx \qquad (x<y<n),$

and these already contain both ordered pairs $xy$ and $yx$. The options of type ii also contain the two ordered pairs $xy$ and $yx$. Thus the modified exact cover problem is obtained by retaining options of types i and ii and retaining only the type iii options with $z=y$.

For gropes with identity element $0$, the required conditions are

$0\circ x=0=x\circ0 \qquad (0\leq x<n).$

The exact cover modification is obtained by forcing the entries in the $0$th row and $0$th column to have value $0$. Equivalently, delete every option from the construction of exercise 75(d) whose implied multiplication table has

$0\circ x\ne0$

$x\circ0\ne0$

for some $x$. The surviving options are precisely those local cycles that are compatible with the fixed entries

$00,\quad 01,\quad 02,\quad\ldots,\quad0(n-1),\quad10,\quad20,\quad\ldots,\quad(n-1)0.$

To implement this directly as an exact cover instance, these fixed entries may instead be covered first by the unique compatible options, and the remaining options are obtained by deleting every option that intersects a fixed entry with a different value. The residual exact cover problem has the same form as exercise 75(d), but its solutions correspond exactly to the multiplication tables satisfying the identity condition.

Thus the three required families are obtained by restricting the original option set as follows:

$$ \begin{array}{c|c} \text{Class of gropes} & \text{Modification of the options}\ \hline \text{idempotent} & \text{delete all }xy\ yy\ yx\text{ with }x<y\[2mm] \text{commutative} & \text{delete all }xy\ yz\ zx\text{ with }x<y<z\[2mm] \text{identity element }0 & \text{delete all options incompatible with }0\circ x=x\circ0=0 \end{array} $$

Each remaining exact cover gives a table satisfying the required extra identities, and each multiplication table satisfying the required extra identities selects only remaining options from the original construction. Hence the modified exact cover problems enumerate exactly the desired gropes. ∎