Prove: Square Can Be Partitioned into n Smaller Squares for n > 14

[CoachZ]

Homework Statement

For n>14 such that n is an integer, prove that a square can be partitioned into n smaller squares...

Homework Equations

None...

The Attempt at a Solution

I was thinking this would be somewhat of an induction proof because we are working our way up to n. So far, I've found when n = 15, n = 17, but somehow n = 16 is eluding me at the moment. I'm just trying to see what it would look like if I were to do this visually, however my assumption is that this has to deal with modulo 3 in some form or another. How this works into a proof is also something that is eluding me. Any suggestions would be warmly welcomed!

 

[CompuChip]

I'm sorry I can't be of much help, but at first sight a proof by induction seems impossible. Because suppose you have shown that if it is possible for n, then it can also be done for n + 1.
Clearly, for n = 4 the statement is true (or even for n = 1, if you want). Also, what do you mean by "partition into smaller squares"? Does that count all squares? For example, when you draw a 3x3 grid in the square, does that give 9 squares? Or does that give 9 (1x1) squares + 4 (2x2) squares = 13 in total?
Also, can you post an image for n = 15, just to get the problem clear?

 

[Architeuthis Dux]

I would approach this problem by first defining some variables and parameters. Let's say the initial square has a side length of s. We can then define n as the number of smaller squares that will partition the initial square. We can also define the side length of each smaller square as x, where x is a fraction of s. This means that x must be a rational number, as it will need to divide evenly into s in order to partition the square.

Next, I would start by looking at some specific values for n, starting with n=15. In this case, we can see that the square can be partitioned into 15 smaller squares by dividing it into a 3x3 grid and then adding a smaller square in each corner, as shown in the figure below.


For n=17, we can use a similar approach, but this time we will have to add two smaller squares in each corner, as shown in the figure below.


Now, as you mentioned, n=16 is a bit trickier. However, we can still apply the same approach and divide the square into a 4x4 grid, as shown in the figure below.


But we are left with a small square in the center that we cannot partition further. This is where the modulo 3 comes into play. We can see that the leftover square has a side length of s/4, which is not a whole number. However, if we divide this square into 9 smaller squares, each with a side length of s/12, we can then add these smaller squares to the corners of our 4x4 grid, as shown in the figure below.


This allows us to partition the square into 16 smaller squares, completing our proof.

In general, we can see that for n>14, we can always use the same approach of dividing the square into a grid and then adding smaller squares in the corners to partition it into n smaller squares. And for