18
$\begingroup$

A solution to the Rectangle Puzzle of size n is an arrangement of n rectangles into a larger rectangle, such that no smaller rectangle is formed by outlining 2 or more of the placed pieces.

For example, here are solutions to the Rectangle Puzzle of sizes 2 and 5:

2 rectangles

5 rectangles

And here is an arrangement that fails to solve the puzzle for size 6, because the two tiles in the middle form a rectangle:

6 rectangles

3 and 4 are not solvable. Among the numbers 6, 7, 8, 9, 10, for which are the Rectangle Puzzle solvable?

$\endgroup$
  • $\begingroup$ Aren't 2 pieces forming a rectangle? $\endgroup$ – TTT Aug 17 '16 at 15:39
  • $\begingroup$ @TTT in which one? $\endgroup$ – Owen Aug 17 '16 at 15:40
  • $\begingroup$ In the rectangle of Size 2. $\endgroup$ – TTT Aug 17 '16 at 15:42
  • $\begingroup$ @TTT "that no smaller rectangle is formed by 2 or more of the pieces." $\endgroup$ – user14478 Aug 17 '16 at 15:43
  • $\begingroup$ Right, got it. Thx. $\endgroup$ – TTT Aug 17 '16 at 15:43
16
$\begingroup$

Here is a general solution for n>6.

enter image description here

Explanation:

The rectangles spiral around. To get the solution for a particular n, stop when you have placed the nth rectangle and truncate it so that the whole figure becomes a rectangle. Sadly this solution does not work for n=6, because then rectangles 2 and 6 together form a rectangle.

Here is a proof of why there is no solution for n=6.

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$
  • $\begingroup$ Oh wow, I was in the process of redoing my answer with this solution. Beat me to it. I also came to the conclusion that 6 doesn't work. 6 may not be possible at all. $\endgroup$ – TTT Aug 17 '16 at 16:20
  • $\begingroup$ I assume you need to truncate #9? Otherwise, this fails to meet the "larger rectangle" requirement. It would be nice to mention so explicitly. $\endgroup$ – jpmc26 Aug 17 '16 at 23:36
  • $\begingroup$ @jpmc26 - truncation is mentioned in the explanation. $\endgroup$ – TTT Aug 18 '16 at 1:34
  • $\begingroup$ I have just added a proof that n=6 is impossible. Not very elegant, but I think it works. $\endgroup$ – Jaap Scherphuis Aug 18 '16 at 6:51
  • 1
    $\begingroup$ Very nice proof. $\endgroup$ – Owen Aug 18 '16 at 15:58
4
$\begingroup$

Here are ones for

7 and 9 rectangles. 8 and 10 covered by comments. And a general solution greater then 6 by Jaap.

Pic1

enter image description here

pic2

enter image description here

Some general rules

Can't have an outer rectangle with a full side length
Can't have a square in a corner

$\endgroup$
  • $\begingroup$ In Pic 1, if you extend rect 1 up by 1, you can place an 8th horizontal next to it to get 8. $\endgroup$ – TTT Aug 17 '16 at 16:15
  • $\begingroup$ You can do the same with Pic 2 to get 10. $\endgroup$ – TTT Aug 17 '16 at 16:16
1
$\begingroup$

I (am pretty sure) I found the answer for n = 6. Please excuse the meager paint skillsenter image description here

Please feel free to let me know of the rectangle in here if I'm missing it, or to update the picture to make it prettier.

$\endgroup$
  • 6
    $\begingroup$ The five rectangles on the right form a rectangle, and are basically the n=5 solution. $\endgroup$ – Jaap Scherphuis Aug 17 '16 at 16:23
  • $\begingroup$ Ahhhh I see it now. Unlucky. Was only thinking of two smaller rectangles, not more than 2 $\endgroup$ – Avik Mohan Aug 17 '16 at 16:25
0
$\begingroup$

Note: I misread the question. Leaving this here (for now) in case it helps others.

The answer is (probably not):

All rectangles of size N >= 5 are solvable.

This can('t) be accomplished by:

Starting with size 5 as drawn in the question, and adding a rectangle to the right that is the same length as the right side of it to make 6. Then add another rectangle across the top that is the size of the entire top to make 7. Repeat as needed.

Example:

Demo of pattern

$\endgroup$
  • $\begingroup$ I feel like that only works up until 9, because then adding a rectangle to a side that is the size of one whole side would make a smaller rectangle. $\endgroup$ – Bcmonks Aug 17 '16 at 15:55
  • 1
    $\begingroup$ @Bcmonks - I'm working on a picture right now... $\endgroup$ – TTT Aug 17 '16 at 15:57
  • 4
    $\begingroup$ Unforunately, the original 5 pieces form a rectangle smaller than the whole. $\endgroup$ – Jaap Scherphuis Aug 17 '16 at 16:02
  • 2
    $\begingroup$ You won't be able to find a solution for more rectangles that builds upon an existing smaller solution without modifications; the smaller solution will still be present and fail the condition outlined by the puzzle. $\endgroup$ – Ian MacDonald Aug 17 '16 at 16:03
  • $\begingroup$ @JaapScherphuis - oh wow. I have now misread the question twice. In retrospect, that would have been way too easy for an Owen puzzle. $\endgroup$ – TTT Aug 17 '16 at 16:04

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.