Berkeley Math Circle Monthly Contest 3

Solution:
One can cut a square into $n$ smaller squares for all $n \geq 6$. Here is how.
For $n=4$

For $n=6$

For $n=8$

Suppose we know how to cut a square into $n$ smaller squares. If we take one of the square "pieces" and cut it onto four smaller squares (as in the picture above for $n=4$). Now we have cut our original square into $n+3$ pieces. Since we know how to cut a square into 4 pieces, we can cut it into $7,10, \ldots, 3k+1, \ldots$ pieces. Similarly, starting with 6 pieces we can get $6,9, \ldots, 3k, \ldots$ pieces, and from 8 pieces $8,11, \ldots, 3k+2, \ldots$ pieces. Hence we can get any number of pieces bigger or equal to 6.