THE Tenth ROMANIAN MASTER OF MATHEMATICS

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 $2n-3$ or fewer sticks. Horizontal sticks are all labeled $h$, and vertical sticks are labeled $v$; $1\times 1$ sticks are both horizontal and vertical, and labeled 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 $2n-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$, centered at $a=(x_a,y_a)$ and $b=(x_b,y_b)$, respectively, and assume, without loss of generality, $x_a<x_b$ and $y_a<y_b$. The sticks covering the cells $(x_a,y_b)$ and $(x_b,y_a)$ 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.



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(y_b-y_a-1)+(n-y_b+y_a+1)+(n-y_b)+(y_a-1)=2n-2$ sticks – a contradiction.

Remark. The solution may equally well be concluded as follows. Since $c$ and $d$ are proved to contain one stick each, there is a third cross $e$ centered at $(x_{\ast },y_{\ast })$ also containing at most one stick. It meets the horizontal arms of $c$ and $d$ at two $v$-cells, so the cells where two of the three crosses meet are all labeled $v$. Assuming, without loss of generality, $y_a<y_{\ast }<y_b$, it follows that both vertical arms of $e$ contain $v$-cells, so $e$ is assigned to two different $v$-sticks – a contradiction.

Second solution. (Ilya Bogdanov) We provide a different proof that $m(A)\ge 2n-2$.

Call a stick vertical if it is contained in some column, and horizontal if it is contained in some row; $1\times 1$ sticks may be called arbitrarily, but any of them is supposed to have only one direction. Assign to each vertical/horizontal stick the column/row it is contained in. If each row and each column is assigned to some stick, then there are at least $2n$ sticks, which is even more than we want. Thus we assume, without loss of generality, that some exceptional row $R$ is not assigned to any stick. This means that all $n-1$ existing cells in $R$ belong to $n-1$ distinct vertical sticks; call these sticks central.

Now we mark $n-1$ cells on the board in the following manner. (↓) For each hole $c$ below $R$, we mark the cell just under $c$; (↑) for each hole $c$ above $R$, we mark the cell just above $c$; and (●) for the hole $r$ in $R$, we mark both the cell just above it and just below it. We have described $n+1$ cells, but exactly two of them are out of the board; so $n-1$ cells are marked within the board. A sample marking is shown in the figure below, where the marked cells are crossed.



Notice that all the marked cells lie in different rows, and all of them are marked in different columns, except for those two marked for (●); but the latter two have a hole $r$ between them. So no two marked cells may belong to the same stick. Moreover, none of them lies in a central stick, since the marked cells are separated from $R$ by the holes. Thus the marked cells should be covered by $n-1$ different sticks (call them border) which are distinct from the central sticks. This shows that there are at least $(n-1)+(n-1)=2n-2$ distinct sticks, as desired.

Third solution. To prove $m(A)\ge 2n-2$, it is sufficient to show that there are $2n-2$ cells in $A$, no two of which may be contained in the same stick.

To this end, consider the bipartite graph $G$ with parts $G_h$ and $G_v$, where the vertices in $G_h$ (respectively, $G_v$) are the $2n-2$ maximal sticks $A$ is dissected into by all horizontal (respectively, vertical) grid lines, two sticks being joined by an edge in $G$ if and only if they share a cell.

We show that $G$ admits a perfect matching by proving that it fulfils the condition in Hall's theorem; the $2n-2$ cells corresponding to the edges of this matching form the desired set. It is sufficient to show that every subset $S$ of $G_h$ has at least $|S|$ neighbours (in $G_v$, of course).

Let $L$ be the set of all sticks in $S$ that contain a cell in the leftmost column of $A$, and let $R$ be the set of all sticks in $S$ that contain a cell in the rightmost column of $A$; let $\ell$ be the length of the longest stick in $L$ (zero if $L$ is empty), and let $r$ be the length of the longest stick in $R$ (zero if $R$ is empty). Since every row of $A$ contains exactly one hole, $L$ and $R$ partition $S$; and since every column of $A$ contains exactly one hole, neither $L$ nor $R$ contains two sticks of the same size, so $\ell \ge |L|$ and $r\ge |R|$, whence $\ell +r\ge |L|+|R|=|S|$. If $\ell +r\le n$, we are done, since there are at least $\ell +r\ge |S|$ vertical sticks covering the cells of the longest sticks in $L$ and $R$. So let $\ell +r>n$, in which case the sticks in $S$ span all $n$ columns, and notice that we are again done if $|S|\le n$, to assume further $|S|>n$. Let $S^{\prime }=G_h\setminus S$, let $T$ be set of all neighbours of $S$, and let $T^{\prime }=G_v\setminus T$. Since the sticks in $S$ span all $n$ columns, $|T|\ge n$, so $|T^{\prime }|\le n-2$. Transposition of the above argument (replace $S$ by $T^{\prime }$), shows that $|T^{\prime }|\le |S^{\prime }|$, so $|S|\le |T|$.

Remark. The case $|S|>n$ may equally well be dealt with as follows. Add to $S$ two empty sticks formally present to the left (respectively, right) of the leftmost (respectively, rightmost) hole. Then there are at least $|S|-n+2$ rows containing two sticks from $S$, so two of these rows are separated by at least $|S|-n$ other rows. Each hole in these $|S|-n$ rows separates two vertical sticks from $G_v$ both of which are neighbours of $S$. Consequently, $S$ has at least $n+(|S|-n)=|S|$ neighbours.

Fourth solution. Induct on $n\ge 2$ to prove that $m(A)\ge 2n-2$. The base cases $n=2$ and $n=3$ are readily dealt with, so let $n>3$ and consider any dissection of $A$ into sticks. Define the cross of a hole as in Solution 1, and notice that each stick is contained in some cross.

If the dissection contains more than $n$ sticks, some cross contains at least two sticks. Remove such a cross from the sieve and glue pieces together along corresponding edges to form an $(n-1)\times (n-1)$ sieve. The dissection of the original sieve induces a dissection of the new sieve: Upon removal, a stick may split into two substicks that glue back together to form a stick in the new sieve. After this operation has been performed, the number of sticks decreases by at least 2, and since by the induction hypothesis the number of sticks in the new dissection is at least $2n-4$, the initial dissection contains at least $(2n-4)+2=2n-2$ sticks.

There are several different ways to rule out the case where the dissection contains at most $n$ sticks. For instance, removal of a cross containing some stick. The induced dissection of the resulting $(n-1)\times (n-1)$ sieve contains at most $n-1$ sticks, which is impossible by the induction hypothesis, since $n-1<2(n-1)-2$.

Therefore, for any $n\times n$ sieve $A$, $m(A)=2n-2$.