APMO

Set aside the squares with sidelengths $n-3,n-2,n-1$, and $n$ and suppose we can split the remaining squares into two sets $A$ and $B$ such that the sum of the sidelengths of the squares in $A$ is 1 or 2 units larger than the sum of the sidelengths of the squares in $B$. String the squares of each set $A,B$ along two parallel diagonals, one for each diagonal. Now use the four largest squares along two perpendicular diagonals to finish the construction: one will have sidelengths $n$ and $n-3$, and the other, sidelengths $n-1$ and $n-2$. If the sum of the sidelengths of the squares in $A$ is 1 unit larger than the sum of the sidelengths of the squares in $B$, attach the squares with sidelengths $n-3$ and $n-1$ to the $A$-diagonal, and the other two squares to the $B$-diagonal. The resulting configuration, in which the $A$ and $B$-diagonals are represented by unit squares, and the sidelengths $a_i$ of squares from $A$ and $b_j$ of squares from $B$ are indicated within each square, follows:



Since $\left(a_1+a_2+\cdots +a_k\right)\sqrt{2}+\frac{((n-3)+(n-2))\sqrt{2}}{2}=\left(b_1+b_2+\cdots +b_{\ell }+2\right)\sqrt{2}+\frac{(n+(n-1))\sqrt{2}}{2}$, this case is done. If the sum of the sidelengths of the squares in $A$ is 1 unit larger than the sum of the sidelengths of the squares in $B$, attach the squares with sidelengths $n-3$ and $n-2$ to the $A$-diagonal, and the other two squares to the $B$-diagonal. The resulting configuration follows:



Since $\left(a_1+a_2+\cdots +a_k\right)\sqrt{2}+\frac{((n-3)+(n-1))\sqrt{2}}{2}=\left(b_1+b_2+\cdots +b_{\ell }+1\right)\sqrt{2}+\frac{(n+(n-2))\sqrt{2}}{2}$, this case is also done. In both cases, the distance between the $A$-diagonal and the $B$-diagonal is $\frac{((n-3)+n)\sqrt{2}}{2}=\frac{(2n-3)\sqrt{2}}{2}$. Since $a_i,b_j\le n-4,\frac{\left(a_i+b_j\right)\sqrt{2}}{2}<\frac{(2n-4)\sqrt{2}}{2}<\frac{(2n-3)\sqrt{2}}{2}$, and therefore the $A$ - and $B$-diagonals do not overlap. Finally, we prove that it is possible to split the squares of sidelengths 1 to $n-4$ into two sets $A$ and $B$ such that the sum of the sidelengths of the squares in $A$ is 1 or 2 units larger than the sum of the sidelengths of the squares in $B$. One can do that in several ways; we present two possibilities: - Direct construction: Split the numbers from 1 to $n-4$ into several sets of four consecutive numbers $\{t,t+1,t+2,t+3\}$, beginning with the largest numbers; put squares of sidelengths $t$ and $t+3$ in $A$ and squares of sidelengths $t+1$ and $t+2$ in $B$. Notice that $t+(t+3)=(t+1)+(t+2)$. In the end, at most four numbers remain. - If only 1 remains, put the corresponding square in $A$, so the sum of the sidelengths of the squares in $A$ is one unit larger that those in $B$; - If 1 and 2 remains, put the square of sidelength 2 in $A$ and the square of sidelength 1 in $B$ (the difference is 1 ); - If 1,2 , and 3 remains, put the squares of sidelengths 1 and 3 in $A$, and the square of sidelength 2 in $B$ (the difference is 2 ); - If $1,2,3$, and 4 remains, put the squares of sidelengths 2 and 4 in $A$, and the squares of sidelengths 1 and 3 in $B$ (the difference is 2 ). - Indirect construction: Starting with $A$ and $B$ as empty sets, add the squares of sidelengths $n-4,n-3,\dots ,2$ to either $A$ or $B$ in that order such that at each stage the difference between the sum of the sidelengths in $A$ and the sum of the sidelengths of B is minimized. By induction it is clear that after adding an integer $j$ to one of the sets, this difference is at most $j$. In particular, the difference is 0,1 or 2 at the end. Finally adding the final 1 to one of the sets can ensure that the final difference is 1 or 2 . If necessary, flip $A$ and $B$.

---

Alternative solution.

Solve the problem by induction in $n$. Construct examples for $n=5,6,7,8,9,10$ (one can use the constructions from the previous solution, for instance). For $n>10$, set aside the six larger squares and arrange them in the following fashion:



By the induction hypothesis, one can arrange the remaining $n-6$ squares away from the six larger squares, so we are done.