3
$\begingroup$

Suppose a $m \times m$ square can be dissected into $7$ rectangles such that no two rectangles have a common interior point and the side lengths of the rectangles form the set

$\{1,2,3,4,5,6,7,8,9,10,11,12,13,14\}$.

Find the maximum value of $m$.

I have calculated that the value is at most $22$, because if we maximize the area covered by the $7$ rectangles which have evidently distinct sides, we get

$14 \times 13 + 12 \times 11 + 10 \times 9 + 8 \times 7 + 6 \times 5 + 4 \times 3 + 2 \times 1 = 504$

and

$\sqrt{504}=22.45$ so the max side length can be $22$.

How do we construct the figure, if possible?

$\endgroup$
7
  • $\begingroup$ A preliminary check should be done to find matchings of side lengths that give total area $22^2=484$. $\endgroup$
    – hardmath
    Sep 3, 2015 at 14:27
  • 2
    $\begingroup$ A short program to check the possible matchings finds seventy-four whose rectangles have total area $484$, including this one: (2*1)+(4*3)+(7*6)+(8*5)+(12*11)+(13*10)+(14*9) = 484 $\endgroup$
    – hardmath
    Sep 3, 2015 at 23:32
  • $\begingroup$ @hardmath this summation is valid but i dont think this can form a square. some other combination of the remaining 73 will surely form a square. i tried to write the program but i couldnt understand how to form the sum from the array. $\endgroup$ Sep 4, 2015 at 7:12
  • $\begingroup$ @user260674 ,If only we could get the other constraint(for possibility of square) except for sum of the areas of rectangle is m^2 . $\endgroup$ Sep 4, 2015 at 7:40
  • 1
    $\begingroup$ @ShakulPathak: Another constraint is the sum of edge lengths along each side being $m$. When $m = 22$ there are fairly few ways that the available edge lengths can add up to that. Once the corner squares are chosen (4 out of the seven available), the edge length criteria eliminate all but a handful of configurations. $\endgroup$
    – hardmath
    Sep 4, 2015 at 12:26

1 Answer 1

4
$\begingroup$

Update (3/18/2016)

The layout below (Fig. 1), which I at first conjectured to be a unique arrangement (up to dihedral symmetries and "stretching") of seven rectangles with unequal sides tiling an $N\times N$ square, provided solutions (using sides of lengths $1$ to $14$ as posed in the question) for $N=18,19,20,21$ but not for $N=17,22$.

A Related Question was posed to discover if other seven rectangle arrangements are possible, and indeed another layout (Fig. 2) was found by computer search. The new layout admits tiling squares with sides $N=19,21,22$. Therefore the maximum square that can be tiled as in the problem here is $22\times 22$.

Figure 1. A $21\times 21$ square tiled by 7 rectangles with prescribed unequal sides

square dissected into seven rectangles

Figure 2. A $22\times 22$ square tiled by 7 rectangles with prescribed unequal sides

alternate seven rectangle layout


It can be shown that $N=22$ is impossible for the layout of Fig. 1 by simple algebra, so that we need not rely on the negative finding of a computer program for this conclusion.

Let the sizes of rectangles be $(h_A,w_A),\ldots,(h_G,w_G)$ respectively. Then:

$$ \begin{align*} N &= h_C + h_D + h_F + h_G \\ h_A &= h_C + h_D + h_F \\ h_B &= h_C + h_D \\ h_E &= \phantom{ h_C + } \;h_D + h_F + h_G \end{align*} $$

$$ \begin{align*} N &= w_A + w_B + w_D + w_E \\ w_C &= \phantom{w_A + w_B + } \;w_D + w_E \\ w_F &= \phantom{w_A + } \;w_B + w_D \\ w_G &= w_A + w_B + w_D \end{align*} $$

The combined sum of heights and widths is $105$. Applying the above relations we find:

$$ 4N + h_C + 2h_D + h_F + w_B + 2w_D = 105 $$

The least that the smaller terms on the left hand side could add up to is $18$, we get that $N \le 21 = \lfloor (105-18)/4 \rfloor$, a slight improvement on the upper bound obtained just by maximizing the total area of rectangles.

Original Post

It was easy to generate all the possible edge pairings whose rectangle areas sum to a given value, e.g. $K^2$ where integer $17 \le K \le 22$. This table counts the pairings with total area $K^2$:

$$ \begin{array}{c|r} K & \text{#pairings} \\ \hline 22 & 74 \\ 21 & 581 \\ 20 & 1110 \\ 19 & 881 \\ 18 & 630 \\ 17 & 65 \end{array} $$

The problem then reduces to finding if any specific set of rectangles can tile a $K\times K$ square.

My approach began with choosing the four "corner" rectangles, which allows us to eliminate redundancy due to dihedral symmetry (flipping and rotating the square). Moreover we can prove at least one edge must covered by its two corner rectangles, so we check for that and also that diagonally opposed corner rectangles do not overlap.

We then fill any edges not already covered from the remaining stock (three rectangles, not including the corners already assigned). In a typical solution the corner rectangles cover three of the four edges and after assigning one extra rectangle to cover the "gap" in the fourth edge, there are two rectangles left to fill in interior "holes".

This is where I got bogged down initially, A simple representation used for choosing the corners and filling edge gaps is awkward at detecting the interior holes and how to fill them. I started writing code to convert to a list representation of those unit squares not covered by the edge rectangles, but failed to get this working correctly.


To show that the maximum area of the seven rectangles is 504 (resp. minimum area is 280) as sketched in the Question, it suffices to work with four lengths and two rectangles at a time. Thus the following:

Lemma Consider integers $D \gt C \gt B \gt A \gt 0$. There are three ways to pair these lengths to form two rectangles, corresponding to pairing $A$ with exactly one of $B,C,D$. The areas of these pairings compare strictly:

$$ (AB + CD) \gt (AC + BD) \gt (AD + BC) $$

Proof: Take the differences between adjacent terms compared above:

$$ (AB + CD) - (AC + BD) = (D-A)(C-B) \gt 0 $$

$$ (AC + BD) - (AD + BC) = (B-A)(D-C) \gt 0 $$

QED

You can bootstrap from this that the maximum area is achieved by pairing the longest two side lengths together, and so on with the remaining side lengths. For if the two longest sides are not already paired, the Lemma says the total area would be strictly increased by taking the two rectangles that have those sides and swapping lengths so the two longest edges are paired. Repeat this argument until all sides are maximally paired.

A similar argument proves that the minimum area is achieved by pairing the shortest side length with the longest one, and so on with the remaining side lengths.

Hence for our particular lengths, the largest possible area is:

$$ 14\cdot 13 + 12\cdot 11 + 10\cdot 9 + 8\cdot 7 + 6\cdot 5 + 4\cdot 3 + 2\cdot 1 = 504 $$

and the smallest possible area is:

$$ 14\cdot 1 + 13\cdot 2 + 12\cdot 3 + 11\cdot 4 + 10\cdot 5 + 9\cdot 6 + 8\cdot 7 = 280 $$

The range $K = 17,\ldots,22$ of square sizes then follows from $22 = \lfloor \sqrt{504} \rfloor$ and $17 = \lceil \sqrt{280} \rceil$.

Update (02/10/2016)

I conjecture that there are very few ways, perhaps only one in a "general position" sense, that a square can dissected into seven unequally-sided rectangles (as is here required).

One such arrangement (up to dihedral symmetry and perturbation of side lengths) is illustrated by the figure shown at top. Once an arrangement like this is identified, it is easy to check if the seven heights and widths of the rectangles can be assigned values $1,\ldots,14$ as the satisfaction of the constraints amounts to checking a few linear equations.

The real difficulty then lies in showing how many generic dissections are possible.

$\endgroup$

You must log in to answer this question.

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