Number of square pieces

Question

Sal cuts a square of integer side length into smaller squares of integer side length. For example, she might cut a $4*4$ square into four $1*1$ squares and three $2*2$ squares, making 7 pieces.

A. Draw a diagram to show how Sal can cut a $5*5$ square into 11 square pieces.

I've completed this one. I was just wondering is there a formula or proof to show the relation?

B. Show that Sal can't cut a $4*4$ square into 11 pieces

I've done this by showing all of the possible cuts for a $4*4$ square, however that's not very convenient. Is there some sort of formula/shortcut/proof for it?

C. Sal has 2 $4*4$ squares, 3 $3*3$ squares, 4 $2*2$ squares and 4 $1*1$ squares. Draw a diagram showing how she can place all or some of these squares together without gaps or overlaps to make the largest square possible. Explain why she cannot construct a larger square.

Here is where I'm having problems. This question almost certainly requires the use of proofs, and I'm not very good at those. So is there some proof I can use to make the biggest square possible and why isn't there a bigger square.
Thanks.

Answer 1

Relating to your Question B, one can prove that a configuration of $11$ squares from a $4\times 4$ square is not possible.

From our $4\times 4$ square, we can only cut out $1\times 1$, $2\times 2$, $3\times 3$ and a $4\times 4$ squares. Call the number of squares of each of these sizes $a$, $b$, $c$ and $d$ respectively.

We need to have $a+b+c+d=11\qquad (*)$

However, it is clear that we would need to have $c=d=0$ since if either of these were $1$, then we cannot have $(*)$ being satisfied as we would either have none or not enough other squares to make up $11$ in total. Also, we could obviously not have $c,d\geq 1$ since we are only working with a $4\times 4$ square.

So $(*)$ reduces to $a+b=11$.

Looking at the picture of the $4\times 4$ square you posted, notice that we have $b\in \{1,2,3,4\}$ and further notice that no matter what number for $b$ we choose, there will always then only be an even number of $1\times 1$ squares left.

Further, note that $11$ is an odd number.

Since the sum of an odd and an even is always odd. We are forced to choose an odd number of $2\times 2$ squares to ensure our answer for $(*)$ is also odd. I.e., we must have $b\in \{1,3\}$. Its easy to verify that, by the picture, the sum of $1\times 1$ squares added to the either $1$ or $3$ $2\times 2$ squares can never add up to $11$.

As for Question C, if we add up the number of $1\times 1$ squares that we have available is $2\times 4^2+ 3\times 3^2+ 4\times 2^2+ 4\times 1^2=79$ the next smallest square number from $79$ is $8^2=64$ and the next largest is $9^2=81$.

So the largest square we can hope to construct is a $8\times 8$ square.