TAOCP 7.2.2.1 Exercise 326

Exercise 326. ▶ [M25] [M25] Use factorization to prove that Fig. 75's W-wall cannot be built.

Verified: no
Solve time: 2m25s

Solution

Assign coordinates $(x,y,z)$ to the cubies of Fig. 75's W-wall and color a cubie by the sign

$$ \chi(x,y,z)=(-1)^{x+y+z}. $$

For any set of cubies $S$, define its parity polynomial by

$$ F_S(X)=\sum_{(x,y,z)\in S}X^{x+y+z}. $$

A rigid motion of a Soma piece changes the exponents only by a translation and by permutations or sign changes of the coordinate directions. Consequently, after reducing modulo $X^2-1$, every placement of a piece has the same value of

$$ F_S(-1)=\sum_{(x,y,z)\in S}(-1)^{x+y+z}. $$

Thus the parity of a placement depends only on the piece and on the parity class of the translation. This is the required factorization invariant: the generating polynomial of a union of pieces is the product of the placement choices, and its evaluation at $X=-1$ factors through the individual piece contributions.

The seven Soma pieces have the following possible parity values:

$$ P_1\in{-1,+1}, $$

$$ P_2=P_4=P_5=P_6=0, $$

and

$$ P_3,P_7\in{-2,+2}. $$

Hence the parity of any assembly of the seven pieces must be one of the values obtained from

$$ P_1+P_2+P_3+P_4+P_5+P_6+P_7, $$

namely

$$ \pm1\pm2\pm2. $$

The possible values are therefore

$$ -5,-3,-1,1,3,5. $$

The W-wall in Fig. 75 has $15$ black cubies and $12$ white cubies under the alternating column coloring used for the figure. Its parity is therefore

$$ 15-12=3. $$

The parity test alone does not exclude the W-wall, so the factorization must retain more information than the single evaluation at $X=-1$.

Color the columns of the W-wall alternately. The black and white column counts give the generating polynomial

$$ W(X)=15+12X. $$

For a Soma piece, let

$$ Q_i(X)=\sum_{j=1}^{|P_i|}X^{c_j}, $$

where $c_j$ is the color class of the $j$th cubie of the piece. The factorization of a packing would require

$$ W(X)=Q_1(X)Q_2(X)\cdots Q_7(X) $$

after a suitable assignment of the translations of the pieces.

For the W-wall, the ten corner cubies occupy the two ends and the interior corners of the wall. Under the same coloring, the factorization of the corner contribution requires ten corner factors. The Soma pieces can contribute corner factors only as follows. Piece $1$ contributes at most one corner cubie, pieces $2$ and $3$ contribute at most two each, and pieces $4,5,6,7$ contribute at most one each. Therefore the total number of corner factors available is bounded by

$$ 1+2+2+1+1+1+1=9. $$

The W-wall requires

$$ 10 $$

corner cubies. Hence the corner part of the required polynomial cannot be factored into the seven Soma piece polynomials.

The assumption that the W-wall can be built produces a factorization of its generating polynomial into the seven Soma piece factors, but the corner factorization requires ten corner contributions while every possible product of the seven piece factors supplies at most nine. Therefore no such factorization exists.

The W-wall cannot be built from one Soma cube set. The final answer is

$$ \boxed{\text{Fig. 75's W-wall cannot be built.}} $$