Problem 1188

Solution 1. (a) The required minimum is $2 n-2$ and is achieved, for instance, by dissecting $A$ along all horizontal (or vertical) grid lines.

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.

Consider a dissection of $A$ into $2 n-2$ 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-2$ sticks and exactly $n$ crosses, either there is a cross assigned to no stick in the dissection, or there are two crosses each of which is assigned to exactly one stick in the dissection.

Case 1: There is a cross assigned to no stick in the dissection. In this case, the vertical arms of the cross are both all- $h$, and the horizontal arms are both all- $v$, so no stick in the dissection covers more than one of the $2 n-2$ cells along the arms of the cross. Consequently, there are at least $2 n-2$ sticks.

Case 2: There are two crosses each of which is assigned to exactly 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}y_{j}$ for some indices $i$ and $j$, the cell $\left(x_{j}, y_{i}\right)$ is covered by no stick having a cell on the bottom row or on the leftmost column, so the number of dissections satisfying the condition in the lemma is zero.

Otherwise, label the holes so that $x_{i}<x_{i+1}$ and $y_{i}<y_{i+1}$ and notice that the union of all horizontal sticks in a dissection satisfying the conditions in the lemma is separated from the union of all vertical sticks in that dissection by a broken line running up-and-to-the-right along grid lines from the lower left corner of $B$ to the upper right corner of $B$.

Since each such path determines at most one dissection satisfying the condition in the lemma, the number of possible dissections does not exceed the number of such paths, which is $\binom{p+q}{p} \leq$ $2^{p+q}$.

Back to the problem, consider dissections $\mathcal{D}$ of $A$ into $2 n-2$ sticks, along with the two cases in the solution to part (a).

Case 1: There is a cross $c$, assigned to no stick in $\mathcal{D}$; let $a$ be the hole at the center of $c$. The cross $c$ subdivides $A$ into four quadrants. Extend each of these quadrants by adding the two arms of $c$ that bound it, along with the hole $a$, to obtain an array as described in the lemma. Since $|\mathcal{D}|=2 n-2$, each stick in $\mathcal{D}$ contains exactly one cell of the cross $c$. Therefore, the restriction of $\mathcal{D}$ to each extended quadrant satisfies the condition in the lemma, so there are at most $2^{4 n+4}$ such dissections involving $c$; and since there are $n$ options for the centre of $c$, the number of these dissections does not exceed $2^{4 n+4} n$.

Case 2: There are two crosses each of which is assigned to exactly one stick in $\mathcal{D}$. Use the notation, conventions and choices in the solution to part (a). Since $|\mathcal{D}|=2 n-2$, the evaluation in part (a) exhausts the sticks in $\mathcal{D}$. So the restriction of $\mathcal{D}$ to the strip flanked by the two rows through $a$ and $b$, respectively, consists of vertical sticks only; and the restrictions of $\mathcal{D}$ to the extensions of the upper (respectively, lower) quadrants around $b$ (respectively, $a$ ) satisfy the condition in the lemma. It follows that there are at most $2^{4 n+2}$ such dissections involving $c$ and $d$. Since there are $\binom{n}{2}=n(n-1) / 2$ options for the centres of $c$ and $d$, and the sticks covering the cells $\left(x_{a}, y_{b}\right)$ and $\left(x_{b}, y_{a}\right)$ may be labelled two ways (recall that they have like labels), the number of these dissections does not exceed $2^{4 n+2} n(n-1)$.

Consequently, the total number of minimal dissections of $A$ into sticks does not exceed $2^{4 n+2} n(n+3)$; the latter is less than $100^{n}$, provided that $n \geq 3$, and the case $n=2$ is clear.