Side length of the smallest square that can be dissected into $n$ squares with integer sides

Let $s_n$ be the shortest possible side length of a square constructed from exactly $n$ squares of positive integer side lengths. If no such square exists, let $s_n = 0$.

The first few values are as follows:

 n | s(n)
---+------
 1 |  1
 2 |  0
 3 |  0
 4 |  2
 5 |  0
 6 |  3
 7 |  4
 8 |  4
 9 |  3
10 |  4
11 |  5
12 |  6
13 |  4
14 |  5

If we search this Integer Sequence in an Online Encyclopedia, something very remarkable happens: there is exactly one search hit. That sequence is A300001, or in English, "Side length of the smallest equilateral triangle that can be dissected into n equilateral triangles with integer sides, or 0 if no such triangle exists."

Do my square sequence's values agree with the triangle sequence's values?

If so, why? If not, when do they first disagree?

At first I thought, maybe there's some manner of bijection between my square dissections and the triangular dissections: if you halve each subsquare along its diagonals, numerically the result should fit in the entire square halved along its own diagonal. But fitting them together requires some nonobvious geometrical fiddling, and I'm not at all confident this subobject-size-preserving bijection is well defined over all dissections. Is it?

Solution 1:

Do my square sequence's values agree with the triangle sequence's values?

Yes, the two sequences are the same. (Ross Millikan has the right idea.) In fact, we will prove an explicit formula for both sequences.

Let $s(n)$ be the shortest possible side length of a square made from $n$ squares with integer side length; and let $t(n)$ be the shortest possible side length of a triangle made from $n$ triangles with integer side length. (And $s(n) = 0$ or $t(n) = 0$ if no such thing exists.)

Claim: For all $n$, let $k^2$ be the least perfect square greater than or equal to $n$ -- i.e., $k = \lceil \sqrt{n} \rceil$. Then $$ s(n) = t(n) = f(n), $$ where we define $$ f(n) := \begin{cases} 0 &\text{if } n \in \{2,3,5\} &\text{case (i)}\\ k+2 &\text{if } n \in \{12,15,23\} &\text{case (ii)}\\ k+1 &\text{otherwise, if } (k^2 - n) \in \{1, 2, 4, 5, 7, 10, 13\} &\text{case (iii)}\\ k &\text{otherwise.} &\text{case (iv)} \end{cases} $$

Proof strategy: First, we will show that $f(n)$ is a lower bound on both $t(n)$ and $s(n)$, by showing that no set of $n$ perfect-square areas can add up to a perfect-square area of size any less than $f(n)$. Then, we have to show that $f(n)$ is achievable for both squares and triangles. This is the hard part. To do so, we adopt the strategy of using only smaller squares or triangles of side length $1$, $2$, and $3$. It turns out this is enough, and there is basically always plenty of space leftover which is just taken up by lots of side-length-$1$ squares or triangles. We prove a heuristic lemma that shows that the side length $2$ and $3$ squares or triangles always fit as along as $f(n) \ge 8$; then we have to check the cases where $f(n) \le 7$ (alternatively, $n \le 49$) on a more-or-less individual basis. Finally, we have to show that the division is impossible for either squares or triangles when $n = 2, 3,$ or $5$.

Part 1: $f(n)$ is a lower bound on $s(n)$ and $t(n)$

Note that $s(n) \ge k$ and $t(n) \ge k$, because we need at least a $k \times k$ square just to fit $n$ $1 \times 1$ squares (by area). Similarly for triangles. (In particular, $s(n)^2 \ge n$ and $t(n)^2 \ge n$ for all $n$, unless they are zero.) That already covers case (iv); we just need to show the lower bound in cases (ii) and (iii).

Now if we define $r = s(n)$ or $r = t(n)$, then $r^2$ is the area of the larger square (or triangle) in units of side-length $1$ squares (or triangles). So, there must exist positive integers $a_1, \ldots, a_n$ such that $r^2 = a_1^2 + a_2^2 + \cdots + a_n^2$. Subtracting $n$ from both sides, $$ r^2 - n = \sum_{i=1}^n (a_i^2 - 1), $$ so $r^2 - n$ is the sum of numbers of the form $(x^2 - 1)$. Such numbers are $0, 3, 8, 15, \ldots$. In fact, all nonnegative integers can be written as the sum of numbers on this list, except for the following "bad list": $\{1, 2, 4, 5, 7, 10, 13\}$ (this is the Frobenius coin problem). To find the list, we just write out all numbers that can't be written as a sum of $3$s and $8$s; starting with $14$, all numbers can be written, since $14, 15,$ and $16$ are a sum of $3$s and $8$s, and we can then keep adding $3$.

Therefore, $r^2 - n$ must not be on the bad list of numbers, $1, 2, 4, 5, 7, 10,$ or $13$. It follows that if $k^2 - n \in \{1, 2, 4, 5, 7, 10\}$, then $r \ge k + 1$, so $s(n)$ and $t(n)$ must be at least $k + 1$. This proves that $f(n)$ is a lower bound in case (iii).

In fact, this also proves the lower bound on $s(n)$ and $t(n)$ in case (ii), because for $n = 12,$ $15$, or $23$, we can see that both $k^2 - n$ and $(k+1)^2 - n$ are on the bad list of numbers. In particular, $16 - 12 = 4$ and $25 - 12 = 13$; $16 - 15 = 1$ and $25 - 15 = 10$; $25 - 23 = 2$ and $36 - 23 = 13$.

Part 2: Achievability -- $s(n) = t(n) = f(n)$ for cases (ii), (iii), and (iv)

We need to show that for $n \ne 2, 3, 5$, it is possible to divide a square (or triangle) of side length $n$ into $f(n)$ squares (or triangles) of integer side length. Let $r = f(n)$. We will use some basic bounds on $n, k,$ and $r$: $k \le r \le k + 2$, and $(k-1)^2 < n \le k^2$.

By definition of $r = f(n)$ (see part 1), $r^2 - n$ is not on the bad list of numbers ($1, 2, 4, 5, 7, 10, 13$). Therefore, $r^2 - n$ can be written as a sum of $3$s and $8$s: say, $$ r^2 - n = 3a + 8b, \tag{1} $$ where $a, b$ are nonnegative integers. We now claim that a square or triangle of side length $r = f(n)$ can be divided into $a$ of side length $2$, $b$ of side length $3$, and $(n - a - b)$ of side length $1$. (Thus there are $n$ total, and the total area is $4a + 9b + (n - a - b) = f(n)^2$.) For this to work, we should also show $a + b \le n$.

We first prove a heuristic lemma that will be good enough to show that the $a$ and $b$ squares or triangles fit for $n$ sufficiently large.

Lemma. Let $a, b \ge 0$ and $r \ge 2$ be integers such that $4a + 9b \le (r-2)^2 + 3$. Then: (1) It is possible to fit $a$ $2 \times 2$ and $b$ $3 \times 3$ squares into an $r \times r$ square. (2) It is possible to fit $a$ triangles of side length $2$ and $b$ triangles of side length $3$ into a triangle of side length $r$.

Proof of lemma (sadly without pictures to help):

1. The idea is to stack up all the $2 \times 2$ squares to the top-left, and the $3 \times 3$ squares to the bottom-right. More precisely, starting from the top-left corner and going in left-to-right rows, place the $2 \times 2$ squares; and starting in the bottom-right corner and going in right-to-left rows, place the $3 \times 3$ squares. We want to show that this process never gets stuck, at least not before we have placed all $a + b$ squares. So suppose we have not placed all the squares, and we get stuck. Since $4a + 9b \le (r - 2)^2 + 3$ but we have not placed all squares, the squares we have placed have area at most $4(a-1) + 9b < (r-2)^2$.

   The question is, what does a "stuck" position look like? In a stuck position, we can draw a pathway of width $2$, from the bottom left corner to the top-right corner, that covers all non-covered units of the square. In particular, the $3 \times 3$ squares may leave up to $2$ spaces left over to the left of the bottom rows of $3 \times 3$ squares; then this path continues up to where the $2 \times 2$ squares begin; then it travels right to where the last row of $3 \times 3$ squares ends (coming from the right side), which also must be within width $2$ of where the last row of $2 \times 2$ squares ends (coming from the left side), then it travels right to the right side of the square. Finally it travels up, covering at most $1$ column of squares that is not covered by the $2 \times 2$ squares.

   Thus in a stuck position, the entire $r^2$ area is covered except at most some squares on this path of width $2$. This path covers exactly $4r - 4$ squares. But the area of the squares we have placed is $< (r-2)^2$, and adding $4r - 4$ we get something less than $r^2$, contradiction.

2. Now we do the triangle case; it is similar but more confusing. Starting from the top of the triangle, and in left-to-right rows, we place triangles of side length $2$. Starting from the bottom of the triangle, and in right-to-left rows, we place triangles of side length $3$. We want to show, once again, that this process does not get stuck. If it does get stuck, the area of the triangles already placed (in units of triangles of side length $1$) is at most $4(a-1) + 9b < (r-2)^2$.

   What does a stuck position look like for the triangle? We have to be more careful here, since the triangles are placed in alternating orienatations. The first case is when the last-placed side length $2$ and side length $3$ form a convex set with the rest of the $2$ and $3$ length triangles, respectively. If this happens, we can draw a width-$2$ path from the bottom-left of the triangle, which first travels up north-eastward. Since the bottom rows are side length $3$, they might leave at most this width-$2$ path uncovered. Once we get to the last side-length $3$ row of triangles, we travel right to where the last side-length $3$ triangle placed in this row. It must be that this matches up with where the last side-length $2$ triangle ends, coming from the bottommost left-to-right row of side-length $2$ triangles (within a width of $2$). We continue north-east for one or two units, then then to the right. The path ends somewhere on the right side of the triangle.

   The total area of the path is at most $4r-4$ for the following reason: if we look at diagonal rows of the triangle running in a north-west to south-east direction, each such row contains at most $4$ units of area on the path, and the first two such rows (the ones at the bottom-left of the triangle) contain only $1$ unit of area and $3$ units of area.

   Now we consider when one or both of the last-placed triangles (side length $2$ coming from the top-left, or side length $3$ coming from the bottom-right) is not convex with the other triangles. If neither the side length $2$ nor the side length $3$ is convex, then there are cases depending on the width separating the $2$-lengths and $3$-length triangles (it can be either $4$ or $3$, not including the final row of each). In either case, the number of units of area on the "path" (i.e. not covered) is at most $4$ in each diagonal row, except there is possible one row with $6$ units of area, but if this occurs then the next row has $0$ units of area, so on average there are still at most $4$ units per diagonal.

   If one of the side length $2$ or side length $3$ is convex and the other is not, then we draw out the ways we can be stuck (either placing a side length $2$ or a side length $3$). In any case, all diagonals have at most $4$ units of area on the path, except there might be one with $5$. But if this occurs, then the next diagonal after it has only $1$ unit of area.

   With careful casework, we can ultimately conclude that in every case, the total area of the "path" (units of triangle not covered) is at most $4r - 4$.

   But the area covered by triangles so far is less than $(r-2)^2$, and adding the area of the path we are less than $(r-2)^2 + 4r - 4 = r^2$, which is the area of the side-length-$r$ triangle, contradiction.

Now that we have the lemma, we apply it. Assume that $r = f(n) \ge 8$. In particular, $n$ is at least $24$, so case (ii) does not apply. We have $r \le k + 1 \le (\sqrt{n} + 1) + 1$, thus $$ n \ge (r - 2)^2. $$ Then from equation (1), $$ 3a + 8b = r^2 - n \le r^2 - (r-2)^2 = 4r - 4. $$ Multiplying by $\frac{4}{3}$, we get $$ 4a + 9b \le \frac{4}{3} (3a + 8b) \le \frac{16}{3}(r-1). $$ Finally, we're interested in when this bound is enough to apply the lemma. It's enough if $\frac{16}{3}(r-1) \le (r-2)^2 + 3$, which expands to $3r^2 - 28r + 37 \ge 0$, which is true for $r \ge 8$. So we apply the lemma and we're done.

What remains is the case where $r = f(n) \le 7$. In particular, for such cases, $n$ is at most $7^2 = 49$. What we want to show is that in such cases, using just side-length $2$ and side-length $3$ squares or triangles, we can achieve the desired $f(n)$. First we make a table of $f(n)$: $$ \begin{array}{cc|cc|cc|cc|cc|cc|cc} n & f(n) & n & f(n) & n & f(n) & n & f(n) & n & f(n) & n & f(n) & n & f(n) \\ \hline 1 & 1 & 2 & 0 & 5 & 0 & 10 & 4 & 17 & 5 & 26 & 7 & 37 & 7 \\ & & 3 & 0 & 6 & 3 & 11 & 5 & 18 & 6 & 27 & 6 & 38 & 7 \\ & & 4 & 2 & 7 & 4 & 12 & 6 & 19 & 5 & 28 & 6 & 39 & 8 \\ & & & & 8 & 4 & 13 & 4 & 20 & 6 & 29 & 7 & 40 & 7 \\ & & & & 9 & 3 & 14 & 5 & 21 & 6 & 30 & 6 & 41 & 7 \\ & & & & & & 15 & 6 & 22 & 5 & 31 & 7 & 42 & 8 \\ & & & & & & 16 & 4 & 23 & 7 & 32 & 7 & 43 & 7 \\ & & & & & & & & 24 & 6 & 33 & 6 & 44 & 8 \\ & & & & & & & & 25 & 5 & 34 & 7 & 45 & 8 \\ & & & & & & & & & & 35 & 7 & 46 & 7 \\ & & & & & & & & & & 36 & 6 & 47 & 8 \\ & & & & & & & & & & & & 48 & 8 \\ & & & & & & & & & & & & 49 & 7 \\ \end{array} $$

• First, consider the trivial cases $r = 1$, $r = 2$, and $r = 3$. $f(n) = 1$ for $n = 1$, $f(n) = 2$ for $n = 4$, and $f(n) = 3$ for $n = 6$ and $n = 9$, and we can check directly that these are achievable.

• For $f(n) = r = 4$, the possible $n$ are $7,8,10,13,$ and $16$. Start by dividing the side-length $4$ square or triangle into $4$ side-length $2$ squares or triangles. Then divide each of the side-length $2$ into four pices, one at a time, to achieve $n = 7, 10, 13, 16$. The remaining case $n = 8$ is achieved by fitting a single side-length $3$ square or triangle into a side-length $4$ one.

• For $f(n) = r = 5$, the possible $n$ are $11, 14, 17, 19, 22, 25$. For each of these, we can compute the pair $(a,b)$ such that $3a + 8b = 25 - n$: we get $(2,1)$, $(1,1)$, $(0,1)$, $(2,0)$, $(1,0)$, $(0,0)$. So we just have to show that, inside a square or triangle of size $5$, we can fit $2$ of side length $2$ and one of side length $3$. This can be drawn straightforwardly.

• For $f(n) = r = 6$, the possible $n$ are $12, 15, 18, 20, 21, 24, 27, 28, 30, 33, 36$. For each $n$, we compute pairs $(a,b)$ such that $3a + 8b = 36 - n$. For $n = 12$, we get $(8,0)$ OR $(0,3)$. $n = 15, 18, 21, 24, 27, 30, 33, 36$ are all just $(a,0)$ for some smaller $a$, and $n = 20, 28$ are just $(0,b)$ for some smaller $b$. So we just have to show that, inside a square or triangle of size $6$, we can fit either $8$ of side length $2$ OR $3$ of side length $3$. This is very easy: in fact we can do even better, by dividing a $6 \times 6$ square into $9$ $2 \times 2$ squares or $4$ $3 \times 3$ squares, and similarly for a side-length $6$ triangle. (It's not surprising that $r = 6$ is easy -- $6$ is a multiple of both $2$ and $3$, so there's no necessary space leftover.)

• Finally, suppose $f(n) = r = 7$. Here, the possible $n$ are $23, 26, 29, 31, 32$, $34, 35, 37, 38$, $40, 41, 43, 46, 49$. For each $n$, again we want pairs $(a,b)$ such that $3a + 8b = 49 - n$. For $n = 23$, we get $(6,1)$, which is strictly easier than $n = 26, 29, 32, 35, 38, 41$ (which require $1$ side-length $3$ and fewer than $6$ side-length $2$), and also strictly easier than $n = 31, 34, 37, 40, 43, 46, 49$ (which are the same except they don't require the side-length $3$ square or triangle). That's all the possible $n$, so we just have to show $n = 23$ is achievable. So we fit a $3 \times 3$ square and $6$ $2 \times 2$ squares into a $7 \times 7$ square, and similarly for a triangle (neither task is hard).

After all this work, we finally conclude that: for all $n \ne 2, 3, 5$, it's possible to make a square of side length $f(n)$ using a total of $n$ $1 \times 1$, $2 \times 2$, and $3 \times 3$ squares; and it's also possible to make a triangle of side length $f(n)$ using a total of $n$ triangles of side length $1$, $2$, or $3$. This completes the proof of achievability, and shows that $s(n) = f(n)$ and $t(n) = f(n)$. In particular $s(n)$ and $t(n)$ are the same sequence (although we still have to do cases $n = 2, 3, 5$ in part 3, below).

Part 3: Division of a square or triangle into $n$ squares or triangles is impossible in case (i) -- $n = 2, 3, 5$

First we have to show that a square cannot be divided into $2, 3,$ or $5$ squares. This is proven in the answer to this mathSE question. For a triangle, we make a similar argument. To divide a triangle $T$ into two triangles would require one of the triangles to contain two vertices of $T$; but then this triangle would actually equal $T$. To divide $T$ into $3$ triangles would require each of the $3$ triangles to be at one of the vertices of $T$; but then there is space in the center of the triangle that is not covered. Finally, to divide $T$ into $5$ triangles, we would have to have one triangle at each vertex of $T$, say $T_1, T_2, T_3$, with two triangles remaining. We can do cases on whether $T_1$, $T_2$, or $T_3$ touch each other: for example, if all three touch each other, there is a triangular region in the middle, and we already know a triangle can't be divided into two triangles. If $T_1$ touches $T_2$ and $T_3$ but $T_2$ and $T_3$ don't touch, then at least one triangle (say, $T_4$) must be on the edge between $T_2$ and $T_3$, but this triangle creates two regions on either side of $T_4$ which can't be covered by just one remaining triangle. The cases with even fewer touching are similar.

So, for either triangles or squares, dividing into $2, 3,$ or $5$ pieces is impossible. Therefore, $s(n) = t(n) = 0$ for $n = 2, 3,$ or $5$. $\square$

Remark: I have not proven that in general, there is a bijection between divisions of a square into squares with integer side length, and divisions of a triangle into triangles with integer side length. As you note, the fact that $s(n) = t(n)$ certainly seems to suggest this. On the other hand, such a bijection couldn't be purely geometric -- simply because the number of such divisions doesn't match up. For example, consider when the side length is $n = 3$. Then the square can be divided in $6$ ways, and the triangle in only $5$ ways.

However, it seems plausible that if you just look at the sizes of the squares or triangles, then such a bijection exists: for example, since a square of side length $5$ can be divided into a $3 \times 3$, two $2 \times 2$, and eight $1 \times 1$ squares, a triangle can be divided this way as well. But I have no idea how to prove such a fact.

Solution 2:

First, think about the area of the small squares and the large square. If you start with $n$ unit squares you have a total area of $n$. You can replace some of them with $2 \times 2$ squares and add $3$ units each time and replace some others with $3 \times 3$ squares and add $8$ units each time. You need to do enough of this to increase $n$ to a perfect square.

The largest number you cannot make out of a sum of $3$'s and $8$'s is $13$ from the coin problem. This explains why $s(12)=6$. To make a square of side $5$ out of $12$ squares you would have to add $13$ units of area, but you can't. Once $n$ is at least $35$ we can always make $(\lceil \sqrt n \rceil+1)^2$ by adding $3$s and $8$s. We might be able to make $(\lceil \sqrt n \rceil)^2$.

The reason that squares and triangles work the same is that the area scales as the square of the side for both, so the argument above works the same. Now we have to argue that once $n$ is large enough you have enough freedom from the remaining size $1$ squares or triangles that we can always form the large figure we want to. Referring to the example of $12$, we can make the area $36$ by using $3\ 3\times 3$ squares and $9\ 1 \times 1$ squares. Assembling them into a $6 \times 6$ square is easy.

For a given $n\ge 35$, let $k=\lceil \sqrt n \rceil.$ The most we have to increase the area is $13+2k+1$, because if $k^2-n \gt 13$ we can make $k^2$. I don't have a concise argument that we can fit the larger squares, but there are so few of them it is not hard.