(RMM 2017 P5) Let $n \geq 2$ be an integer. A sieve is an $n \times n$ grid from which $n$ cells have been removed, with exactly one removed from each row and each column. A stick is a $1 \times k$ or $k \times 1$ rectangle of cells, with $k$ a positive integer. For a sieve $A$, let $m(A)$ be the minimum number of sticks needed to partition $A$. Determine the possible values of $m(A)$.
Let $A$ be a sieve. Then by placing only horizontal sticks, we must place two per line except for the two lines where the removed cell is at the end, where we need to place one. Thus, we obtain a partition with $2n-2$ sticks and we get

$$
m(A) \leq 2n-2
$$

We will show that in fact for any sieve $A$, the bound is achieved, that is, $m(A) = 2n-2$. For this, we proceed by induction on $n$. For $n=2$ and $n=3$, we can verify the result by hand, so we assume it is true for $n-1$. We then consider a tiling of a sieve $A$ of side $n \geq 4$ with $m(A)$ sticks.

We note that if we choose a removed cell and delete its row and column, we obtain a tiling of the new sieve obtained by cutting some sticks in half and then reattaching them, and by deleting others. The sticks deleted are precisely the horizontal sticks on the same row as the cell or the vertical sticks on the same column as the cell; we say that these sticks are associated with the removed cell. Each stick in the tiling is associated with a removed cell, or possibly with two for the $1 \times 1$ cells.

In all cases, if there are at least $n+1$ sticks in the tiling, by the pigeonhole principle, one of the removed cells has at least 2 associated sticks. By deleting its row and column, we therefore delete at least 2 sticks, and the tiling of the sieve of side $n-1$ obtained has at most $m(A)-2$ sticks. By the induction hypothesis, we have $m(A)-2 \geq 2n-4$ and $m(A) \geq 2n-2$.

Suppose now that there are at most $n$ sticks in the tiling. Then it suffices to take any removed cell with an associated stick and delete its row and column. Then we delete at least 1 stick, and the tiling of the sieve of side $n-1$ obtained has at most $n-1$ sticks. By the induction hypothesis, we have $n-1 \geq 2n-4$, which is absurd since $n \geq 4$.

Thus, in all cases, we have $m(A) = 2n-2$.