6
$\begingroup$

Here on puzzlingSE is an interesting question about tiling a rectangle with smaller rectangles. I will restate the question:

For which $n \in \mathbb{N}$ can a rectangle $R$ be tiled with $n$ smaller rectangles, $r_1, r_2, r_3, \ldots, r_n$, such that the only rectangle formed by the union of two or more smaller rectangles is $R$ itself?

This has already been answered for all but $n = 6$:

  • $n = 1$ is trivially possible.

  • Examples given in the post show that $n = 2$ and $n = 5$ are possible.

  • The top answer shows that all $n \ge 7$ are possible.

  • It is not too hard to show that $n = 3$ and $n = 4$ are impossible.

So the question is, is it possible to do this when $\boldsymbol{n = 6}$?

I expect the answer is no. I'm looking for a solution which is as elegant as possible.


Partial results: for a tiling of $R$ with six rectangles, the following are true:

  • No vertical line or horizontal line can cut $R$ in half.

  • There can be no four rectangles meeting at a point in the interior of $R$.

$\endgroup$
  • 1
    $\begingroup$ The problem is solved in Chung et al, Tiling rectangles with rectangles, Mathematics Magazine 55 (November 1982) 286-291, available at math.ucsd.edu/~ronspubs/82_04_tiling.pdf $\endgroup$ – Gerry Myerson Aug 18 '16 at 6:57
  • 1
    $\begingroup$ @GerryMyerson ...but the article asserts, without proof, that no tiling is possible for $n=6$. $\endgroup$ – grand_chat Aug 18 '16 at 7:15
  • $\begingroup$ @GerryMyerson thank you for the reference! Odd that they seem to have overlooked the simple tiling with $n=2$ -- that tiling seems to fit their definition. And yeah, they do explicitly leave out the proof for $n = 6$. $\endgroup$ – 6005 Aug 18 '16 at 8:06
4
$\begingroup$

Terminology: A compound is a proper subset of the smaller rectangles whose union is a rectangle. The problem is to prove there is no compound-free tiling by 6 rectangles.

First, we note that the four corners of R must be occupied by four separate rectangles:

  • If the same rectangle occupies two adjacent corners, it splits R by a straight line, which is not allowed according to the partial results.
  • If it occupies two diagonally opposite corners, it is R and no further rectangles can be placed.

After placing the rectangles at the corners:

.----1----.
.  |   |  .
.  |   ---.
.---      4
2     ----.
.--   |   .
. |   |   .
.---3-----.

how can we assign the remaining two rectangles to the edges 1, 2, 3 and 4 and the interior? We note that unless they are assigned to two opposite edges (the boxcar case), there are two adjacent edges with only three distinct rectangles on them, which can occur in two essentially different configurations:

.-------.
.   |   .
.   |---.
.---- B . (1)
.  |A   .
.-------.
.------.
.  | X .
.  |---.
.----  . (2)
. Y |  .
.------.

In configuration (1), to prevent the formation of compounds, at least two rectangles each must sit on edges A and B. But that makes a minimum of seven rectangles – and we only have six.

The remaining space in configuration (2) is in the shape of an ell, which must be filled by three rectangles. It is quite easy to show that up to rotations/reflections the only compound-free tiling of an ell by three rectangles is

.---.
.   .
.   .
.   .
.   .---.
.   | Y .
.-------.
.   X   .
.-------.

There are only two ways to place this ell tiling into configuration (2). In one of them, the rectangles marked X form a compound; in the other, the rectangles marked Y form a compound (try it).

Hence there is no compound-free 6-rectangle tiling of R with two adjacent edges sharing three distinct rectangles.


For the boxcar case, here are the two essentially different arrangements of the four corner squares:

.----------.
.   |   |  .
.   |   |  .
.   |   |  .
.   |   |  .
A---B   C--D (cis)
. |      | .
. |      | .
. |      | .
. |      | .
.----------.
.----------.
.   |   |  .
.   |   |  .
.   |   |  .
.   |   |  .
A---B   |  . (trans)
. |    C---D
. |    |   .
. |    |   .
. |    |   .
.----------.

In both configurations, the only time when the remaining space can be filled by two rectangles is when ABCD forms a straight line, but that causes AD to split R, which is again not allowed by the partial results.

We have covered all possible arrangements of the two remaining rectangles, and shown that none of them can give rise to a compound-free tiling. In conclusion, the tiling asked for in the original question cannot be done for n = 6.

$\endgroup$
  • $\begingroup$ Excellent work, thank you. $\endgroup$ – 6005 Aug 19 '16 at 19:27
1
$\begingroup$

Since I posted this, on the puzzlingSE post Jaap Scherphuis added a nice proof that $n = 6$ is impossible. I copy the proof here, with minor edits, and make this post community-wiki.

Observe that:

  1. A single rectangular piece cannot cover two of the corners of the completed figure.

    If there were such a piece, then the remaining n-1 pieces would form a sub-rectangle of the figure.

    Therefore the four corners of the final figure are from four different pieces.

  2. A corner piece must have at least 3 adjacent pieces.

    There must be at least one neighbour on each internal side of the corner piece. If a corner piece had exactly two neighbours, there must be exactly one on each side. If the neighbours were both longer than that side, they would overlap. Therefore at least one of those neighbours is the same length, and then the corner piece and that neighbour together form a rectangle. This is not allowed, so a corner piece must have more than two neighbours.

  3. Diagonally opposite corner pieces cannot touch.

    If diagonally opposite corner pieces touched, then the remaining area of the whole figure would consist of two rectangular areas. If you fill such an area with two or more pieces, those pieces are a sub-rectangle of the figure, which is not allowed. If you fill it with a single piece, then that is a corner piece with exactly two neighbours, which is also not allowed as per #2 above.

Now lets consider $n=6$ specifically.

Four of those six pieces must be in the four corners of the final figure (#1). Suppose the remaining two pieces are fully internal to the figure. Each of the outside pieces can only expose one side to the internal area, so the internal area is rectangular. Filling it with the remaining two pieces creates a sub-rectangle with 2 pieces.

Suppose on the other hand that all 6 pieces are on the boundary of the final figure, i.e. there are no internal pieces. So we have 4 corner pieces and 2 edge pieces. Suppose a corner piece lies between two edge pieces. It must have a third neighbour (#2), but the only candidate is the diagonally opposite corner, which violates #3. The only other arrangement for the edge pieces is on opposite sides of the final figure, say the left and right sides. The two top corners are adjacent, cannot touch either of the bottom corners, so the only way for them to have 3 neighbours is for both corners to be adjacent to both edge pieces. This is not possible.

The last possibility is that we have 4 corner pieces, 1 edge piece, and 1 internal piece. The two corners next to the edge piece must have the internal piece as their third neighbour. The edge piece has three internal sides and so must have at least three neighbours. The only possibility is that it is also adjacent to the internal piece. In a similar argument to #2, the corners cannot be the same length as the edge piece, and if both were longer then the edge piece and the internal piece have matching lengths and form a rectangle.

All possibilities lead to failure, so $n=6$ is impossible.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.