Given are two positive integers $k$ and $n$ with $k \leq n \leq 2 k-1$. Julian has a large stack of rectangular $k \times 1$-tiles. Merlin names a positive integer $m$ and receives $m$ tiles from Julian to place on an $n \times n$ board. On each tile, Julian first writes whether it must be a horizontal or a vertical tile. Tiles must not overlap on the board and they must not stick out. What is the largest number $m$ that Merlin can name if he wants to be sure that he can place all the tiles according to Julian's instructions on the board?
We prove that the largest $m$ that Merlin can name is equal to $\min (n, 3(n-k)+1)$. First, we prove that $m \leq \min (n, 3(n-k)+1)$. If Merlin orders $n+1$ tiles, Julian can label all of them as horizontal. Since $n \leq 2k-1$, it is not possible to place more than one horizontal tile in the same row, so Merlin would need $n+1$ rows, which is a contradiction. Therefore, it must hold that $m \leq n$.

Now suppose that Merlin orders $3(n-k)+2$ tiles. Julian can then make $n-k+1$ tiles vertical and $2n-2k+1$ tiles horizontal. Vertical tiles can cover squares from the top $k$ rows, the bottom $k$ rows, or $k$ rows in between, but in all cases, they cover squares from the $k-(n-k)=2k-n \geq 1$ middle rows of the board. In each of these middle rows, the vertical tiles cover at least $n-k+1$ squares, leaving $k-1$ squares for the horizontal tiles. No horizontal tile can fit in these $2k-n$ middle rows, so all horizontal tiles must be in the remaining $n-(2k-n)=2n-2k$ rows. However, there are $2n-2k+1$ horizontal tiles, which is a contradiction. Therefore, it must hold that $m \leq 3(n-k)+1$. Altogether, we have $m \leq \min (n, 3(n-k)+1)$.

Now we prove that it is always possible to place a collection of $\min (n, 3(n-k)+1)$ tiles on the board. We first consider two special configurations. Place $n-k$ horizontal tiles in the bottom-left corner, covering a rectangle of height $n-k$ and width $k$. To the right of this, exactly $n-k$ vertical tiles can fit (as far down as possible), covering a rectangle of width $n-k$ and height $k$. Above this, exactly $n-k$ horizontal tiles can fit (as far to the right as possible), and there is space left in the top-left corner for $n-k$ vertical tiles. Thus, we can place $2(n-k)$ horizontal and $2(n-k)$ vertical tiles. Another way to cover the board is as follows. Place $n$ vertical tiles at the top, covering a rectangle of width $n$ and height $k$. There is then space below for $n-k$ horizontal tiles (each in its own row; the exact placement does not matter). It is therefore also possible to place $n$ vertical and $n-k$ horizontal tiles.

Now suppose that Merlin receives $A$ horizontal tiles and $B$ vertical tiles from Julian. Then $A+B \leq n$ and $A+B \leq 3(n-k)+1$. Without loss of generality, assume that $A \leq B$. If $A \leq n-k$, then Merlin uses the second special configuration and removes tiles as needed. Since $B \leq n$, this works. On the other hand, if $A \geq n-k+1$,
![](https://cdn.mathpix.com/cropped/2024_12_06_b9d7fc7a50c35493cd4fg-7.jpg?height=486&width=1210&top_left_y=364&top_left_x=447)

then $B \leq 3(n-k)+1-A \leq 3(n-k)+1-(n-k+1)=2(n-k)$. Since $A \leq B$, it also holds that $A \leq B \leq 2(n-k)$. Therefore, Merlin can use the first special configuration, removing tiles as needed. Thus, Merlin can always place $\min (n, 3(n-k)+1)$ tiles on the board.