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)?
| n | N(n) | S(n) | R(n) |
|---|---|---|---|
| 1 | 1 | 1 | 1 |
| 2 | 0 | 0 | 0 |
| 3 | 0 | 0 | 0 |
| 4 | 1 | 1 | 1 |
| 5 | 0 | 0 | 0 |
| 6 | 1 | 1 | 4 |
| 7 | 1 | 2 | 8 |
| 8 | 2 | 6 | 36 |
| 9 | 4 | 16 | 105 |
| 10 | 7 | 56 | 384 |
| 11 | 18 | 183 | 1340 |
| 12 | 40 | 657 | 4975 |
| 13 | 118 | 2276 | 17668 |
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 R(n) / S(n) → 8 as n→∞.
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.