National Olympiad Final Round

A partition of a square into 1 square is trivial. If $n\ge 2$ then a partition into $2n$ squares can be obtained by cutting $n$ squares of side length $\frac{1}{n}$ from one side of the square and $n-1$ more squares of the same size from a neighbouring side. One square of side length $\frac{n-1}{n}$ of the side length of the big square is left (Fig. 14 depicts the situation in the case $n=4$ that provides a partition into 8 squares). For each $n\ge 2$, one can obtain a partition into $2n+3$ squares by splitting one square in a partition into $2n$ squares into four. Thus there exist partitions into 1, 4 and every natural number starting from 6.

Fig. 14

It remains to show that there are no partitions of a square into 2, 3 and 5 squares. A square has 4 vertices and each vertex belongs to only one square in a partition. If two vertices belonged to the same square in the partition, this piece should be as large as the initial square, which is possible only in partition into 1. Hence the number of squares in a partition into a larger number of squares must be at least 4. In a hypothetical partition into 5 squares, at least three sides of the initial square should adjoin exactly 2 squares in the partition. Let the initial square be $ABCD$ and let the sides $DA,AB$ and $BC$ adjoin exactly 2 squares in the partition. Let the squares adjoining the side $AB$ have side lengths $x$ and $y$ in the order from vertex $A$ to vertex $B$. The square of side length $x$ is adjoining also the side $AD$ and the square of side length $y$ is adjoining the side $BC$, whence the other squares adjoining the sides $AD$ and $BC$ have side lengths $y$ and $x$, respectively. If $x>y$ then the squares located by vertices $A$ and $C$ would overlap (Fig. 15). If $x<y$ then the squares located by vertices $B$ and $D$ would overlap. If $x=y$, four squares in the partition would cover the whole initial square and the fifth square cannot exist.

Fig. 15