Problem of the Month (September 2001)

In how many ways can we cut a square into n smaller squares?

Let R(n) denote the number of ways to cut a square into n squares (where reflections and rotations count as different), and let S(n) be the number of ways up to symmetry (where reflections and rotations do not count as different).

What are the values of R(n) and S(n) for small values of n? Are R(n) and S(n) eventually increasing? Do R(n) and S(n) grow exponentially? What else can you prove about R(n) and S(n)?

If we define N(n) to be the number of different collections of n squares that can be arranged in a square, then what can you say about N(n)?


ANSWERS

Joseph DeVincentis and Berend Jan van der Zwaag wrote computer programs that calculated N(n), S(n), and R(n) for n ≤ 13. Their results are show below:

nN(n)S(n)R(n)
1111
2000
3000
4111
5000
6114
7128
82636
9416105
10756384
11181831340
12406574975
13118227617668
Here are some pictures for n ≤ 9.

Berend Jan van der Zwaag proved several inequalities for R(n) and S(n) for larger values of n. For example, S(n+3) ≥ R(n)/2 since we can cut a square into 4 subsquares and replace one subsquare with any instance counted in R(n). The factor of 1/2 is because the result might have diagonal symmetry through the centers. Similarly, R(n+3) ≥ 4 R(n). This shows that R(n) grows exponentially. He notes that there are many other inequalities by replacing any square in any tiling with a tiling of subsquares.

Berend Jan van der Zwaag notes that any tiling has between 1 and 8 symmetries, so S(n) ≥ R(n) ≥ 8 S(n). This shows that S(n) grows exponentially as well. He also makes the conjecture that limn→∞R(n) / S(n) = 8.

Berend Jan van der Zwaag asked whether there is any tiling of a square by squares so that the squares can not be rearranged so that the largest square is in a corner. Then he found the smallest such example, shown below:

If you can extend any of these results, please e-mail me. Click here to go back to Math Magic. Last updated 10/9/01.