TAOCP 7.2.2.2 Exercise 103

The previous solution fails because it attempts to proceed as if a complete discrete tomography instance were given, then introduces unsubstantiated repairs to the data.

taocpmathematicsalgorithmsvolume-4medium

Section 7.2.2.2: Satisfiability

Exercise 103. [18] [18] (Do this exercise by hand, it's fun!) Find the $7 \times 21$ image whose tomographic sums are $(r_1, \ldots, r_7) = (1, 0, 13, 6, 12, 7, 19)$; $(c_1, \ldots, c_{21}) = (4, 3, 3, 4, 1, 6, 1, 3, 3, 5, 1, 5, 1, 5, 1, 5, 1, 1, 1)$; $(a_1, \ldots, a_{27}) = (0, 0, 1, 2, 3, 2, 3, 2, 3, 3, 5, 4, 3, 2, 3, 3, 3, 4, 3, 2, 2, 1)$; $(b_1, \ldots, b_{27}) = (0, 0, 0, 1, 3, 3, 4, 3, 2, 2, 3, 3, 3, 4, 3, 2, 1, 1)$.

Verified: no
Solve time: 3m39s

The previous solution fails because it attempts to proceed as if a complete discrete tomography instance were given, then introduces unsubstantiated repairs to the data. The correct response is to restart from the specification and verify what information is actually available before attempting any reconstruction.

1. What the problem actually provides

We are asked to reconstruct a $7 \times 21$ binary image $x_{ij} \in {0,1}$ from tomographic sums:

  • Row sums:

$$ (r_1,\dots,r_7) = (1,0,13,6,12,7,19), $$

which are complete and satisfy

$$ \sum_{i=1}^7 r_i = 58. $$

  • Column sums:

$$ (4,3,3,4,1,6,1,3,3,5,1,5,1,5,1,5,1,1,1), $$

which contains only $19$ entries, not $21$.

  • Diagonal sums $a_k$ for $k=1,\dots,27$, but only the first 22 entries are given.
  • Diagonal sums $b_k$ for $k=1,\dots,27$, but only the first 18 entries are given.

2. First correction: no assumption about missing data is allowed

A critical error in the previous solution is the introduction of “missing column sums” and attempts to infer them. This is invalid.

In discrete tomography, one may only use constraints explicitly given or provably implied by consistency conditions involving the full system. Here:

  • The column vector is explicitly stated with 19 entries.
  • There is no justification that entries are missing rather than the exercise being partially transcribed.
  • The diagonal sequences are also clearly truncated.

Therefore, the correct mathematical stance is:

The instance is not fully specified as written.

We do not modify or complete the data.

3. Second correction: row sums do not determine or validate column completeness

The previous solution incorrectly attempted to use row sums to infer missing column data. This is not valid.

Row sums only enforce:

$$ \sum_i r_i = \sum_j c_j, $$

but here $\sum_j c_j$ is not even defined, since the column vector is incomplete.

Thus:

  • No contradiction arises from partial column data.
  • No completion can be inferred.
  • No constraint forces the number of column entries to be 21 beyond the problem statement itself.

So there is no logical basis for augmentation.

4. Third correction: diagonal data is also incomplete

The diagonal sums $a_k$ and $b_k$ are essential in TAOCP-style tomography because they couple variables globally. However:

  • A full $7 \times 21$ instance requires 27 diagonal sums in each direction.
  • Only partial sequences are provided for both $a_k$ and $b_k$.

Thus the system of equations is structurally incomplete. In particular:

  • Many variables $x_{ij}$ appear in unspecified or missing diagonal constraints.
  • The constraint system cannot be formed as a complete linear system.

5. Consequence: the reconstruction problem is underdetermined and ill-posed as stated

Let $x_{ij} \in {0,1}$ for $1 \le i \le 7$, $1 \le j \le 21$. A full tomographic reconstruction requires:

  • 7 row constraints,
  • 21 column constraints,
  • 27 NW–SE diagonal constraints,
  • 27 NE–SW diagonal constraints.

This yields a tightly constrained discrete system.

However, in the present statement:

  • Column constraints are incomplete,
  • Both diagonal constraint families are incomplete.

Therefore the constraint graph does not cover all variables.

A key structural fact is:

Without full diagonal coverage, the system decomposes into multiple independent degrees of freedom.

Hence uniqueness cannot be established, and reconstruction is not defined.

6. Why the previous “reconstruction” attempt is invalid

The earlier solution failed in three fundamental ways:

  1. Inventing missing data

It introduced unknown column entries and even assigned them values. This has no logical basis in the problem statement. 2. Asserting uniqueness without a complete constraint system

Uniqueness in discrete tomography depends critically on the full set of row, column, and diagonal projections. Here, the constraint system is incomplete, so uniqueness cannot even be formulated. 3. Failing to construct any candidate image

No partial or consistent $7 \times 21$ matrix was produced, nor can one be justified from incomplete diagonal data.

7. Correct mathematical conclusion

From the given information alone:

  • The row sums are valid and complete.
  • The column sums are truncated and do not define a full constraint vector.
  • Both diagonal sum sequences are truncated.

Therefore the tomographic specification does not define a complete discrete tomography instance.

The correct conclusion is:

$$ \text{The image is not uniquely determined because the tomographic data is incomplete.} $$

Stronger:

$$ \text{The reconstruction problem is underdetermined and cannot be solved from the given data.} $$

Final answer

No $7 \times 21$ binary image can be reconstructed uniquely, or even consistently specified up to equivalence, because the column-sum vector and both diagonal-sum vectors are incomplete. Any attempt to complete or reconstruct the image requires additional data not provided in the problem statement.

∎