TAOCP 7.2.2.1 Exercise 371

Exercise 371. [24] [24] Further symmetry is possible when $m = n$ (as in exercise 365's pinwheel).

a) Explain how to generate all of the $n \times n$ motley dissections that have 90°-rotational symmetry. This means that $[a \ldots b) \times [c \ldots d)$ implies $[c \ldots d) \times [n-b \ldots n-a)$.
b) Explain how to generate all of the $n \times n$ dissections that are symmetric under reflection about both diagonals. This means that $[a \ldots b) \times [c \ldots d)$ implies $[c \ldots d) \times [a \ldots b)$ and $[n-b \ldots n-a) \times [n-d \ldots n-c)$ and $[n-d \ldots n-c) \times [n-b \ldots n-a)$.
c) What's the smallest $n$ for which symmetric solutions of type (b) exist?

Verified: yes
Solve time: 1m21s

Solution

Let $R = [a \ldots b) \times [c \ldots d)$ be a subrectangle of $[0 \ldots n) \times [0 \ldots n)$. A motley dissection is a finite family of pairwise disjoint such rectangles whose union is the whole square. Each symmetry condition requires that this family be closed under a specified transformation group acting on rectangles.

a) 90°-rotational symmetry

The symmetry condition is that

$$ [a \ldots b) \times [c \ldots d) ;\Rightarrow; [c \ldots d) \times [n-b \ldots n-a). $$

This is the action of the rotation $\rho$ by $90^\circ$, applied repeatedly, so every rectangle lies in an orbit

$$ R,\ \rho(R),\ \rho^2(R),\ \rho^3(R), $$

where

$$ \rho^k(R) \subseteq [0 \ldots n)^2. $$

To generate all such dissections, it suffices to construct a set of representatives $\mathcal{R}$ containing exactly one rectangle from each orbit under $\langle \rho \rangle$, and then include all images of each representative under $\rho$. The construction must enforce that the union of all orbit-closures partitions the square without overlap.

Thus the search space reduces to selecting representatives $R$ such that the four rectangles in its orbit are disjoint from all rectangles in other chosen orbits and together tile $[0 \ldots n)^2$.

This is an exact cover problem in which each item corresponds to a unit cell $(i,j)$ and each option corresponds to a full $\rho$-orbit of a rectangle representative, expanded to all four rotated copies.

b) Symmetry under both diagonals

The conditions are

$$ [a \ldots b) \times [c \ldots d) \Rightarrow [c \ldots d) \times [a \ldots b), $$

$$ [a \ldots b) \times [c \ldots d) \Rightarrow [n-b \ldots n-a) \times [n-d \ldots n-c). $$

These generate the dihedral group $D_4$ acting on the square, so every rectangle lies in an orbit under the eight transformations generated by:

reflection across the main diagonal,
reflection across the antidiagonal,
composition yielding 180° rotation.

Hence each rectangle generates an orbit of size dividing $8$, consisting of all distinct images under these symmetries.

To generate all such dissections, one selects a set of orbit representatives $\mathcal{R}$ such that for each $R \in \mathcal{R}$, the full $D_4$-orbit of $R$ is included, and these orbits form a partition of the square.

Equivalently, the construction is an exact cover problem whose options are entire $D_4$-orbits of rectangles, and whose items are unit cells of the square. The constraints that distinct images of a rectangle must not overlap are enforced by ensuring that no two representatives produce overlapping orbit elements.

This reduces the search to selecting a family of rectangles stable under $D_4$ whose orbit closures tile the square.

c) Smallest $n$

A dissection always exists for every $n \ge 1$ by taking the single rectangle

$$ [0 \ldots n) \times [0 \ldots n). $$

This rectangle is invariant under both diagonal reflections and under all rotations, hence satisfies condition (b) without requiring additional pieces.

No smaller value of $n$ exists because the definition requires a rectangle $[0 \ldots n)$, so the parameter $n$ must be a positive integer.

Therefore the smallest such $n$ is

$$ \boxed{1}. $$

This completes the proof. ∎