IMO Team Selection Test 3, June, 2020

We show that the largest $m$ Merlijn can pick is $\min(n, 3(n-k)+1)$. First we show that $m \le \min(n, 3(n-k)+1)$. If Merlijn asks for $n+1$ tiles, Julian can instruct Merlijn to place them all horizontally. As $n \le 2k-1$, it is impossible to place more than one tile horizontally on a single row, so Merlijn would need at least $n+1$ rows, this is a contradiction. Therefore $m \le n$.

Now suppose that Merlijn asks for $3(n-k)+2$ tiles. Julian can now instruct Merlijn to place $n-k+1$ tiles vertically and $2n-2k+1$ tiles horizontally.

Note that vertical tiles always cover the $k - (n-k) = 2k - n \ge 1$ rows in the middle of the board. Therefore the vertical tiles together cover at least $n-k+1$ squares in each of these rows in the middle of the board, leaving at most $k-1$ squares for the horizontal tiles. Therefore no horizontal tiles fit in these middle rows, and the $2n-2k+1$ horizontal tiles need to fit in the remaining $n-(2k-n) = 2n-2k$ rows. This is a contradiction. Therefore we must have $m \le 3(n-k)+1$. It follows that $m \le \min(n, 3(n-k)+1)$.

Now we show that it is always possible to place a pile of $\min(n, 3(n+k)+1)$ tiles on the board. We first consider two special configurations. Put $n-k$ horizontal tiles into a $(n-k) \times k$-rectangle at the bottom left. To the right of that, we can fit $n-k$ more vertical tiles into a $k \times (n-k)$-rectangle in the bottom right. Above that rectangle, we can fit $n-k$ more horizontal tiles into a $(n-k) \times k$-rectangle in the top right. Finally, to the left of that, we can fit $n-k$ more vertical tiles into a $k \times (n-k)$-rectangle in the top left. In this way, we can fit $2(n-k)$ horizontal and $2(n-k)$ vertical tiles on the board.

One other way to cover the board is as follows. Place $n$ vertical tiles in the top left, covering a $k \times n$-rectangle. Below that there is room for $n-k$ horizontal tiles to fit in an $(n-k) \times k$-rectangle. In this way, we can fit $n$ vertical and $n-k$ horizontal tiles on the board.

Suppose that Merlijn receives $A$ horizontal tiles and $B$ vertical tiles from Julian. Then we have $A+B \le n$ and $A+B \le 3(n-k)+1$. Without loss of generality we assume that $A \le B$. If $A \le n-k$, then Merlijn uses the second special configuration, omitting tiles he doesn't have. As $B \le n$, this works. Else, $A \ge n-k+1$, so $B \le 3(n-k)+1-A \le 3(n-k)+1-(n-k+1) = 2(n-k)$. As $A \le B$, we also have $A \le 2(n-k)$, and Merlijn can use the first configuration, omitting tiles he doesn't have. Therefore it is always possible for Merlijn to place $\min(n, 3(n-k)+1)$ tiles on the board. $\square$