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$