26

Let's pack some (one or more) T hexominoes together with some (one or more) small $a\times b$ rectangles into some bigger $m\times n$ rectangle without holes and overlapping pieces.

For example, I can pack two T hexominoes and eight $1\times1$ rectangles into a $5\times4$ rectangle:

Task

Find as many as you can different integer pairs $\{a,b\}$ so that one or more rectangles of size $a\times b$ can be packed together with T hexominoes into a $m\times n$ rectangle without holes and overlapping pieces.

Provide images of solutions if you claim that some combination is possible. Please, put your images in spoiler tags so that other users can try find themselves.

If some answers will have same number of pairs $\{a,b\}$, then answer with smaller total area of outer rectangles on example images is preferable. If area also equal, then earlier posted answer is preferable.

EDIT: Please, add to your answers total area of outer rectangles. If one tiling implicitly includes several $a\times b$ rectangles, then multiply area by number of combinations it includes.

Notes

I can guarantee that there exist solutions following integer pairs:
$1\times1$, $1\times2$, $1\times3$, $1\times4$, $1\times5$, $1\times6$, $1\times8$, $1\times9$,
$2\times2$, $2\times3$, $2\times4$, $2\times5$, $2\times6$

I'm wondering why a $1\times7$ rectangle solution is hard to find (maybe it's impossible?) when there exist solutions for with $1\times8$ and $1\times9$ rectangles.

1 week after posting, I'll put up my own answers for unfound combinations.

Somnium
  • 1,028
  • 7
  • 24
  • 2
    Please clarify your question; I can't understand what you're asking. Do you want to pack $m$ T-hexominoes and $n$ $a\times b$ rectangles into a $c\times d$ rectangle? What are the combinations you're looking for of $m$, $n$, $a$, $b$, $c$, $d$? Are some of these fixed? – Rand al'Thor Nov 19 '14 at 21:56
  • 1
    Thanks for editing! But when you say 'a 1x7 rectangle solution', does this mean $a$ and $b$ are 1 and 7? What are the other parameters? Or are you just trying to pack some T-hexominoes and some 1x7 rectangles into a big rectangle of some size? – Rand al'Thor Nov 19 '14 at 22:05
  • @randal'thor Yes, I'm "just trying to pack some T-hexominoes and some 1x7 rectangles into a big rectangle of some size". 1x7 is one that I'm suspicious about. – Somnium Nov 19 '14 at 22:09
  • Now that I've understood it, this is an interesting question! There must have been books written about this sort of thing. – Rand al'Thor Nov 19 '14 at 22:18
  • Such problems are calleng polyomino tilings. I like solving them and made a web-site dedicated to it (can be seen in my profile), however, a lot of tilings I've found are not on the web-page because I had not enought time to put them there. You can have a look, maybe you'll find it interesting. – Somnium Nov 19 '14 at 22:20
  • 1
    Under notes, you say $1 \times 7$ is impossible, then again that it is possible. Is the second supposed to be $1 \times 8$? In the list you have found, is the first $1 \times 2$ supposed to be $1 \times 1$? – Ross Millikan Nov 19 '14 at 22:41
  • @RossMillikan I said maybe impossible, I've only such feeling because I couldn't find one nor prove it's impossible. And yes, 1x2 should 1x1, that a mistake. I'll correct. About 1x8 I don't understand. Combinations with all listed rectangles I have found. There should be possible more combinations. – Somnium Nov 20 '14 at 07:20
  • @Len I'm not asking for smallest, I'm asking for any. That's only an example, I've used two hexominoes to show, that it's allowed to use more than one. – Somnium Nov 20 '14 at 17:28
  • @Len Added constraints. I believe, that there is finite set of $a\times b$ rectangles with which T hexomino can be packed into rectangle (For some other hexominoes, indeed, there exist infinite set, for example, for L hexomino). – Somnium Nov 20 '14 at 19:24
  • 1
    The more solutions I see, the more I like this question. A pity I can not up-vote it more than I have already! I'm eager to the see the link to your homepage once it is up! – BmyGuest Dec 14 '14 at 17:48

5 Answers5

14

2x2 - area 108 - optimal

2x2

2x3 - area 72 - optimal

2x3 2x3 2x3

2x4 - area 108 - optimal

2x4

3x4 - area 84 - optimal

3x4

1x5 - area 54 - optimal

1x5

2x5 - area 304 - optimal

2x5

3x5 - area 576 - optimal

3x5

2x6 - area 240 - optimal

2x6

1x7 - area 1034

1x7

1x8 - area 432 - optimal

1x8

3x8 - area 5880

3x8

1x9 - area 585 - optimal

1x9

Note that by subdividing the yellow rectangles:
2x3 indirectly solves 1x1, 1x2, 1x3
2x4 indirectly solves 1x4 and 2x2
2x5 indirectly solves 1x5
2x6 indirectly solves 1x6

Glorfindel
  • 28,033
  • 9
  • 96
  • 142
Florian F
  • 29,623
  • 4
  • 63
  • 138
  • Yes, it was a nice surprise. – Florian F Nov 22 '14 at 22:10
  • Your 2x2 solution can be extended also for 2x4 - it'll be smaller then. – Somnium Nov 24 '14 at 10:28
  • I know. I already did the picture and edited the answer. I must have forgotten to save the edits. I'll do that tonight. – Florian F Nov 24 '14 at 11:12
  • No more rectangles found? I have some unfinished in my answer. Maybe they will help you. Seems like you have skill in finding tilings. – Somnium Nov 26 '14 at 18:38
  • 1
    No more. I filled a number of pages with T patterns but managed only to improve on existing answers. – Florian F Nov 26 '14 at 22:50
  • I believe combinations we found are the only solvable or others are too huge to be found by hand. What do you think about I make similar question with different pieces? Or it won't be so interesting second time? – Somnium Nov 26 '14 at 23:49
  • Thanks. It's the result of a program. And a week of computing. – Florian F Dec 08 '14 at 01:04
  • @FlorianF 1x7 is amazing... What program did you use? Non-stop week computing?! Is it smallest possible rectangle? – Somnium Dec 11 '14 at 15:47
  • I wrote a java program to search solutions. Simple backtracking. I am not sure it ran non-stop, my computer sometimes goes to sleep. I don't know yet whether it is the smallest solution. I am searching by smallest dimension. I fond a solution at 15xN and then 22xN. But I haven't been thru all dimensions. The larger the fixed dimension is, the longer it takes. I shoud go up to 32xN to be sure. But I haven't been past 25xN. – Florian F Dec 11 '14 at 16:38
  • @FlorianF May I post your solution on my webpage? I'll mention it was found by Florian F from StackExchange. – Somnium Dec 11 '14 at 21:14
  • Yes. What is the address? – Florian F Dec 12 '14 at 08:35
  • Thanks. I haven't it posted yet but I will when I'll update page. Address can be found in my profile. – Somnium Dec 12 '14 at 19:59
  • Great solution. It's a bit of a shame that most (every?) puzzle seems to be "solve-able" by brute-force trying these days, but knowing there is a solution is already great! And the answer is striking. +1 from me. – BmyGuest Dec 14 '14 at 17:46
  • Interestingly, your 3x5 solution is very similar to one of mine unsuccessfull 3x5 (already replaced by successfull huge one). Your solution's area is wrong, should be - 576. – Somnium Dec 14 '14 at 20:30
  • @BmyGuest Brute-force for this kind of puzzle (when rectangle size is unknown) is very expensive in time. – Somnium Dec 14 '14 at 20:31
  • 56 was a typo. I was still busy verifying optimality according to my (hopefully correct) program. You had a good start after all with the 3x5. – Florian F Dec 14 '14 at 20:33
  • To prove that solution is optimal, you should check all rectangles with smaller area. For example, if you think that some solution with area 6 is optimal, then you should check rectangles with areas 5,4,3,2,1 - 5x1,4x1,2x2,3x1,2x1,1x1. For small areas it's obvious that many of rectangles won't have solutions, however, for big areas that might be false. – Somnium Dec 14 '14 at 21:03
  • Nice 3x8 solution! – Somnium Dec 19 '14 at 12:26
  • It confirms what you said earlier: more solutions might exist but are too huge to be found by hand. – Florian F Dec 20 '14 at 19:35
  • However there is pattern in all solutions - hexominoes should be packed in clusters so one side is straight and is equal to one side of rectangle, so there should be finite number of rectangles, with which tiling is possible. – Somnium Dec 20 '14 at 20:14
8

Let's start with the easy ones.

1x1

enter image description here

1x2

enter image description here

1x3

enter image description here

1x4

enter image description here

1x6

enter image description here

These ones took me a while.

1x5

enter image description here

2x3

enter image description here

Kevin
  • 6,449
  • 1
  • 31
  • 30
  • Just curious, what interface/software are you guys using to make the graphs? – Leo Nov 21 '14 at 19:08
  • @Leo, I wrote a small image rendering application using Python and the Pillow library. I don't know what everyone else is using. – Kevin Nov 21 '14 at 20:12
  • @Leo I wrote VB.NET application for creating polyomino tilings. In my opinion, fastest method without any special programs is to use PowerPoint - create figures from squares, group them and then it's easy to copy/move/rotate them. – Somnium Nov 21 '14 at 22:20
  • 1
    Your 1x5 could be reduced to a 9 by 6 rectangle. – Florian F Nov 22 '14 at 14:35
6

Rev 4 - added 1 x 9 incorrect but still trying, added 1 x 5 using Florian's clue
Rev 3 - added 1 x 8 solution
Rev 2 - added 2 x 6 solution
Rev 1 - added 2 x 2 solution
Thanks for the clarification, Somnium. I will put some more answers here.

1 x 5 solution using Florian's clue (area = 54)

1x5 solution

1 x 8 solution (area = 560)

1x8 solution

1 x 9 incorrect still trying

1x9 incorrect

2 x 2 solution (area = 144)

2x2 solution

2 x 3 alternate (area = 72)

2x3 alternate

2 x 6 solution (area = 240)

2x6 solution

Len
  • 8,936
  • 2
  • 30
  • 65
2

2x6 - area 240 Another solution

3x5 - area 1014

Following maybe will help someone.

2x9 unsuccessful try

1x7 unsuccessful try

Somnium
  • 1,028
  • 7
  • 24
1

I found one for a new size, $4 \times 5$:

36x39 = 1404
enter image description here

Glorfindel
  • 28,033
  • 9
  • 96
  • 142
  • That was unexpected! It's found by program or by hand? – Somnium Jun 09 '18 at 08:54
  • By program. I'm getting better at hand-solving, but this is out of my league. – Glorfindel Jun 09 '18 at 09:12
  • I usually try at first hand-solving, to see if there's some pattern, if there's something that can prevent solution existence, then do computer search. Do you have solutions of other size (may be bigger)? If I want to post your solution on my webpage (not so soon), do you want attribution? – Somnium Jun 09 '18 at 09:48
  • It's not so much that I want attribution; because this content is posted on Stack Exchange, under the CC BY-SA 3.0 license you have to provide attribution; see the Terms of Service. (The flip side of this is that you don't even need to ask me for permission to publish the content elsewhere, though I appreciate it!) I don't have any more solutions at the moment, by the way. – Glorfindel Jun 09 '18 at 15:12
  • @Somnium and as for something preventing solution existence, my program is far better than me at that as well. It takes half a second to realize that there's no solution for the F-pentomino + the 2x2 rectangle (well, at least not one with dimensions below 63x128). – Glorfindel Jun 09 '18 at 15:28
  • Not for all polyominoes brute force will give answer so fast, especially for such big dimensions. I guess this one particular solutions was found in a lot longer time than 0.5 second. – Somnium Jun 09 '18 at 15:35
  • This solution was found in 5 minutes, but a couple of other tilings took several days, that's correct. – Glorfindel Jun 09 '18 at 15:47