(EGMO 2016 P5) Let $k, n$ be integers such that $2 \leq k \leq n \leq 2 k-1$ and consider an $n \times n$ grid. As long as possible, we add $1 \times k$ or $k \times 1$ rectangles to the grid so that each rectangle covers exactly $k$ cells and no two rectangles overlap. We stop when this operation is no longer possible. Find, in terms of $n$ and $k$, the minimum number of rectangles in a final configuration.
We will show that the result is:

$$
\left\{\begin{array}{l}
n \text { if } k=n \text { or } 2 k-1=n \\
2(n-k+1) \text { otherwise }
\end{array} .\right.
$$

We call a stick a rectangle $1 \times k$ or $k \times 1$. Suppose we only have sticks oriented in the same direction, for example, vertically. Then we can always place at least $n$ sticks, one on each column. Moreover, by alternating a stick touching the bottom side and a stick touching the top side, the condition $2 k-1 \geq n$ gives a configuration where no more sticks can be added. Thus, we can always find a final configuration with $n$ sticks, and if all the sticks are in the same direction, this is the minimum number.

Now suppose we have a configuration with both vertical and horizontal sticks. If there is a vertical stick on a column, since $n \leq 2 k-1$, it is strictly less than $k$ units away from one of the two edges, for example, the left edge. Then between the stick and this edge, no horizontal stick can be placed, but a vertical stick can be placed on each column. Thus, all columns from the left edge contain a vertical stick.

By doing the same with the right edge, the columns that do not contain a vertical stick are adjacent. If there were at least $k$ such columns, we could then place a horizontal stick in each row, between the columns that contain vertical sticks, and the final configuration would contain at least $n$ sticks. This configuration is not optimal because we can already find a final configuration with $n$ sticks in the same direction. Thus, if the final configuration has sticks in both directions, it must have at least $n-k+1$ vertical sticks. Similarly, it must have at least $n-k+1$ horizontal sticks, and thus at least $2(n-k+1)$ sticks in total.

Now, let's find a configuration with $2(n-k+1)$ sticks, for $k < n$. For this, we consider a $(k+1) \times (k+1)$ square at the bottom left of the grid where we place 4 sticks in a square on the border. We then place $n-k-1$ vertical sticks to the right of this square, and $n-k-1$ horizontal sticks above this square.

Now, if $k=n$, we cannot place two sticks in opposite directions, so the answer is $n$. If $k < n$, it is the minimum between $n$ and $2(n-k+1)$, which is $n$ if $2 k-1=n$ and $2(n-k+1)$ otherwise.