58th Ukrainian National Mathematical Olympiad

For both a) and b) it is obvious that $n$ has to be odd and greater than $k$.

a) Hence, $n$ is odd and greater than $4$. Let us show that any such odd $n$ satisfies the condition. It is clear that any stripe $4\times l$ can be covered by rectangles $4\times 1$. For $5\times 5$ and $7\times 7$ the required coverage is shown on Fig. 7–8. For any odd $n=4m+5$ and $n=4m+7$ it is sufficient to cut the square $n\times n$ into a square $5\times 5$ or $7\times 7$ and several stripes $4\times l$ (Fig. 9).

Fig. 9

b) Let us show that by a similar scheme we can cover squares $n=8m+9$ and $n=8m+15$. For this, it is sufficient to cover $9\times 9$ and $15\times 15$. Then, each $n\times n$ of the above size can be cut into a square $9\times 9$ or $15\times 15$ and several stripes $8\times l$ (Fig. 10–11).

Now, let us show that squares $n=8m+11$ and $n=8m+13$ cannot be covered according to the condition. For the square $11\times 11$, consider this coloring in black and white squares, as shown in Fig. 12. Out of $121$ squares, $65$ are black and $56$ are white, which means there are $9$ more black cells than white ones. Each rectangle $8\times 1$ inside of this square covers the same number of black and white cells. Therefore, if there existed such coverage, the number of black and white cells would differ only by $1$. For the general case square $n\times n$ when $n=8m+11$, analogous coloring yields $9$ more black cells than white cells.

Fig. 10

Analogously, for square $13\times 13$, we show the coloring (Fig. 13) with $89$ black and $80$ white cells, which again means there is no such coverage. And for the case $n\times n$ when $n=8m+13$, the same holds.