Clearly, a square can be partitioned into four smaller non-overlapping squares with two lines through its center and parallel to its sides. Trivially, a square can be partitioned into one square with no lines.

Question: For which integers n > 0 can a square be partitioned into n non-overlapping squares (not necessarily the same size)?

Any square can be partitioned into four as explained in the problem.  This means any solution for n is a solution for n+3.

The smallest n=1 (mod 3) is 1
The smallest n=2 (mod 3) is 8
[partition a 4x4 square into a 3x3 and 7 1x1s]
The smallest n=0 (mod 3) is 6.
[partition a 3x3 square into a 2x2 and 5 1x1s]

This leaves the only non-partition numbers as 2, 3, 5.

Now to prove these number cant be done.
The four corners of the original square must end up corners of the partitioned square.  With n=2 or n=3, at least two corners must end up in the same square.  This can only happen if this square of the partition is the size of the original square, which leaves no room for the other squares.

With n=5, the first 4 squares of the partition each must fill a corner.  These squares either abut or leave a gap.  Any gap must be filled by the last square, so there can be only one gap and the other 3 must be abutments. 
If the first two abutting squares are the same size then for the third to abut it must also be the same size.  This leaves a square for the last two to partition but n=2 is impossible.
If the first two square are different sizes, the third must abut the larger, and the fourth cannot abut either of its neighbors so there would be two gaps.

Edited on March 16, 2011, 10:29 am

Posted by Jer on 2011-03-16 09:16:12