Cut a 13×13 square into the minimum number of smaller squares,
all sides being integer.
If the smaller squares are all different, this problem is known as perfect tiling.
The smallest square allowing a perfect tiling is 110×110
If some smaller squares may be equal, the tiling is said imperfect.
The problem is also known as "Mrs Perkins' quilt", from the name choosen by H.E. Dudeney in his book "Amusements in Mathematics", although it seems he has taken the problem from Sam Loyd.
This example shows a minimal imperfect tiling of the 21×21 square.
Consider the 2n×2n square. An obvious tiling is in four n×n squares.
In the same way, the 9×9 square could be tiled by nine 3×3 squares.
To keep the interest of this problem for any n, the sides of the smaller squares are required to be globally coprime, that is the GCD of sides is 1. (and the 21×21 square is then not tiled by nine 7×7 squares !)
With this constraint, a 4×4 square is tiled by a minimum of 7 pieces. How ?
How many pieces are needed to tile a 9×9 square ?
Deduce a minimal tiling of the 13×13 square from the tilings of smaller squares.