51st Ukrainian National Mathematical Olympiad, 4th Round

We will write $a\to x$, if an $a\times a$ square without one corner cell can be cut along the lines of the grid into $x$ squares.

Evidently, $2\to 3$. Also note that $7\to 8$ and $9\to 9$ (fig. 24 and 25). We will show that if $a\to x$ and $b\to y$, then $ab\to x+y$. Indeed, a square with the side length $ab$ without a corner cell can be cut into two parts: a square with the side length $b$ without a corner cell, and a square with the side length $ab$, with a $b\times b$ square removed from its corner. The first part can be cut into $y$ squares, and the second part can be cut into $x$ squares, since it is a square with the side length $a$ without a corner, magnified by a factor of $b$. So, $$a\to x\Rightarrow 2a\to x+3.(\ast )$$ We will also show that $$a\to x\Rightarrow 2a-1\to 2x+2.(\ast \ast )$$ Indeed, an "incomplete" square can be partitioned into 2 squares with the side length $a-1$ and 2 "incomplete" squares with the side length $a$ (fig. 26). So: $7\to 8$, $9\to 9$, $63\to 17$, $126\to 20$, $252\to 23$, $503\to 48$, $1006\to 51$, $2011\to 104$, i.e., we have shown that our original figure can be cut into $104<121$ squares.