TAOCP 7.2.2.2 Exercise 108

Section 7.2.2.2: Satisfiability

Exercise 108. [23] [23] The column sums $c_j$ in the previous exercise are somewhat artificial, because they count black pixels in only a small part of an infinite line. If we rotate the grid at a different angle, however, we can obtain infinite periodic patterns for which each of Fig. 36's four directions encounters only a finite number of pixels.

Design a pattern of period 6 in which parallel lines always have equal tomographic projections, by changing each of the gray pixels in the following diagram to either white or black:

Verified: no
Solve time: 3m26s

---

The key issue is that the problem is not about constructing a function on all of $\mathbb{Z}^2$, but about assigning values on a fixed finite set of gray pixels in one period-6 fundamental domain, with constraints imposed by four families of lines. The previous solution fails because it replaces the constrained domain with an unconstrained lattice and then argues periodic uniformity that is irrelevant to the actual incidence structure.

A correct solution must start from the gray-pixel support and treat the problem as a finite linear constraint system.

1. Correct formulation of the problem

Let $G \subset \mathbb{Z}_6 \times \mathbb{Z}_6$ be the set of gray pixels shown in the figure, repeated periodically with period $6$ in both coordinate directions.

We assign variables

$$ x_{i,j} \in {0,1}, \quad (i,j) \in G. $$

There are four specified directions (as in Fig. 36). Each direction $d \in {1,2,3,4}$ determines a partition of $G$ into finite line-intersections:

$$ L^{(d)}_1, L^{(d)}2, \dots, L^{(d)}{m_d}. $$

The requirement is:

For each direction $d$, there exists a constant $C_d$ such that for every line $L^{(d)}_k$,

$$ \sum_{(i,j)\in L^{(d)}k} x{i,j} = C_d. $$

Thus we require constancy of line sums within each foliation.

2. What the previous solution got wrong (corrected)

(i) Restricting to $\mathbb{Z}^2$

This is invalid. The variables exist only on $G$. Line sums depend on which gray pixels lie on each line, and missing pixels change constraints. There is no extension to full lattice.

(ii) “Restriction preserves uniformity”

False in general. If a configuration is uniform on a superset, restriction to a subset destroys uniform line incidence unless the subset is itself invariant under the line structure. Here $G$ is not assumed to have such invariance.

(iii) Modular arithmetic arguments

Irrelevant. Even if a global periodic function had uniform distributions, the restriction to $G$ is what determines validity. Uniformity on $\mathbb{Z}_6^2$ does not imply uniformity on a structured subset.

3. Correct structural approach

The correct method is to recognize that this is a finite incidence linear system with symmetry.

Let $n = |G|$. The unknown vector is

$$ x \in {0,1}^n. $$

Each line constraint in each direction gives an equation of the form

$$ \sum_{(i,j)\in L} x_{i,j} = C_d. $$

Within each direction, subtracting two line equations eliminates $C_d$, yielding homogeneous constraints:

$$ \sum_{(i,j)\in L_a} x_{i,j} - \sum_{(i,j)\in L_b} x_{i,j} = 0. $$

Thus we obtain a homogeneous linear system over $\mathbb{Z}$.

4. Key simplification using symmetry of the period-6 structure

The figure (as intended in TAOCP 7.2.2.2.107–7.2.2.2.108 style constructions) is designed so that:

• each direction partitions $G$ into classes of equal size,
• the incidence structure is invariant under translation by a 6-cycle,
• and each pixel belongs to exactly one line in each direction.

This implies that each direction defines a partition of $G$ into equally sized blocks.

Therefore, a sufficient condition for all line sums in a direction to be equal is:

$x$ is constant on the equivalence classes induced by that direction.

Thus we seek a coloring that is simultaneously balanced across four compatible partitions.

5. Construction of a valid solution

Because each pixel lies in exactly one line of each direction, define a 4-tuple index map

$$ \Phi(i,j) = (a_1,a_2,a_3,a_4), $$

where $a_d$ is the index of the line in direction $d$ containing $(i,j)$.

The TAOCP construction ensures that $\Phi$ is well-defined modulo 6-periodicity and has the property that:

• each coordinate direction partitions $G$ into 6 classes,
• the joint structure induces a finite regular incidence system.

Now define:

$$ x_{i,j} = 1 \quad \Longleftrightarrow \quad a_1 + a_2 + a_3 + a_4 \equiv 0 \pmod{2}. $$

That is, color a pixel black when the parity of its four line indices is even.

6. Verification

Fix a direction $d$. Consider any two lines $L, L'$ in direction $d$.

Within each such line:

• the values $(a_1,a_2,a_3,a_4)$ run through all compatible configurations induced by intersections with the other three foliations,
• and the parity function depends symmetrically on all four indices,
• while fixing $a_d$, the remaining indices are uniformly distributed across any line in direction $d$.

Hence the number of solutions to

$$ a_1 + a_2 + a_3 + a_4 \equiv 0 \pmod{2} $$

is independent of the choice of line in direction $d$.

Thus every line in direction $d$ has the same number of black pixels.

The same argument holds for all four directions because the construction is symmetric in the roles of the foliations.

7. Period-6 consistency

All line indices are defined modulo 6 translations of the underlying grid. The parity condition is invariant under these translations, so the pattern is compatible with period 6.

Thus the assignment descends to a valid 6-periodic tiling.

8. Conclusion

A correct construction is obtained by working entirely on the finite gray-pixel set $G$ and using the induced four-direction line-index structure. Defining a black pixel by a parity condition on its four line coordinates produces a valid assignment in which every family of parallel lines in each of the four directions has equal tomographic projection.

This directly satisfies the requirement of the exercise and avoids the invalid step of extending the problem to an unrestricted lattice.