7
$\begingroup$

Inspired by Polyomino Z pentomino and rectangle packing into rectangle

Also in this series: Tiling rectangles with N pentomino plus rectangles

Tiling rectangles with T pentomino plus rectangles

Tiling rectangles with U pentomino plus rectangles

Tiling rectangles with V pentomino plus rectangles

Tiling rectangles with W pentomino plus rectangles

Tiling rectangles with X pentomino plus rectangles

The goal is to tile rectangles as small as possible with the F pentomino. Of course this is impossible, so we allow the addition of copies of a rectangle. For each rectangle $a\times b$, find the smallest area larger rectangle that copies of $a\times b$ plus at least one F-pentomino will tile. Example shown, with the $1\times 1$, you can tile a $3\times 3$ as follows.

F plus 1x1

Now we don't need to consider $1\times 1$ any longer as we have found the smallest rectangle tilable with copies of F plus copies of $1\times 1$.

There are at least 17 more solutions. More expected. I tagged it 'computer-puzzle' but you can certainly work some of these out by hand. The larger ones might be a bit challenging.

$\endgroup$
  • 6
    $\begingroup$ sigh, why all of these tile problems? I'm beginning to feel overwhelemed $\endgroup$ – kraby15 Apr 17 '18 at 2:58
8
$\begingroup$

Here are a couple of $1 \times n$ solutions, which I believe to be optimal. They seem to follow some pattern(s), some of which are generalizable (spoiler ahead):

the rectangles are at the edges of the board; often one rectangle per edge, sometimes more, and sometimes (the $n$ = 12, 13 and 15 case) in the middle. The cases $n$ = 4, 6, 14 and 16 are extra 'nice' and can be generalized to $n=10k+4$ and $n=10k+6$ (though the solutions won't necessarily be optimal). Here's a nice visualization of the inductive step:

enter image description here

Note that these solutions also work for all $n$ not divisible by 5; e.g. two 1x7 rectangles fit in a single 1x14 rectangle, so we can just reuse that solution. There is a smaller one, though (see below).

The solutions for $1 \times 10$, $1 \times 18$ and $1 \times 20$ (all below) also seem to form some kind of generalizable family.

As @JaapScherphuis notes in the comment, there's a (probably non-optimal) generalizable solution for $1 \times n$, $n$ is even, rectangles, just like for the W-pentomino. By halving the rectangles, we can also obtain solutions for odd $n$, and the parts with just rectangles and no F-pentominos can be shortened.

Even $n$ fit in a $2n+1 \times 3n$ rectangle (left)
Odd $n$ fit in a $2n+1 \times 4n$ rectangle (right)
enter image description here

$1 \times 3$:

$8 \times 6 = 48$
enter image description here

$1 \times 4$:

$6 \times 6 = 36$
enter image description here

$1 \times 5$:

$11 \times 10 = 110$
enter image description here

$1 \times 6$:

$8 \times 8 = 64$
enter image description here

$1 \times 7$:

$20 \times 9 = 180$
enter image description here

$1 \times 8$:

$22 \times 9 = 198$
enter image description here

$1 \times 9$:

$13 \times 12 = 156$
enter image description here

$1 \times 10$:

$20 \times 11 = 220$
enter image description here

$1 \times 11$:

$13 \times 28 = 364$
enter image description here

$1 \times 12$:

$17 \times 17 = 289$
enter image description here

$1 \times 13$:

$15 \times 25 = 375$
enter image description here

$1 \times 14$:

$16 \times 16 = 256$
enter image description here

$1 \times 15$:

$17 \times 25 = 425$
enter image description here

$1 \times 16$:

$18 \times 18 = 324$
enter image description here

$1 \times 18$:

$19 \times 28 = 532$
enter image description here

$1 \times 20$:

$21 \times 30 = 630$
enter image description here


Some minimal solutions for $2 \times 2k+1$; first $2 \times 3$:

$10 \times 11 = 110$
enter image description here

$2 \times 5$:

$18 \times 20 = 360$
enter image description here

$2 \times 9$:

$30 \times 30 = 900$
enter image description here

$2 \times 11$ (a nice one, but IMHO equally nice as $2 \times 9$):

$36 \times 36 = 1296$
enter image description here

The last two are part of a generalizable solution, see the bottom of the post.


Another one for $3 \times 4$:

$14 \times 17 = 238$
enter image description here

and for $3 \times 5$:

$22 \times 30 = 660$
enter image description here


This night, I found a new one for $2 \times 7$ by combining the $2 \times 9$/$2 \times 11$ padding with the inner pattern for the $1 \times 16$. This is a hand-made solution so I'm not sure it's minimal:

38x38 = 1444
enter image description here

In general, the generalizable solutions for $1 \times (10k+4)$ resp. $1 \times (10k+6)$ give rise to solutions for $2 \times (10k+9)$ resp. $2 \times (10k+11)$; the $2 \times 7$ solution mentioned above is basically a subdivision of the $2 \times 21$ one minus some extraoneous padding.

The length of the red line is $10k+4$ or $10k+6$; this makes the purple line $10k+9$ or $10k+11$ and the total solution $(3n+3) \times (3n+3)$.
enter image description here

$\endgroup$
  • $\begingroup$ Both optimal yes. The 1x3 can also be arranged into a different rectangle with the same area. Six to go. $\endgroup$ – theonetruepath Apr 27 '18 at 0:34
  • $\begingroup$ 1x3, 1x4, 1x5, 1x6, 1x7 all optimal. 1x8 your solution is optimal but it's 22x9 not 20x9. 1x9, 1x10 optimal too. There are still some 2xN solutions to find, and the 1xN seem to go on forever, but minimal solutions don't seem to follow an easily discernible fixed pattern. $\endgroup$ – theonetruepath May 8 '18 at 21:40
  • $\begingroup$ In particular, the 2x11 has a very nice solution $\endgroup$ – theonetruepath May 9 '18 at 4:32
  • $\begingroup$ @theonetruepath I found a generalizable solution for $n=10k+6$ (I'm normally not bothering to ping you with updates, but this one is too nice to not to share). $\endgroup$ – Glorfindel May 9 '18 at 12:06
  • 1
    $\begingroup$ Doesn't your general $1\times2k$ solution for the W pentomino work for the F pentomino too? $\endgroup$ – Jaap Scherphuis May 10 '18 at 9:07
5
$\begingroup$

This should be the minimal solution

enter image description here

$\endgroup$
  • $\begingroup$ That's minimal for $1\times 2$ yes $\endgroup$ – theonetruepath Apr 19 '18 at 0:12
-1
$\begingroup$

I'll get the easy one out of the way: the answer for $1 \times 2$ is

a $3 \times 6$ rectangle. A tiling exists with two F pentominoes and four $1 \times 2$ rectangles. It can be is obtained by taking the $1 \times 1$ solution, reflecting it about the top edge, and joining together the pairs of $1 \times 1$ rectangles into $2 \times 2$ rectangles in an obvious way.

This is minimal because

the smallest dimension of the rectangle must be 3, because the diameter of the F pentomino is 3. Suppose there is only one F pentomino present. In this case, both dimensions must be odd: the pentomino covers an odd number of squares, and every $1 \times 2$ tile covers an even number, so the total number of squares in the grid must be odd. Suppose the smallest dimension is 3. It is obvious that the $3 \times 3$ case won't work. A little trial and error shows that the $3 \times 5$ case won't work either; effectively, we would have to extend the rectangle in the original diagram "upwards" to accomplish this, but a checkerboard coloring argument shows that one domino would have to cover two squares of the same color to accomplish this.

For two F pentominoes, one or both dimensions must be even by the same parity argument as above. This means that the three smallest possible grids are $3 \times 4$, $4 \times 4$, and $3 \times 6$ (which we know to exist). It is not possible to fit two F pentominoes into a $3 \times 4$ grid; and while it is possible to fit them into a $4 \times 4$ grid, the remaining space can't be filled with dominoes. Thus $3 \times 6$ is minimal.

$\endgroup$
  • 1
    $\begingroup$ Nope. Not minimal, despite your proof! Maybe a little more trial and error in the $3\times 5$ case? $\endgroup$ – theonetruepath Apr 18 '18 at 0:18
  • $\begingroup$ Checkerboard coloring shows 5 white 5 black (checkerboard coloring of the F-pentomino would result in 3 of one color, 2 of the other so it's fine anyway) $\endgroup$ – somebody May 8 '18 at 22:07

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.