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: no
Solve time: 6m54s

$$ R=[a\ldots b)\times[c\ldots d) $$

denotes a rectangle whose horizontal interval is $[a\ldots b)$ and whose vertical interval is $[c\ldots d)$. A motley dissection has the property that no two distinct rectangles have the same pair of horizontal cutting lines and no two distinct rectangles have the same pair of vertical cutting lines.

The key point is that the symmetry conditions act on whole rectangles. Therefore a symmetric solution must be built from complete orbits of rectangles under the relevant symmetry group.

(a) $90^\circ$-rotational symmetry

Define

$$ \rho([a\ldots b)\times[c\ldots d))

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

This is rotation by $90^\circ$ about the center of the square. Since

$$ \rho^4=1, $$

every rectangle has an orbit

$$ \mathcal O_\rho(R)= {R,\rho(R),\rho^2(R),\rho^3(R)}, $$

where repeated members are removed when a rectangle is fixed by some power of $\rho$.

To generate all rotationally symmetric $n\times n$ motley dissections, proceed as follows.

Generate every possible rectangle in the $n\times n$ square.
Replace every rectangle by its complete orbit under $\rho$.
For each orbit, check the motley conditions internally. If two members of the orbit have the same pair of horizontal cutting lines or the same pair of vertical cutting lines, discard the orbit.
Use the surviving orbits as the objects in an exact-cover search.

The exact-cover rows are now symmetry orbits rather than individual rectangles. A chosen row covers all cells covered by all rectangles in the orbit. The usual cell-cover constraints guarantee that the selected orbits form a dissection. Additional columns or equivalent bookkeeping constraints enforce the motley requirement that no horizontal or vertical interval pair is reused.

This construction is complete. If a dissection has $90^\circ$-rotational symmetry and contains $R$, then it must also contain

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

so it is a union of the generated orbits.

It is also sound. Every selected object is already invariant under $\rho$, so the union of selected objects is invariant under $\rho$. The exact-cover constraints ensure that the result is a valid motley dissection.

(b) Reflection symmetry about both diagonals

Let

$$ \sigma([a\ldots b)\times[c\ldots d))

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

be reflection in the main diagonal, and let

$$ \tau([a\ldots b)\times[c\ldots d))

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

be reflection in the other diagonal.

The four required images of a rectangle are therefore

$$ R, $$

$$ \sigma(R)

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

$$ \tau(R)

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

and

$$ \sigma\tau(R)

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

The two reflections generate the Klein four-group

$$ G={1,\sigma,\tau,\sigma\tau}. $$

Hence every rectangle must occur together with its orbit

$$ \mathcal O_G(R)

{R,\sigma(R),\tau(R),\sigma\tau(R)}, $$

again with repetitions deleted if some rectangles coincide.

The generation procedure is therefore:

Generate all rectangle orbits under $G$.
Reject an orbit if its members violate the motley condition.
Treat every remaining orbit as one exact-cover object.
Search for a collection of compatible orbits covering the whole square.

The proof of correctness is the same as in part (a).

If a dissection has the two diagonal symmetries, then applying either reflection to any rectangle in the dissection gives another rectangle in the dissection. Therefore the dissection is a union of complete $G$-orbits.

Conversely, every union of complete $G$-orbits is invariant under both reflections, because $G$ is closed under both generators. The exact-cover constraints ensure that the result is a dissection, and the motley restrictions ensure that it is a motley dissection.

(c) The smallest $n$

We must rule out $n=1$ and $n=2$, and then exhibit a solution for $n=3$.

$n=1$

The only rectangle is the whole square. There is no nontrivial dissection, so no type-(b) solution exists.

$n=2$

The possible cutting lines are

$$ 0,1,2. $$

A proper rectangle has one of the following horizontal intervals:

$$ [0\ldots1),\qquad [1\ldots2),\qquad [0\ldots2), $$

and similarly for vertical intervals.

A rectangle using the full horizontal interval and a proper vertical interval is a vertical strip. Under reflection in the other diagonal it becomes a horizontal strip. Thus such rectangles occur in pairs. But the two strips then have the same pair of cutting lines in the other direction, violating the motley condition.

Similarly, a rectangle using a proper horizontal interval and the full vertical interval cannot occur in a valid symmetric motley dissection.

The remaining proper rectangles are the four unit squares. The diagonal-reflection orbit of a corner unit square consists of two opposite corner squares. Choosing all such orbits gives the four-cell partition

$$ [0\ldots1)\times[0\ldots1), $$

$$ [0\ldots1)\times[1\ldots2), $$

$$ [1\ldots2)\times[0\ldots1), $$

$$ [1\ldots2)\times[1\ldots2). $$

However, the two cells in each orbit have the same horizontal interval and the same vertical interval, so the motley condition fails. Therefore no nontrivial type-(b) symmetric motley dissection exists for $n=2$.

$n=3$

A symmetric solution exists. Consider the following five rectangles:

$$ [0\ldots1)\times[0\ldots3), $$

$$ [0\ldots3)\times[0\ldots1), $$

$$ [0\ldots3)\times[2\ldots3), $$

$$ [2\ldots3)\times[0\ldots3), $$

and

$$ [1\ldots2)\times[1\ldots2). $$

These five rectangles partition the $3\times3$ square.

The first four form one orbit under the two diagonal reflections:

$$ [0\ldots1)\times[0\ldots3) $$

is mapped to

$$ [0\ldots3)\times[0\ldots1), $$

then to

$$ [2\ldots3)\times[0\ldots3), $$

and then to

$$ [0\ldots3)\times[2\ldots3). $$

The central rectangle is fixed by both reflections.

The horizontal interval pairs of the five rectangles are

$$ [0\ldots1),\ [0\ldots3),\ [0\ldots3),\ [2\ldots3),\ [1\ldots2), $$

but the two rectangles with horizontal interval $[0\ldots3)$ have different vertical intervals. Equivalently, listing the pairs of horizontal cutting lines gives

$$ (0,1),(0,3),(2,3),(0,3),(1,2), $$

with the repeated pair $(0,3)$ occurring only with different vertical pairs. The corresponding vertical pairs are

$$ (0,3),(0,1),(0,3),(2,3),(1,2). $$

Thus no two distinct rectangles have both the same horizontal and vertical cutting-line pairs. Hence the dissection is motley.

Therefore a type-(b) symmetric motley dissection exists for

$$ n=3. $$

Since $n=1$ and $n=2$ are impossible, the smallest value is

$$ \boxed{n=3}. $$

TAOCP 7.2.2.1 Exercise 371