
Problem 5. Fix an integer $n \geq 2$. An $n \times n$ sieve is an $n \times n$ array with $n$ cells removed so that exactly one cell is removed from every row and every column. A stick is a $1 \times k$ or $k \times 1$ array for any positive integer $k$. For any sieve $A$, let $m(A)$ be the minimal number of sticks required to partition $A$. Find all possible values of $m(A)$, as $A$ varies over all possible $n \times n$ sieves.

## Palmer MEBANE and NiKOlai BeLUHOV


Solution 1. Given $A, m(A)=2 n-2$, and it is achieved, for instance, by dissecting $A$ along all horizontal (or vertical) grid lines. It remains to prove that $m(A) \geq 2 n-2$ for every $A$.

By holes we mean the cells which are cut out from the board. The cross of a hole in $A$ is the union of the row and the column through that hole.

Arguing indirectly, consider a dissection of $A$ into $2 n-3$ or fewer sticks. Horizontal sticks are all labelled $h$, and vertical sticks are labelled $v ; 1 \times 1$ sticks are both horizontal and vertical, and labelled arbitrarily. Each cell of $A$ inherits the label of the unique containing stick.

Assign each stick in the dissection to the cross of the unique hole on its row, if the stick is horizontal; on its column, if the stick is vertical.

Since there are at most $2 n-3$ sticks and exactly $n$ crosses, there are two crosses each of which is assigned to at most one stick in the dissection. Let the crosses be $c$ and $d$, centred at $a=\left(x_{a}, y_{a}\right)$ and $b=\left(x_{b}, y_{b}\right)$, respectively, and assume, without loss of generality, $x_{a}<x_{b}$ and $y_{a}<y_{b}$. The sticks covering the cells $\left(x_{a}, y_{b}\right)$ and $\left(x_{b}, y_{a}\right)$ have like labels, for otherwise one of the two crosses would be assigned to at least two sticks. Say the common label is $v$, so each of $c$ and $d$ contains a stick covering one of those two cells. It follows that the lower (respectively, upper) arm of $c$ (respectively, $d$ ) is all- $h$, and the horizontal arms of both crosses are all- $v$, as illustrated below.

![](https://cdn.mathpix.com/cropped/2024_06_04_f8e625b68f0af3ff5fa8g-09.jpg?height=651&width=648&top_left_y=1302&top_left_x=681)

Each of the rows between the rows of $a$ and $b$, that is, rows $y_{a}+1, y_{a}+2, \ldots, y_{b}-1$, contains a hole. The column of each such hole contains at least two $v$-sticks. All other columns contain at least one $v$-stick each. In addition, all rows below $a$ and all rows above $b$ contain at least one $h$-stick each. This amounts to a total of at least $2\left(y_{b}-y_{a}-1\right)+\left(n-y_{b}+y_{a}+1\right)+\left(n-y_{b}\right)+\left(y_{a}-1\right)=2 n-2$ sticks. A contradiction.

Remark. One may find a different argument finishing the solution. Since $c$ and $d$ are proven to contain one stick each, there is a third cross $e$ centred at $\left(x_{*}, y_{*}\right)$ also containing at most one stick. It meets the horizontal arms of $c$ and $d$ at two $v$-cells, so all the cells where two of the three crosses meet are labelled with $v$. Now, assuming (without loss of generality) that $y_{a}<y_{*}<y_{b}$, we obtain that both vertical arms of $e$ contain $v$-cells, so $e$ is assigned to two different $v$-sticks. A contradiction.
