16. Divide an $m$-by- $n$ rectangle into $m n$ nonoverlapping 1-by-1 squares. A polyomino of this rectangle is a subset of these unit squares such that for any two unit squares $S, T$ in the polyomino, either
(1) $S$ and $T$ share an edge or
(2) there exists a positive integer $n$ such that the polyomino contains unit squares $S_{1}, S_{2}, S_{3}, \ldots, S_{n}$ such that $S$ and $S_{1}$ share an edge, $S_{n}$ and $T$ share an edge, and for all positive integers $k<n, S_{k}$ and $S_{k+1}$ share an edge.

We say a polyomino of a given rectangle spans the rectangle if for each of the four edges of the rectangle the polyomino contains a square whose edge lies on it.

What is the minimum number of unit squares a polyomino can have if it spans a 128-by343 rectangle?
Solution: To span an $a \times b$ rectangle, we need at least $a+b-1$ squares. Indeed, consider a square of the polyomino bordering the left edge of the rectangle and one bordering the right edge. There exists a path connecting these squares; suppose it runs through $c$ different rows. Then the path requires at least $b-1$ horizontal and $c-1$ vertical steps, so it uses at least $b+c-1$ different squares. However, since the polyomino also hits the top and bottom edges of the rectangle, it must run into the remaining $a-c$ rows as well, so altogether we need at least $a+b-1$ squares. On the other hand, this many squares suffice - just consider all the squares bordering the lower or right edges of the rectangle. So, in our case, the answer is $128+343-1=470$.