Let $n \geq 3$ be an integer and consider an $n \times n$ board, divided into $n^{2}$ unit squares. We have for each $m \geq 1$ arbitrarily many $1 \times m$ rectangles (type I) and arbitrarily many $m \times 1$ rectangles (type II) available. We cover the board with $N$ of these rectangles, which do not overlap and do not extend beyond the board. The total number of type I rectangles on the board must be equal to the total number of type II rectangles on the board. (Note that a $1 \times 1$ rectangle is both of type I and of type II.) What is the smallest value of $N$ for which this is possible?
We prove that the minimal value $N=2n-1$. First, we construct an example by induction.
Base case. For $n=3$, $N=5$ is possible, by placing a $1 \times 1$ rectangle in the middle field and covering the remaining fields with four $2 \times 1$ and $1 \times 2$ rectangles. There are then three rectangles with height 1 (type I) and three rectangles with width 1 (type II), where the $1 \times 1$ rectangle is counted twice.
Inductive step. Let $k \geq 3$ and assume that we can cover a $k \times k$ board with $2k-1$ rectangles such that all conditions are met. Consider a $(k+1) \times (k+1)$ board and cover the $k \times k$ sub-square at the bottom right according to the inductive hypothesis. Then cover the left column with a rectangle of width 1 and height $k+1$, and cover the remaining space with a rectangle of height 1 and width $k$. We have now used one more rectangle with width 1 and one more rectangle with height 1, so the condition is satisfied and we have used $2k-1+2=2(k+1)-1$ rectangles. This constructs an example for $n=k+1$.
This proves that it is possible to cover the board with $N=2n-1$ rectangles. We now want to prove that it cannot be done with fewer rectangles. Let $k$ be the number of rectangles with width 1 and height greater than 1. Then the number of rectangles with height 1 and width greater than 1 is also $k$. Let $l$ be the number of $1 \times 1$ rectangles. Thus, $N=2k+l$. If $k \geq n$, then $N \geq 2n$, so there is nothing to prove in this case. We therefore assume that $k < n$ and we will prove that then $l \geq 2n-2k-1$, so that $N \geq 2n-1$.
Each rectangle with width 1 can only cover fields in one column. Therefore, there are $n-k$ columns in which no field is covered by a rectangle with width 1 and height greater than 1. Similarly, there are $n-k$ rows in which no field is covered by a rectangle with height 1 and width greater than 1. Consider the $(n-k)^2$ fields that lie in both such a row and such a column. These fields must be covered by $1 \times 1$ rectangles. Thus, $l \geq (n-k)^2$.
We have $(k-n+1)^2 \geq 0$, so $k^2 + n^2 + 1 - 2kn + 2k - 2n \geq 0$, and thus $n^2 - 2kn + k^2 \geq 2n - 2k - 1$. We conclude that $l \geq (n-k)^2 \geq 2n - 2k - 1$, which is exactly what we wanted to prove. Therefore, in all cases, $N \geq 2n-1$, and this proves that the minimal value of $N$ is $2n-1$.