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. \quad (*)$$
We will also show that
$$a \to x \Rightarrow 2a-1 \to 2x+2. \quad (**)$$
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.