Can you post all the problems of RMM 2017 ? Or give the link please.

Look here

See here for a second part to the problem that did not appear on the RMM.

$m(A) = 2n-2$ is obvious to construct. For the lower bound $m(A) \ge 2n-2$, it is natural to try to prove that we can select $2n-2$ of the $n^2$ grid cells such that any stick can contain at most one of them. To do this, we do a standard bipartite matching trick. This is appeared in a few places, such as EGMO 2016/3 and IMO 1986/6. Consider the maximal vertical / horizontal sticks in the sieve. Obviously, there are $2n-2$ maximal vertical and horizontal sticks. Create a bipartite graph with left half $V$ (for vertical sticks) and right half $H$ (for horizontal sticks). For a stick $v \in V$ and $h \in H$, draw the edge $vh$ iff the vertical stick and horizontal stick intersect in at least one grid cell. Therefore, each edge in this graph corresponds to a cell in the $n \times n$ grid. Now I claim that if this graph has a perfect matching, we have found our $2n-2$ grid cells such that no stick can cover two of them. But this is clear by the definition of the graph. To show this graph has a perfect matching, we use Hall's marriage theorem. Verifying the condition of Hall is left as an exercise since I don't feel like writing it...

My solution: We claim the answer is $2n-2$. It's easy to construct a solution for $2n-2$. We go about proving this by induction. The base cases are easy, so let it be true for some $n$. Now we delete the row and the column associated with a cell that has been removed. This decreases the number of sticks by at least $2$. If not, then remove again and we can always find an $i$ for which we can use the inductive hypothesis for $i$ by the intermediate value theorem (discrete!). So we are done.

Well, my solution in the actual contest was like this: (1) It's easy that $ m(A) \leq 2n-2 $. (2) Now, let's say $ m(A) <2n-2 $. Then, let's say bit tile $ 1 \times k (k>1) $ are less than $ n-1 $. There are at least two rows that doesn't have $ 1 \times k (k>1) $ so, let's say the biggest one is $ j $ and smallest one is $ i $. ($ 1 \leq i< j \leq n $) Then, there are at least one $ 1 \times k (k>1) $ in row $ 1 $ to $ i-1 $ and $ j+1 $ to $ n $ so, we get $ n-j+i-1 $. And we use that the tiles intersecting row $ i,j $ are all $ k \times 1 (k \geq1) $. There are exactly $ j-i-1 $ erased cells between row $ i,j $.Thus we get that tiles $ k \times 1 (k \geq1) $ intersecting row $ i,j $ are at least $ n+j-i-1 $ And, so we get $ m(A) \geq (n-j+i-1)+(n+j-i-1)=2n-2 $ so contradiction. I wonder if there are people who solved like me in the contest. Most of them looked like they used induction

First of all, the answer is $2n-2$ for all sieves. This is clear since we can just take all the horizontal segments of maximal length, or all the vertical segments of maximal length. Since the "main" equality cases involve all horizontal or all vertical, it is natural to consider the following approach. Place all the horizontal segments first, and then you put the vertical segments. Consider what would happen if we placed down every horizontal segment, so that now we have to place the vertical segments down. Divide the sieve into $2n-2$ zones, as follows. Call them \[2L, 3L, \cdots nL, \cdots 1R, 2R, \cdots (n-1)R \] Each of them is defined as follows. $kL$, for example, represents all cells to the left of the unique removed cell with $x$-coordinate $k$. If there is at least horizontal stick in all of these cells, we are immediately done, for example. Say that out of the above $2n-2$ zones, exactly $k$ are unoccupied. Let's see what happens when a zone is unoccupied. Say that $4R$ was unoccupied. Then that means that there MUST be vertical sticks in every column to the right of $R$. Say the $r$ right zones are unoccupied and $\ell$ left zones are unoccupied. By the above logic, this means that the $r$ rightmost zones and $\ell$ leftmost zones must each contain at least one vertical stick. If these zones do not coincide, then we can finish since \[ m(A) \ge (2n - 2 - r - \ell) + r + \ell = (2n-2) \] If the zones do coincide, then you know that $r + \ell \ge n$. In other words, there are at least $n$ vertical sticks. Repeat the above argument for horizontal sticks, and we may conclude since the horizontal zones can't coincide. This would imply that there are at least $n$ horizontal sticks as well as vertical, and then there would be $2n$ sticks.

Another inductive solution: The answer is $2n-2$, which is attainable in every configuration by taking all horizontal sticks of maximal length. It suffices to prove that in any configuration, we can select $2n-2$ squares, no two of which can lie on the same stick, which we will do by induction with base cases $n=2,3$ obvious. Suppose the result has been show for $n=2,3,...m$ and we would like to show it for $n=m+1$. Case 1: None of the four corners of the sieve are removed. Proof: Since there must be a removed square on each of the boundary edges of the sieve, no two of the four corner squares can lie on a common stick. Now take the inner $(m-1)\times (m-1)$ array, and by the inductive hypothesis we can find $2m-4$ squares with the desired property, so after adding in the four corner squares we have $2m=2(m+1)-2$ total selected squares, as desired. Case 2: At least one corner of the sieve has been removed. WLOG suppose it is the bottom right corner. Proof: Consider any $2m-2$ squares with the desired property on the top left $m\times m$ subarray. Now note that in the $(m+1)\times (m+1)$ grid, we can find a square on the bottom row whose neighbor to the top is a removed square, and we can find a square on the rightmost column whose neighbor to the left is a removed square. It's easy to see that these squares cannot lie on the same stick as each other or the other $2m-2$ squares, so adding them to the set gives $2m$ squares with no two on the same stick, as desired. Then we have exhausted both cases, so the inductive step is complete.

Hopefully this works... RMM 2017/5 wrote: 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. Answer: $m(A)=2n-2$ is the only possible value. Place the grid on the coordinate plane, with sides parallel to the axes. Construction: For any cell of the sieve, other than those in the extreme columns, place two sticks, one on the left and the other on the right to cover the entire row containing that cell. For the other two cells, use a $1 \times (n-1)$ stick. Evidently, we have a partition using $2n-2$ sticks. Estimate: To see $m(A) \geqslant 2n-2$ for all $n \geqslant 2$, proceed by induction on $n$. Base cases are easy to see, so we proceed to the induction step for an $n \times n$ grid and an arbitrary sieve $A$. Let $R, C$ be the lowest row and the leftmost column of the grid, respectively, and $b$ be the cell in $R \cap A$. Consider the two possibilities: Case 1. $b$ is a corner. WLOG, say $b$ is the left corner. Let $c \in A$ and $d \in A$ be cells in the row just above $R$ and column just to the right of $C$, respectively. Note that there exists a horizontal stick in $R$ and a vertical stick in $C$ (by looking at cells below $c$ and to the left of $d$). Delete $b$ alongside $R, C$ to get an $(n-1) \times (n-1)$ grid and it's induced sieve $A'$. All but the sticks which completely lie inside $R$ or $C$ are destroyed, so by the induction hypothesis, we must have $$m(A) \geqslant m(A')+2 \geqslant 2(n-2)+2=2(n-1),$$as desired. Case 2. $b$ is not a corner. Take cell $r \in A$ in the row just above $R$. WLOG, $r$ is to the right of $b$; looking at the cell just below $r$ we can say that there exists a horizontal stick in $R$ to the right of $b$. Subcase 1. If there exists a horizontal stick to the left of $b$ in $R$. Delete $b$ alongside $R$ and the column $C'$ it lies in. The grid splits into two rectangular pieces; "glueing" them together in the natural way, we get an $(n-1) \times (n-1)$ grid with an induced sieve $A'$. Moreover, only vertical sticks in $C'$ and horizon sticks in $R$ have been destroyed, so by induction hypothesis, $$m(A) \geqslant m(A')+2 \geqslant 2(n-2)+2=2(n-1).$$ Subcase 2. If no horizontal stick exists to the left of $b$ in $R$. Let $x, y$ be the left, right neighbors of $b$ respectively. There is a vertical stick (say $v$) containing $x$. If any vertical stick in the column of $y$ has a cell at the same height as $v$, then column $C'$ must contain a vertical stick. Delete $R, C'$ and glue the rectangular pieces so formed, to get an $(n-1) \times (n-1)$ grid with induced sieve $A'$. It is clear that only sticks we lose are the vertical one in $C'$ and horizontal one in $R$. So, $$m(A) \geqslant m(A')+2 \geqslant 2(n-1)$$. Otherwise, each cell of $v$ above $R$ is adjacent to one of the ends of a horizontal tile. Fusing cells of $v$ with these tiles, we may assume $v$ has no cell other than $x$. So, we have reduced to subcase 1. Our induction step is complete, so the result holds. $\square$

Sorry for the bump but this in my opinion is another unique solution inspired by elmo 2017. Define a hole to be the tile which has been taken out from a row We say that a row is associated to exactly 2 sticks if there are exactly two horizontal sticks in a row which contains that hole. Similarly We say that a row is associated to 3 or more 'sticks' if the row which contains that hole is partitioned into At least a 1 * 1 square and two horizontal square, or into two 1*1 square and other being the horizontal stick. Similarly a single partition is the of the row which contains that hole into a single horizontal stick . A hole in a row/column can be associated to at least 2 sticks(except 2 squares at the extreme columns.) Assume m(a)=2n-3 sticks. If a hole is associated to a horizontal stick or a 1*1 square in a row then increase the length of the immediate left or right stick or square by one unit so that the hole is covered. Such process forms a partition of each row . Suppose one of the row(not topmost or bottommost rows) is partitioned into a single stick then it is imperative that the hole must lie on an end column or row which is a contradiction to the condition that each row/column has exactly one hole. Since increasing the length of a stick should complete cover that row. hence we are done.

Please check the solution.

I'd like to check it and learn from it, but I don't understand it at all. Can you define the associations and partitions you're using, and what you mean by "surrounded"?

I'm just as confused as before. In this configuration, I can't figure out how you can associate at least two sticks to every hole and get the second half of the solution to make sense. | |--- |||-- ||| || || ||| --||| ---| | Also, the step where you extend a stick to cover a hole just does not sound like it works in general, no matter what comes before. But maybe I'm still failing to understand your basic idea.

Okay you are right my method cannot guarantee about vertical sticks which is the main difficulty of the problem.

We claim that $m(A) = 2n-2$, and construction is just $2n-2$ vertical sticks. We can prove this with induction on $n$. The base case $n=2$ is obvious. Suppose that $m(A) = 2k-2$ for a $k \times k$ sieve, and no consider a $(k+1) \times (k+1)$ sieve. Now, if we remove the column and row for one of the deleted cells, then we would obtain a $k \times k$ sieve. For sticks that are entirely contained in this row or column, they are deleted. Other sticks may only contain one square in this row or column, and therefore would only lose one square. It suffices to show that two sticks will be deleted completely because we can reduce the resulting sieve to $2k-2$ sticks. Suppose that we choose the removed square that is going to have its row and column deleted at random. Each square has a probability $\frac{1}{k+1}$ of being chosen. Now, each stick is completely contained in either one row or column, so if there are $x$ sticks, the expected number of sticks being deleted is $\frac{x}{k+1}$. Now, it remains to show $x > k+1$. Note that this is true because the sieve has area $(k+1)^2 - (k+1)$, and each sieve has length at most $k$. Therefore, we have $x \ge \frac{(k+1)^2 - (k+1)}{k} = k+1$. Clearly equality cannot occur, so we have $x > k+1$. This means that there exists a removed square such that if we remove its column and row, it removes at least $2$ sticks. Thus, we are done.

Hopefully correct . We claim that the answer is $2n-2$ .The construction is quite easy . First of all , use dark magic to convert a stick to a bone. Other rules of the problem stay invariant. We proceed by induction. Base cases , being trivial are ommitted . Suppose $x$ is any deleted cell . Comsider the situation when the row and column through $x$ is deleted .Call the above move a "operation on $x$" We get a $(n-1) \times (n-1)$ seive . Note that in the process , some bones are unaffected , some are broken(few cells are lost) , whereas some bones are completely exterminated(which means they are deleted). Note that if $\exists x$ such that the operation on $x$ exterminates atleast 2 bones , then we are done by induction. Now we randomly choose $x$ . Note that for every bone , there is exactly one cell such that an operation on that cell exterminates the bone . So the probability that a bone gets exterminated is exactly $\frac 1n$. So we have (Let $b$ represent the $\#$bones .) $$\mathbb E [\# \text{exterminated bones}]= \frac bn$$. Next we claim that $b>n$ . This evidently finishes as then the expexted value is always greater than one and since it is a integer , there is some cell $x$ such that $\#$exterminated bones is exactly 2. Note that maximal length of a bone is $n-1$ . This implies total number of bones is atleast $\frac {n^2-n}{n-1}$ . Equality holds in the unfortunate case when the lengths of all bones are $n-1$ . But we dont buy that logic as that is obviously contradictory. We are done . $\blacksquare$

The answer is $m(A)=2n-2$. To construct, we can just cover the sieve with all vertical sticks. I claim there exists $2n-2$ squares, such that if two are on the same row, there is a removed square between them in that row. We proceed by induction on $n$, with the base case of $n=2$ being trivial. Assume this is true for $n$, and I will show this is true for $n+1.$ Let $(x,y)$ be the square on $x$th column and $y$th row. We have two cases: Case 1: a corner is removed, wlog $(1,1)$. If $(a,2)$ and $(2,b)$ are removed, mark $(a,1)$ and $(1,b)$, and we can mark the other $2n-2$ cells in the remaining $n\cdot n$ square $(x,y): 2\le x,y\le n+1$ by inductive hypothesis. Case 2: No corners are removed. Suppose $(c,1)$ is removed. We consider the $n\cdot n$ "square" $(x,y): 2\le x\le n+1, 1\le y\le n+1, y\ne c$. We can mark $2n-2$ squares. If $(d,n)$ is marked, then we mark $(d,1).$ We only need to mark one more square. We move one of the squares to the left of the removed square on its row to column c such that no new conflicts arise in that column. Suppose this square was originally on row $p$, then we mark $(p,1)$. This completes the induction.

The global minimum is $2n-2$; the construction is obvious. We proceed with induction. The base case $n=2$ is trivial. For the inductive step, consider tiling any $n$ by $n$ sieve. Notice that no stick of length $n$ or longer will fit and we seek to cover an area of $n^2-n$, so any possible construction consisting of $n$ sticks will involve only sticks of length $n-1$, which is obviously improbable. Hence, at least $n+1$ sticks must be used and there is a way to remove the row and column of an empty square that entirely removes at least two sticks, and possibly breaks apart some other sticks. Now, we can re-join the broken sticks in the resulting $n-1$ by $n-1$ sieve and apply the inductive hypothesis.

We claim the answer is $2n-2$ over every sieve. Partition the sieve into $2n-2$ straights, which is a maximal length verticle stick. Claim: If $S$ is a set of straights and $\alpha(S)$ denote the set of sticks in our tiling which intersect with one element in $S$. Then $|\alpha(S)| \geq |S|$. Partition $S$ into two sets $A$ and $B$ where $A$ is the set of straights bordering the top of the sieve and $B$ bordering the bottom. Notice that a stick cannot intersect both one element in $A$ or $B$. Thus, $|\alpha(S)|=|\alpha(A)|+|\alpha(B)|$ and $|S|=|A|+|B|$ since $A$ and $B$ are disjoint. Thus, we will prove our claim for $A$ and $B$ independently. Wlog we choose $A$ (instead of $B$). We will now show that $|\alpha(A)| \geq |A|$. We will prove this by induction on $|A|$. Indeed, if $|A|=1$ then it clearly intersects at least one stick. Now, assuming this is true for $|A|=k$, we will prove the result for $|A|=k+1$. Let $m$ be the stick of maximal length $\ell$ in $A$ and let $B=A-\{m\}$. If there is some verticle stick contained in $m$ then it does not intersect any other stick in $A$. So, we have \[|A| = |B|+1 \geq k+1\]as desired. Now, suppose there is no verticle stick contained in $m$. Let the sticks $s_1,s_2, \ldots, s_\ell$ be the $\ell$ horizontal sticks which intersect $m$. No two straights in $A$ are the same length so, by maximality, some $s_i$ cannot intersect any other element in $A$. Thus, we get the same inequality $|A| = |B|+1 \geq k+1$. Proving the claim. $\square$ So, the set of sticks is greater than or equal to the number of straights, which is $2n-2$. Construction for $2n-2$ is easy by lying sticks along each straight.

The answer for $n$ is $\boxed{2n-2}$; construction can be done with all vertical sticks. For the bound, we induct. Since a $n\times n$ sieve uses at least as many sticks as a $(n-1) \times (n-1)$ sieve, it has at least $2n-4$ sticks. By EV, there exists a removed cell such that there are at least two sticks contained entirely in either the row or column of the removed cell. Note that if we completely take out that row and column, and join the split up $n \times n$ sieve, we get a valid tiling of a $(n-1) \times (n-1)$ sieve, which we know needs at least $2n-4$ sticks. Thus, the $n\times n$ sieve needs at least $2n-4 + 2 = 2n-2$ sticks.

The answer is $2n-2$ only, which is clearly achievable by placing maximal vertical sticks (so $n-2$ rows have two sticks and $n-1$ rows have one). We now prove that we always need at least $2n-2$ sticks. To do this, I will select $2n-2$ cells such that no stick can cover two or more of them, which clearly finishes. This is by induction on $n$, with base cases trivial. Now, number the rows $1$ through $n$, with $1$ being the bottom row. Pick the removed cell on row $n$ and delete its column, as well as row $n$, and "glue" the remaining parts together in the obvious way to form an $(n-1) \times (n-1)$ array. By inductive hypothesis, select $2n-4$ cells here such that no two can be covered by a stick. It is clear that these cells will maintain this property in the original $n \times n$ array as well. Furthermore, it is evident that in every column there is one selected cell above and below the removed cell in that column, except in those columns where the removed cell is in row $1$ or $n-1$. Now reintroduce the row and column we deleted. If the cell on row $n$ is on the leftmost or rightmost column, then we may select two more cells: the one to the left/right of the second-leftmost/rightmost removed cell (resp.) and the one to the top of the second-topmost, which clearly works. Otherwise, we still take the cell above the second-topmost removed cell. Then we consider the highest removed cell on the other side, which should have a selected cell above it, say on row $k$. Then we deselect this cell and add the cell in the same column but on row $n$, which clearly won't be contained in a stick with any other cells. Finally, in the column of the cell on row $n$, we add the cell on row $k$, which cannot be contained in a stick with any other cells, since otherwise in the $(n-1) \times (n-1)$ construction the deselected cell would've been containable in a stick with other cells (by the maximality of the removed cell). Therefore this construction, with $2n-2$ selected cells, will work for the $n \times n$ grid. Therefore, we are done. $\blacksquare$

The answer is 2n-2, with all vertical sticks; we'll proceed by induction, with base case n=2 evident. Note that there must be at least n+1 sticks used, since n and less don't suffice; they would need to cover at least n-1 area which is impossible with removed squares. Now, by pigeonhole at least one stick is in a row and column, or there's two stacked on one row/column; in the former, put an empty square in the intersection (since we consider all cases), and join the remaining stuff together, which reduces to n-1xn-1, hence the answer is 2(n-1)-2+2 in this case. In the latter, remove the row/column which entirely contains two sticks, then remove an arbitrary one of the other type, reducing it into n-1xn-1 again, which again gives the claimed answer. $\blacksquare$

Note that $m(A) \le 2(n-1)$ through tiling all rows or columns. We now claim that $m(A)$ can only equal $2(n-1)$. Let a cut row or column refer to the potentially two parts of a column created after the removal of cell. Consider the bipartite graph between the $2(n-1)$ cut rows and cut columns of $A$. It remains to show Hall's condition holds. Let $V$ be a subset of the $2(n-1)$ columns. If $|V| < (n-1)$, then there is sum of the minimal length of cut rows touching the left side and the minimal of cut rows touching the right side is at least $|V|$ by pigeonhole, so at least $|V|$ cut columns are covered. Else, if $|V| \ge (n-1)$, there is at least $|V| - (n-2)$ rows with all of its corresponding cut row(s) filled in. Then, these complete rows, when sorted from left to right, cover at least $(n-1) + 1 \cdot (|V| - (n-2) - 1) = |V|$ cut columns.

The answer is $m(A) = 2n-2$ as the only possible value. We will present a construction for it and subsequently a proof of it as an upper bound. Construction. For the construction, let the removed cells in the first and last rows be opposite corners of the grid, and use only vertical sticks so that there is $1$ stick in the first and last rows and $2$ in the other rows, for a total of $2(n-2)+1+1=2n-2$ sticks. Upper bound. We will induct downwards on $n$, with the base case $n=1$ trivially true. Suppose that for some $n$, we know that any partition of a $n \times n$ sieve has at most $2n-2$ sticks. In each removed cell of the sieve, write down the number of complete sticks in its row and column combined. Note that the sum of the numbers in the removed cells is equal to the total number of sticks. By the inductive hypothesis and Pigeonhole, there exists a removed cell with a number at least $\lceil \tfrac{2n-2}{n} \rceil = 2$ written in it. For the inductive step, delete the union of the row and column of $\mathcal{C}$ to obtain a smaller $(n-1) \times (n-1)$ sieve, with at least $2$ less sticks than in the original configuration. Thus the number of sticks in the new configuration is at most $(2n-2)-2 = 2(n-1) - 2$, completing the inductive step.

For the $n - 2$ rows with the 'removed' cell not on the edges, there are at least $2$ sticks in the row. For the $2$ edge rows, there are at least $1$ row. Then the maximum of $m(A)$ is $2(n - 2) + 2 = 2(n - 1)$. We will prove that $m(A) = 2(n - 1)$ for all $n$, by using induction. $\newline$ Base Case: Our base case is $n = 2$. Note that there are only two possible configurations here, both of which are just reflections of each other. The minimum number of sticks in this configuration is equal to $2 = 2(2) - 2$. $\newline$ Inductive Step: Define a cross to be the union of a row and column, which intersect at a deleted square in the sieve. Assume that the minimum sticks for this $n \times n$ sieve is $2n - 2$. We can delete the cross of a random deleted square, to create a $(n - 1) \times (n - 1)$ square. $\newline$ Now, note that we can globally sum the number of fully intact sticks in each sieve. Note that this number is equal to the total number of sticks in the sieve. Since we have $n$ crosses, and at most $2n - 2$ sticks, the average number of sticks per cross is $2 - \frac{2}{n}$. This then implies that there is at least one cross that contains two sticks. By choosing to delete this cross each time, we reduce the number of sticks by $2$, and we reduce the $n \times n$ sieve to an $(n - 1) \times (n - 1)$ sieve. Since $2n - 4 = 2(n - 1) - 2$, our induction is done.

The answer is $2n-2$ regardless of the arrangement of removed cells. For construction, one can place two horizontal rectangles in each row where the removed cell is not first or last (there are $n-2$ such rows) and one horizontal rectangle in rows where the removed cell is first or last (there are $2$ such rows) - in total there are $2(n-2) + 1 \cdot 2 = 2n-2$ rectangles. We establish the bound by induction on $n$. The base case $n=2$ holds since after removing $2$ cells there are $2$ remaining with a common vertex and hence require at least $2$ rectangles. Assume for $n-1$ (where $n\geq 3$) and suppose there exists a configuration on an $n\times n$ table with $m\leq 2n-3$ rectangles. For each removed cell consider the pair of its row and column. There are $n$ such pairs, hence by the Pigeonhole principle there exists a row and column with a total of at least $\left\lceil \frac{m}{n} \right\rceil$ rectangles. After removing this row and column, the amount of remaining rectangles is at most $m - \left\lceil \frac{m}{n} \right\rceil$, but also at least $2n-4$ by the induction hypothesis. In particular, $m\geq 2n-4$. If $m=2n-4$, then $m - \left\lceil \frac{m}{n} \right\rceil \geq 2n-4$ is false for $n\geq 3$ since the ceiling is positive due to $2n-4 > 0$. If $m=2n-3$, then $2n-3 - \left\lceil 2 - \frac{3}{n} \right\rceil \geq 2n-4$, i.e. $\left\lceil 2 - \frac{3}{n} \right\rceil \leq 1$ and this is false for $n\geq 4$. It only remains to separately deal with $n=3$, which is case-bashable. Up to symmetries there are two possibilities. If the central cell is removed, then so are the other two from some of the two diagonals and each of the two remaining halves requires $2$ rectangles. Otherwise, exactly one diagonal cell is removed - say, the lower-left, then the other two are the second on first row and third on second row; what remains is an isolated $1\times 1$ square and a zig-zag figure of $5$ cells which requires $3$ rectangles.

I claim $m(A)$ is always equal to $2n-2$, I will proceed by induction, suppose the result holds for an $n-1$ by $n-1$ sieve, now we take an $n$ by $n$ sieve and remove a cross which is a row and a coloumn such that they are centred on a removed square and such that neither the row or the coloumn is on an edge of the square. Suppose there does not exist two sticks that are fully contained within the removed cross, we must have that there for the $2$ sections in thee coloumn on either side of the removed cell that the sticks passing through them go out from them, thus what we can do is extend all the sticks in these two sections so that all cells not in the row that acomponies the coloumn are covered by one of these sticks, clearly this doesnt increase the number of sticks and implies that there are at least two sticks fully contained within the cross which suffices. wtf this is like 15m

Nice grids problem which can be solved by using bipartite graph! By the way, verifying Hall’s condition is not easy as it looks. The answer is $m(A)=2n-2$ for all possible sieve $A$ of the size $n \times n$ We split the problem into two parts. Part(i) ; Construction We can just take all the vertical sticks of maximal length, we obtain a partition of $A$ into $2n-2$ sticks. $\implies m(A)\leq 2n-2$ Part(ii) ; Bound We’re going to show that for any sieve $A$ of the size $n \times n$, it is impossible to partition $A$ into less than $2n-2$ sticks. It is sufficient to show that we can find $2n-2$ cells s.t. for any two of them, there exists no stick which cover both cells. $(\spadesuit)$ We construct a bipartite graph $G$ between $V$ and $H$ where $V$ is the set of all maximal vertical sticks and $H$ is the set of all maximal horizontal sticks. (Maximal stick is the stick that cannot be extended further along its direction.) We draw an edge between a stick in $V$ and a stick in $H$ iff they share a common cell. Note that $(\spadesuit)$ is equivalent to finding a perfect matching in $G$. Now, we’re left to verify the Hall’s Condition Claim For any subset $S$ of $V$, $|N(S)|\geq|S|$ Proof We call a maximal vertical stick “above” iff it touches the top side of the sieve $A$. Similarly, we call a maximal vertical stick “bottom” iff it touches the bottom side of the sieve $A$. Let $a$ be the longest length among all above sticks in $S$ and $b$ be the longest length among all bottom sticks in $S$. Since the length of all bottom sticks in $S$ are different positive integers, $a\geq \#\text{bottom sticks in} S$ Similarly, $b\geq \# \text{above sticks in} S$ $\implies a+b\geq \#\text{above sticks in} S+\#\text{bottom sticks in} S = |S|$ $(\clubsuit)$ $ |S|\leq n$ If $a+b\leq n$, the longest above stick and longest bottom stick in $A$ spans in total of $a+b$ columns. $\implies |N(S)|\geq a+b \geq |S|$ and we’re done. If $a+b>n$, the longest above stick and longest bottom stick in $S$ spans in total all $n$ columns. $\implies |N(S)|\geq n\geq |S|$ and we’re done If $|S|>n$, let $S’=V-S$ and $N’(S)=H-N(S)$ Note that every sticks in $N’(S)$ do not intersects any sticks in $S$ $\implies$ $N(N’(S)) \subseteq S’ \implies |S’|\geq |N(N’(S))|$ From $(\clubsuit)$, we obtain $a+b\geq |S|>n$ which means that the longest above stick and longest bottom stick in $S$ spans in total all $n$ columns $\implies |N(S)|\geq n \implies |N’(S)|\leq n-2< n$ By repeating the same argument as the previous case, $|N(N’(S))|\geq |N’(S)| $ $\therefore |S’|\geq |N(N’(S))| \geq |N’(S)|\implies (2n-2)-|S’|\leq (2n-2)-|N’(S)| \implies |S| \leq |N(S)|$

The answer is $m(A) = 2n-2$ sticks always. We can clearly partition an $n \times n$ sieve using $2n-2$ sticks by allocating $2$ sticks to every row, $1$ stick for rows for which the edge square is removed. Call a fork the union of a row and a column which intersect at a square removed by the sieve. We proceed by induction on $n$. The idea is that we can do a sort of ``probabilistic induction" by not explicitly stating what fork to remove. Claim: [Housekeeping] $m(A) > n$ for all $n \times n$ sieves $A$. Proof: Note that all sticks cover at most $n-1$ squares; thus, to have $m(A) \leq n$, all sticks must be $1 \times (n-1)$. But this is clearly impossible after placing the first stick by picking a row where the removed square of the sieve is in the middle of the row. $\blacksquare$ So now, suppose that for all $k \leq n$, any $k \times k$ sieve requires at least $2k-2$ sticks to be covered, and assume for the sake of contradiction that an $n \times n$ sieve $A$ can be covered with less than $2n-2$ sticks. Then, notice that every stick in the partition is contained in at least one fork, and as there are at least $n+1$ sticks and $n$ forks, there must exist a fork that contains two sticks. We may remove this fork and truncate or reconnect any sticks that span this fork to create a partition of the $(n-1) \times (n-1)$ sieve that contains less than $2n-4$ sticks, which is a contradiction.