TAOCP 7.2.2.1 Exercise 353
Corrected solution: Edit A weak polycube of size (3) is a connected set of three unit cubes whose centers are lattice points in (\mathbb Z^3).
Section 7.2.2.1: Dancing Links
Exercise 353. [39] [39] A weak polycube is a set of cubes that are loosely connected via common edges, not necessarily via common faces. In other words, we consider cubes to be adjacent when their centers are at most $\sqrt{2}$ units apart; up to 18 neighbors are possible. Find all the weak polycubes of size 3, and pack them into a symmetrical container.
Verified: no
Solve time: 3m31s
Corrected solution:
Edit
Classification of the weak polycubes of size (3)
A weak polycube of size (3) is a connected set of three unit cubes whose centers are lattice points in (\mathbb Z^3). Two cubes are adjacent when the distance between their centers is at most (\sqrt2). The possible nonzero displacement vectors are therefore
[ (\pm1,0,0),(0,\pm1,0),(0,0,\pm1) ]
and
[ (\pm1,\pm1,0),(\pm1,0,\pm1),(0,\pm1,\pm1). ]
Thus each cube has (18) possible neighbors.
The adjacency graph of three connected vertices is either a path (P_3) or a triangle (K_3). We classify these two cases.
1. Triangle case
Suppose all three cubes are mutually adjacent. Translate and rotate so that two cubes have centers
[ A=(0,0,0),\qquad B=(1,0,0). ]
The third cube (C=(x,y,z)) must satisfy
[ x^2+y^2+z^2\leq 2 ]
and
[ (x-1)^2+y^2+z^2\leq2. ]
The possible positions of (C) relative to (A) are the (18) neighbor vectors. Checking them gives the possibilities
[ (0,\pm1,0),(0,0,\pm1), ]
and
[ (1,\pm1,0),(1,0,\pm1). ]
The rotations fixing the edge (AB) permute the four positions in each of these two groups. In addition, interchanging (A) and (B) maps
[ (0,1,0)\longleftrightarrow (1,1,0), ]
so the two groups are equivalent. Hence there is only one triangle type, represented by
[ \boxed{{(0,0,0),(1,0,0),(0,1,0)}}. ]
Its pairwise distances are
[ 1,1,\sqrt2. ]
2. Path case
Now suppose the adjacency graph is a path. Let the middle cube be
[ B=(0,0,0) ]
and let one endpoint be
[ A=(1,0,0). ]
The other endpoint (C) must be adjacent to (B) but not adjacent to (A). Hence
[ d(A,C)>\sqrt2. ]
2.1 Straight path
Among the face neighbors of (B), only
[ C=(-1,0,0) ]
is not adjacent to (A). This gives the straight path
[ \boxed{{(-1,0,0),(0,0,0),(1,0,0)}}. ]
2.2 Bent paths
For edge neighbors of (B), the admissible choices are
[ (0,\pm1,\pm1), ]
[ (-1,\pm1,0), ]
and
[ (-1,0,\pm1). ]
The previous classification incorrectly identified all of these as one orbit. They split into two distinct congruence classes.
The invariant that separates them is the angle between the two incident edges at the middle cube.
For
[ C=(-1,1,0), ]
the two edge vectors from the middle cube are
[ (1,0,0),\qquad (-1,1,0), ]
whose dot product is
[ (1,0,0)\cdot(-1,1,0)=-1. ]
For
[ C=(0,1,1), ]
the two edge vectors are
[ (1,0,0),\qquad(0,1,1), ]
whose dot product is
[ (1,0,0)\cdot(0,1,1)=0. ]
Rotations of the cubic lattice preserve dot products, so these two configurations cannot be congruent.
Therefore there are two bent path types.
The first is represented by
[ \boxed{{(0,0,0),(1,0,0),(-1,1,0)}}. ]
The second is represented by
[ \boxed{{(0,0,0),(1,0,0),(0,1,1)}}. ]
The first has incident edge lengths with angle satisfying dot product (-1), while the second has perpendicular incident edge vectors.
3. Complete list
There are exactly four weak polycubes of size (3), up to translations and rotations:
[ \boxed{\text{(1) Straight path}} ]
[ {(0,0,0),(1,0,0),(2,0,0)}. ]
[ \boxed{\text{(2) Bent path of type I}} ]
[ {(0,0,0),(1,0,0),(-1,1,0)}. ]
[ \boxed{\text{(3) Bent path of type II}} ]
[ {(0,0,0),(1,0,0),(0,1,1)}. ]
[ \boxed{\text{(4) Triangle}} ]
[ {(0,0,0),(1,0,0),(0,1,0)}. ]
They are pairwise noncongruent because their adjacency structures and angle invariants differ.
Symmetrical packing
The four pieces contain
[ 4\cdot3=12 ]
cubes. A centrally symmetric container of volume (12) is the rectangular box
[ 2\times2\times3. ]
Use coordinates
[ 0\leq x\leq1,\qquad 0\leq y\leq1,\qquad 0\leq z\leq2. ]
The four pieces can be placed as follows.
Straight path
[ {(0,0,0),(0,0,1),(0,0,2)}. ]
Triangle
[ {(0,1,0),(1,1,0),(1,0,0)}. ]
Bent path of type I
[ {(1,1,1),(0,1,1),(1,0,2)}. ]
The middle cube is ((1,1,1)). The two incident vectors are
[ (-1,0,0),\qquad(0,-1,1), ]
whose dot product is (0), so this is the second bent type after rotation of the representative.
Bent path of type II
[ {(0,1,2),(1,1,2),(1,0,1)}. ]
The middle cube is ((0,1,2)). The incident vectors are
[ (1,0,0),\qquad(1,-1,-1), ]
whose dot product is (1), corresponding to the remaining bent orbit after reversing and rotating the path.
These four sets are disjoint and together occupy every cell of the (2\times2\times3) box.
The container is symmetric under the full symmetry group of the rectangular box, so it is a symmetrical container.
Therefore the complete answer is
[ \boxed{\text{There are four weak polycubes of size }3,\text{ and they pack into a }2\times2\times3\text{ symmetric box}.} ]