4
$\begingroup$

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?

$\endgroup$
10
  • 1
    $\begingroup$ @LordSharktheUnknown The actual question is whether we can make an 8*8 square with the pieces explained in the given thread Question C. If yes, show how. If not, prove why. $\endgroup$
    – bio
    Commented May 13, 2017 at 12:30
  • 1
    $\begingroup$ Why don't you edit your question to incorporate the list of pieces? That would help your readers. $\endgroup$ Commented May 13, 2017 at 12:32
  • 2
    $\begingroup$ You would have to use both order 4 squares and (at least) two of the order 3 squares. Can you show that no matter where you place those four squares, you can fill in the rest with the other pieces? $\endgroup$ Commented May 13, 2017 at 12:44
  • 1
    $\begingroup$ @bio: It appears there's no paradox. Could you please edit the title to be more descriptive? (Perhaps "Covering an $8 \times 8$ square with non-overlapping smaller squares".) $\endgroup$ Commented May 13, 2017 at 14:17
  • 1
    $\begingroup$ I can write the complete proof of non-existence, but it's going to be very messy $\endgroup$ Commented May 13, 2017 at 14:55

1 Answer 1

4
$\begingroup$

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.

  1. 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".

  2. 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.

  3. 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.

  4. There are not enough squares remain to fulfill requirement in $[2]$ for every horizontal line.

$\endgroup$
6
  • $\begingroup$ When you introduce form 8, you know that you can use 2 4*4, 3 3*3, 4 2*2 and 4 1*1. Sorry if that's what you used but I don't really understand that bit $\endgroup$
    – bio
    Commented May 14, 2017 at 9:13
  • $\begingroup$ @bio You can use "up to" that many squares, it doesn't mean you need to use all of them. In fact, if you add up the area of all the squares you can use, you get $2*4^2+3*3^2+4*2^2+4*1^2=79$. This is bigger than $8^2 = 64$. It is impossible to use all the given squares to build a $8\times 8$ square without overlap. If one use $a$ copies of $4*4$ squares, $b$ copies of $3*3$ squares, $c$ copies of $2*2$ squares and $d$ copies to $1*1$ squares with $a\le 2, b, \le 3, c, d\le 4$, there are only two possible combinations $(a,b,c,d) = (2,2,3,2)$ or $(2,3,1,1)$ which have the desired area $64$. $\endgroup$ Commented May 14, 2017 at 10:14
  • $\begingroup$ I don't understand all the symbols ( I'm only Year 7) $\endgroup$
    – bio
    Commented May 14, 2017 at 11:45
  • $\begingroup$ @bio in that case, it seems impossible to explain all the symbols. As a last ditch of effort, I have written down the key assertions I claim. Do you understand what I'm trying to show (even if you can't follow the details)? $\endgroup$ Commented May 14, 2017 at 12:52
  • $\begingroup$ What does disjoint mean? $\endgroup$
    – bio
    Commented May 16, 2017 at 9:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .