62nd Ukrainian National Mathematical Olympiad, Third Round, First Tour

The example of cutting into $2n=18$ squares is provided in the fig. 10.

Suppose that there exists an example for $n\le 8$. Denote the sides of the squares by $a,b$, and of the large square as $N$. Let's first show that it's possible to represent $N$ as the sum $ka+bl$, where $k,l\le n$, at least in two different ways.

Clearly, at least one such representation has to exist. Let $N=k_{1}a+l_{1}b$, then any vertical/horizontal line, not passing through any side of any square, intersects precisely $k_1$ squares with side $a$ and precisely $k_2$ squares with side $b$.

Choose any $x$ and draw vertical lines on distances $x,x+a,x+2a,\dots$ from the left side of the large square ($x$ has to be such that no such line passes through any side of any of the squares). Each such line will intersect precisely $k_1$ squares with size $a$, so the large square is intersected by precisely $\frac{n}{k_1}$ lines for any choice of $x$, but it's possible only if $N=\frac{n}{k_1}a$. Similarly, $N=a\frac{n}{l_1}$. So, we got two representations of $N$, contradiction.

Now that we know that such $k_2,l_2$ exist, so we get $a(k_1-k_2)=b(l_2-l_1)$, so we can zoom in and let $a=l,b=k$ for some $l,k\le n$. So, from now on, $1\le a,b\le n,a\ne b,a,b,N$ are positive integers, and their largest common divisor $(a,b)=1$.

Write the condition on the area: $n(a^2+b^2)=N^2$.

For $n=3,6,7$ this equation doesn't have a solution: as $n$ has a prime divisor of form $p=4k-1$, we get $N^2\mid p$, so $(a^2+b^2)\mid p$, so $a$ and $b$ are divisible by $p$, but they are coprime.

For $n=1,2$ we can just check all pairs $(a,b)$ which satisfy the conditions above and see that for no of them the value of $n(a^2+b^2)$ is a perfect square.

For $n=4$ the only such pair is $(a,b)=(3,4)$. Then $N=10$, but $10$ can be represented as $3a+4b$ in a unique way, so it's wrong.

For $n=5$ the only such pair is $(a,b)=(1,2)$, then $N=5$, but from the square $5\times 5$ we can't cut out $5$ squares $2\times 2$, as each of them contains at least one of the cells $(2,2),(2,4),(4,2),(4,4)$.

For $n=8$ the only such pair – $(1,7)$, then $N=20$, but from the square $20\times 20$ we can't cut out $8$ squares $7\times 7$, as each of them contains at least one of the cells $(7,7),(7,14),(14,7),(14,14)$.