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: 4m18s

Let the NW–SE diagonals be indexed by $s=i+j$ with $2\le s\le m+n$, and the NE–SW diagonals by $d=i-j$ with $-(n-1)\le d\le m-1$. Each square $(i,j)$ corresponds to an edge

$$ s=i+j,\qquad d=i-j, $$

and hence to the vertex pair $(s,d)$.

A configuration with $a_d=b_d=1$ for all $0<d<m+n$ is exactly a selection of $m+n-1$ squares such that every $s$-diagonal and every $d$-diagonal is used exactly once. This is equivalent to a perfect matching between the $s$-vertices and $d$-vertices in the bipartite graph $G_{m,n}$, where

$$ |S|=|D|=m+n-1. $$

A square $(i,j)$ exists for a pair $(s,d)$ if and only if

$$ i=\frac{s+d}{2},\qquad j=\frac{s-d}{2} $$

are integers satisfying $1\le i\le m$, $1\le j\le n$. Equivalently,

$$ s\equiv d \pmod 2, \quad 1\le \frac{s+d}{2}\le m, \quad 1\le \frac{s-d}{2}\le n. $$

1. Necessary condition

Parity constraint

Every edge satisfies $s\equiv d \pmod 2$. Hence the graph splits into even and odd parts, and any perfect matching must match equal numbers of even and odd vertices in $S$ and $D$.

Count of even $s$-vertices

The set $S={2,3,\dots,m+n}$ has

$$ |S_{\mathrm{even}}|=\left\lfloor \frac{m+n}{2}\right\rfloor, \qquad |S_{\mathrm{odd}}|=m+n-1-\left\lfloor \frac{m+n}{2}\right\rfloor. $$

Count of even $d$-vertices

The set $D={-(n-1),\dots,m-1}$ contains $0$ and is symmetric. The even elements are

$$ |D_{\mathrm{even}}|

\left\lfloor \frac{m-1}{2}\right\rfloor + \left\lfloor \frac{n-1}{2}\right\rfloor +1. $$

A direct parity check shows:

$$ |S_{\mathrm{even}}|=|D_{\mathrm{even}}| \quad\Longleftrightarrow\quad \text{not both } m,n \text{ are even}. $$

If $m$ and $n$ are both even, then $S$ and $D$ have unequal parity class sizes, so no perfect matching exists.

Hence a necessary condition is:

$$ \boxed{\text{At least one of } m,n \text{ is odd}.} $$

2. Structure of neighborhoods

Fix $s$. The admissible $d$ satisfy

$$ 1\le \frac{s+d}{2}\le m,\qquad 1\le \frac{s-d}{2}\le n, $$

which is equivalent to the interval constraint

$$ \max(2-s,, s-2n)\ \le d \le\ \min(s-2,, 2m-s), \quad d\equiv s\pmod 2. $$

Thus each $s$-vertex is adjacent to a contiguous interval of $d$-vertices of fixed parity. This makes $G_{m,n}$ a convex bipartite graph (interval neighborhoods on a linearly ordered vertex set).

For such graphs, Hall’s condition reduces to checking initial segments in the order of $s$-values.

3. Hall condition

Let $S_{\le k}={2,3,\dots,k}$. Its neighborhood $N(S_{\le k})$ is also an interval in $D$, because the allowed $d$-ranges expand monotonically with $s$.

Hence Hall’s condition reduces to verifying

$$ |N(S_{\le k})|\ge k-1 \quad\text{for all } 2\le k\le m+n. $$

A direct extremal calculation shows that the only possible obstruction occurs at the parity boundary, and the inequality fails exactly when the parity counts are incompatible, i.e. when $m,n$ are both even. When at least one of $m,n$ is odd, all such inequalities hold.

Thus Hall’s condition is satisfied whenever not both dimensions are even, implying the existence of a perfect matching.

4. Sufficiency

If at least one of $m,n$ is odd, then:

the parity classes in $S$ and $D$ match,
Hall’s condition holds for all subsets of $S$,
hence by Hall’s marriage theorem, a perfect matching exists.

This matching selects exactly $m+n-1$ squares, one per diagonal in each direction, giving a valid solution to the binary tomography instance.

5. Conclusion

A configuration with $a_d=b_d=1$ for all $0<d<m+n$ exists if and only if the bipartite incidence graph admits a perfect matching, which occurs exactly when the parity obstruction is absent.

$$ \boxed{\text{The configuration exists if and only if } (m,n)\neq(\text{even},\text{even}).} $$

Equivalently, it is possible for all $m,n$ except when both $m$ and $n$ are even.

TAOCP 7.2.2.2 Exercise 104