, 2016

The required minimum is $n$ if $n = k$, and it is $\min(n, 2n-2k+2)$ if $k < n < 2k$.

The case $n=k$ being clear, assume henceforth $k < n < 2k$. Begin by describing maximal arrangements on the board $[0, n] \times [0, n]$, having the above mentioned cardinalities.

If $k < n < 2k-1$, then $\min(n, 2n-2k+2) = 2n-2k+2$. To obtain a maximal arrangement of this cardinality, place four tiles, $[0, k] \times [0, 1]$, $[0, 1] \times [1, k+1]$, $[1, k+1] \times [k, k+1]$ and $[k, k+1] \times [0, k]$ in the square $[0, k] \times [0, k]$, stack $n-k-1$ horizontal tiles in the rectangle $[1, k+1] \times [k+1, n]$, and erect $n-k-1$ vertical tiles in the rectangle $[k+1, n] \times [1, k+1]$.

If $n = 2k-1$, then $\min(n, 2n-2k+2) = n = 2k-1$. A maximal arrangement of $2k-1$ tiles is obtained by stacking $k-1$ horizontal tiles in the rectangle $[0, k] \times [0, k-1]$, another $k-1$ horizontal tiles in the rectangle $[0, k] \times [k, 2k-1]$, and adding the horizontal tile $[k-1, 2k-1] \times [k-1, k]$.

The above examples show that the required minimum does not exceed the mentioned values.

To prove the reverse inequality, consider a maximal arrangement and let $r$, respectively $c$, be the number of rows, respectively columns, not containing a tile.

If $r=0$ or $c=0$, the arrangement clearly contains at least $n$ tiles.

If $r$ and $c$ are both positive, we show that the arrangement contains at least $2n-2k+2$ tiles. To this end, we will prove that the rows, respectively columns, not containing a tile are consecutive. Assume this for the moment, to notice that these $r$ rows and $c$ columns cross to form an $r \times c$ rectangular array containing no tile at all, so $r < k$ and $c < k$ by maximality. Consequently, there are $n-r \ge n-k+1$ rows containing at least one horizontal tile each, and $n-c \ge n-k+1$ columns containing at least one vertical tile each, whence a total of at least $2n-2k+2$ tiles.

We now show that the rows not containing a tile are consecutive; columns are dealt with similarly. Consider a horizontal tile $T$. Since $n < 2k$, the nearest horizontal side of the board is at most $k-1$ rows away from the row containing $T$. These rows, if any, cross the $k$ columns $T$ crosses to form a rectangular array no vertical tile fits in. Maximality forces each of these rows to contain a horizontal tile and the claim follows.

Consequently, the cardinality of every maximal arrangement is at least $\min(n, 2n-2k+2)$, and the conclusion follows.