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: 2m07s

Solution

The exercise as reproduced here still lacks the information needed to carry out the construction. The statement refers to “the following diagram” and to “Fig. 36's four directions,” but the actual arrangement of gray pixels and the four tomographic directions are not present in the supplied text. Therefore the variables to be assigned, the allowed period-6 cell arrangement, and the projection constraints cannot be determined.

The earlier response was correct to notice that the diagram was unavailable, but it incorrectly described the exercise itself as incomplete. The exercise in the book is well-defined because the figure supplies the missing data. The issue is only that the copy of the exercise given here omits an essential part of the problem statement.

A complete solution must begin by labeling the gray cells in the diagram, assigning each one a value in ${0,1}$, and then checking the four families of parallel lines. For each direction, every line in the infinite periodic extension must have the same finite tomographic sum. Without the diagram, neither the linear constraints nor the resulting black-and-white pattern can be reconstructed.

Consequently, no rigorous construction or verification of the required period-6 pattern can be given from the information currently available. The figure containing the gray-pixel diagram, together with the referenced directions from Fig. 36 if they are not already visible in the exercise context, is required before a mathematical solution can be written.