Number of square pieces, Question C
Sal has two $4\times 4$ squares, three $3\times 3$ squares, four $2\times 2$ squares and four $1\times 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.
I came across the fact that I couldn't work out how to make an $8\times8$ square. In theory, I should be able to make one, as the area of all of the squares combined is $79$ unit squares, and by taking away a few squares, I should be able to get a $8\times8$ square, however everyone seems to be forgetting that you can't change the shape of a square in order to get it to fill a gap.
So, can we really make an $8\times8$ square, and if no, prove why.
Also, if we can't make a $8\times8$ square, how can we make a $7\times7$ square?
It is impossible to cover an $8 \times 8$ square by given squares
For any integer $n > 1$, let $\fbox{n}$ be the shorthand for a $n \times n$ square. For any $a, b, c, d \in \mathbb{N}$, we will use expression of the form $\fbox{8} = a\,\fbox{4} + b\,\fbox{3} + c\,\fbox{2} + d\,\fbox{1}$ to denote the possibility of covering a $8\times 8$ square by $a$ copies of $\fbox{4}$, $b$ copies of $\fbox{3}$, $c$ copies of $\fbox{2}$ and $d$ copies of $\fbox{1}$ without gap nor overlap.
The total area of available squares is $2\cdot 4^2 + 3\cdot 3^2 + 4\cdot 2^2 + 1\cdot 1^2 = 79$. If one can cover $\fbox{8}$ as $a\,\fbox{4} + b\,\fbox{3} + c\,\fbox{2} + d\,\fbox{1}$, the area of unused squares will be $$(2-a)4^2 + (3-b)3^2 + (4-c)2^2 + (4-d)1^2 = 79-8^2 = 15$$
This tell us $$0 \le 2 - a \le 0 \implies a = 2\quad\text{ and }\quad 0 \le 3 - b \le 1 \implies b = 2\text{ or }3$$
To satisfy $0 \le c \le 4$ and $0 \le d \le 4$, there are two and only two possibilities:
$$\fbox{8} = 2\,\fbox{4} + 2\,\fbox{3} + 3\,\fbox{2} + 2\,\fbox{1} \quad\text{ or }\quad \fbox{8} = 2\,\fbox{4} + 3\,\fbox{3} + 1\,\fbox{2} + 1\,\fbox{1} $$
Consider the scenario $\fbox{8} = 2\,\fbox{4} + 2\,\fbox{3} + 3\,\fbox{2} + 2\,\fbox{1}$ first.
Let $T_1$, $T_2$ be the two $\fbox{3}$ and $O_1$, $O_2$ be the two $\fbox{1}$. Divide $\fbox{8}$ into $8$ rows $R = \{ r_1, \ldots, r_8 \}$ and $8$ columns $C = \{ c_1, \ldots, c_8 \}$. Consider following sets of rows and columns $$\begin{align} R_1 &= \{ r \in R : r \cap T_1 \ne \emptyset \}\\ R_2 &= \{ r \in R : r \cap T_2 \ne \emptyset \}\\ C_1 &= \{ c \in C : c \cap T_1 \ne \emptyset \}\\ C_2 &= \{ c \in C : c \cap T_2 \ne \emptyset \}\\ \end{align} $$ Since $T_1$ doesn't overlap with $T_2$, it is impossible for $R_1 \cap R_2 \ne \emptyset$ and $C_1 \cap C_2 \ne \emptyset$ to be true at the same time. So at least one of these two intersections of pair of rows or pair of columns is empty. Let's say $R_1 \cap R_2 = \emptyset$, there will be $6$ rows in $R_1 \cup R_2$. Let $r$ be one of these rows. Since the side length of a $\fbox{8}$ is even while that of $\fbox{3}$ and $\fbox{1}$ are odd, $r$ need to intersect with an even number of $\fbox{3}$ or $\fbox{1}$. This means $r$ intersect one of $O_1$ or $O_2$. Now we have $6$ rows, there are not enough $\fbox{1}$ remain to intersect all of them. This rule out the possibility $\fbox{8} = 2\,\fbox{4} + 2\,\fbox{3} + 3\,\fbox{2} + 2\,\fbox{1}$.
For the other scenario, $\fbox{8} = 2\,\fbox{4} + 3\,\fbox{3} + 1\,\fbox{2} + 1\,\fbox{1}$, the argument is similar. Let $T_1, T_2, T_3$ be the three $\fbox{3}$ and $O_1$ be the one $\fbox{1}$. Once you pick the $6$ rows (or columns) intersecting with $T_1$ and $T_2$, you are left with one $\fbox{3}$ and one $\fbox{1}$ to intersect with them. Since $T_3$ and $O_1$ together can only handle at most $4$ out these $6$ rows (or columns). The scenario $\fbox{8} = 2\,\fbox{4} + 3\,\fbox{3} + 1\,\fbox{2} + 1\,\fbox{1}$ is also impossible.
Update
For benefit of those who can't follow the symbols, following are the key assertions I make. I hope this will clarify the ideas behind this approach.
By consideration of area only, there are at most two ways of picking squares to cover the $8\times 8$ square. It involves either "two $4\times 4$, two $3 \times 3$, three $2\times 2$, one $1\times 1$ squares" or "two $4 \times 4$, three $3 \times 3$, one $2 \times 2$, one $1 \times 1$ squares".
In both cases, pick two $3 \times 3$ squares and project them onto the $x$-axis and onto the $y$-axis. Under at these one of these projections, the "shadow" of those two squares will be disjoint.
Let's say the projections on $y$-axis are disjoint. If one draw a horizontal line which intersect one of these two $3 \times 3$ squares, that line has to intersect one of the remaining $3\times 3$ or $1 \times 1$ squares.
There are not enough squares remain to fulfill requirement in $[2]$ for every horizontal line.