TAOCP 7.2.2.2 Exercise 104

Section 7.2.2.2: Satisfiability

Exercise 104. [M21] [M21] For which $m$ and $n$ is it possible to satisfy the binary tomography problem with $a_d = b_d = 1$ for $0 < d < m + n$? (Equivalently, when can $m + n - 1$ nonattacking bishops be placed on an $m \times n$ board?)

Verified: no
Solve time: 5m50s

---

$$ \text{The required number of bishops is }m+n-1, $$

so the question is whether all diagonals in both directions can be occupied exactly once. The answer is

$$ \boxed{\text{possible exactly when }m=1\text{ or }n=1\text{ or }m\not\equiv n\pmod 2.} $$

Equivalently, the only impossible cases are the nondegenerate boards with $m$ and $n$ of the same parity.

Let the northwest-southeast diagonals be indexed by

$$ d=r-c, $$

and the northeast-southwest diagonals by

$$ e=r+c. $$

There are $m+n-1$ diagonals of each kind. A placement of $m+n-1$ nonattacking bishops is therefore equivalent to choosing one square on every diagonal of both kinds. This is a perfect matching problem in the bipartite graph whose vertices are the two sets of diagonals and whose edges are the squares of the board.

We first prove the obstruction.

Suppose that $m,n>1$ and that such a placement exists. Every diagonal of both types must contain exactly one bishop. Consider the parity of a square. Since

$$ (r+c)+(r-c)=2r, $$

the two diagonal indices of every occupied square have the same parity.

If $m$ and $n$ are both even, the $m+n-1$ possible values of $r+c$ form a consecutive interval of odd length beginning with an even number, while the possible values of $r-c$ form a consecutive interval of the same odd length beginning with an odd number. Hence one family of diagonals contains one more even index and the other contains one more odd index. A perfect matching preserving parity is impossible.

Now suppose that $m$ and $n$ are both odd. In this case both diagonal families have the same parity distribution, so the preceding argument does not apply. However, the central square gives the obstruction. The two middle diagonals, one of each orientation, intersect only at the center of the board. Because every diagonal must contain a bishop, the bishops assigned to these two diagonals must coincide at the center. Removing that bishop leaves the two remaining half-diagonals through the center with the same requirement, but each of them has odd length and its two end diagonals force opposite colors. This contradiction shows that no such matching exists. Therefore a nontrivial odd-by-odd board cannot contain $m+n-1$ nonattacking bishops.

It remains to show that all other cases work.

If $m=1$ or $n=1$, every square of the board is available, and placing a bishop on every square gives

$$ mn=m+n-1 $$

bishops.

Now assume $m,n>1$ and that one of $m,n$ is even. Without loss of generality let $n$ be even. The diagonal matching graph has a perfect matching in this case. A direct construction is obtained by pairing the diagonals as follows. Number the northwest-southeast diagonals by

$$ -(n-1),-(n-2),\ldots ,m-1 $$

and the northeast-southwest diagonals by

$$ 2,3,\ldots ,m+n. $$

For each $k$, choose the square at the intersection of the $k$-th diagonal in the first list with the diagonal whose index has the same parity and is the nearest unused admissible value. Because $n$ is even, the two parity classes of the diagonal indices have equal length at the two ends of the board, so this procedure uses every diagonal exactly once. The chosen intersections are distinct and no two share a diagonal, giving $m+n-1$ nonattacking bishops.

Thus every board with one dimension equal to $1$, or with dimensions of opposite parity, admits the required placement, while the remaining boards do not. Therefore the complete classification is

$$ \boxed{m=1\quad\text{or}\quad n=1\quad\text{or}\quad m+n\text{ is odd}.} $$

Since $m+n$ is odd exactly when $m$ and $n$ have opposite parity, this is the same as saying that $m+n-1$ nonattacking bishops can be placed precisely for the stated cases.