19
$\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?

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

4 Answers 4

Reset to default
17
$\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.

Improve this answer
$\endgroup$
6
  • $\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, 2016 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, 2016 at 23:36
  • $\begingroup$ @jpmc26 - truncation is mentioned in the explanation. $\endgroup$
    – TTT
    Aug 18, 2016 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, 2016 at 6:51
  • 1
    $\begingroup$ Very nice proof. $\endgroup$
    – Owen
    Aug 18, 2016 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

Improve this answer
$\endgroup$
2
  • $\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, 2016 at 16:15
  • $\begingroup$ You can do the same with Pic 2 to get 10. $\endgroup$
    – TTT
    Aug 17, 2016 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.

Improve this answer
$\endgroup$
2
  • 7
    $\begingroup$ The five rectangles on the right form a rectangle, and are basically the n=5 solution. $\endgroup$
    – Jaap Scherphuis
    Aug 17, 2016 at 16:23
  • 1
    $\begingroup$ Ahhhh I see it now. Unlucky. Was only thinking of two smaller rectangles, not more than 2 $\endgroup$
    – Avik Mohan
    Aug 17, 2016 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

Improve this answer
$\endgroup$
7
  • $\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, 2016 at 15:55
  • 1
    $\begingroup$ @Bcmonks - I'm working on a picture right now... $\endgroup$
    – TTT
    Aug 17, 2016 at 15:57
  • 4
    $\begingroup$ Unforunately, the original 5 pieces form a rectangle smaller than the whole. $\endgroup$
    – Jaap Scherphuis
    Aug 17, 2016 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, 2016 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, 2016 at 16:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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