What is the minimum square partition of an almost-square rectangle?
A similar question was asked on Mathoverflow. The commenters mentioned a paper of Kenyon, which shows that the minimum number of squares required to tile a $w \times (w-1)$ rectangle is $\Theta(\log w)$. See also a related paper of Walters.



You can tile a $(4t+7) \times (4t+6)$ rectangle using only $t+5$ squares (for $t \geq 0$).