14
$\begingroup$

Inspired by Polyomino Z pentomino and rectangle packing into rectangle

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

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 X pentomino plus rectangles

The goal is to tile rectangles as small as possible with the W 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 W-pentomino will tile. Example shown, with the $1\times 1$, you can tile a $3\times 3$ as follows.

3x3

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

There are at least eight more solutions.

$\endgroup$
12
$\begingroup$

First, a generalizable solution for $1 \times n$, $n$ is even. By halving the rectangles, we can also obtain solutions for odd $n$, and the parts with just rectangles and no W-pentominos can be shortened.

These can be used for F pentominos as well.
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
Computer research shows that this is optimal for $1 \times 8$, $1 \times 9$, $1 \times 10$, $1 \times 12$ and $1 \times 14$.

This is a way to tile

a 6x3 rectangle with Ws and 1x2s:
enter image description here

This is optimal for this $a \times b$ because

to fill the gap at the 'bottom' of the W, you need at least two 1x2s (using another W to fill it leads to at least a 5x4 rectangle which is bigger. That fixes the right half of the rectangle; that a 5x3 rectangle is not possible is easy to see with a checkerboard argument, and for a 4x4 we'd need another 7 squares, which is odd, so another W, and the only position to place that W leaves two corner squares empty.

And here is a way to tile

a 4x7 rectangle with Ws and 1x3s:
enter image description here

I've found two more, one for 1x4:

enter image description here
(11x8 = 88)

and a rather large one for 1x5:

enter image description here
(15x12 = 180)

Continuing down the line we have (AFAIK) minimal tilings for 1x6:

enter image description here
(8x18 = 144)

for 1x7 one which looks like a Star Wars fighter:

enter image description here (10x37 = 370)

for 1x8:

enter image description here
(17x24 = 408)

for 1x10:

enter image description here
(21x30 = 630)

for 2x3:

enter image description here
(7x10 = 70)

for 2x5:

enter image description here
(20x20 = 400)

for 2x11:

enter image description here
(38x38 = 1444)

Notice the 8 by 8 'rounded square' in the center of the 2x11 solution, wrapped by two layers of W pentominos before moving on to the rectangles. This is the same layout as the 2x5 solution, but there the rounded square has dimension 2 by 2, so it vanishes. Whether this solution type is generalizable for other $2 \times n$ I don't know yet. It does not lead to solutions for $2 \times 7$; for example, a rounded rectangle of sizes $46 \times 74$ and $32 \times 102$ cannot be tiled by W pentominos.

Moving on to the $a = 3$ case, one for 3x4:

enter image description here
(19x28 = 532)

The solution for $3 \times 4$ is generalizable (but not necessarily minimal) to other $3 \times n$ ($n$ not divisible by 3). Here is a 'recipe' for this, a $3 \times 5$ solution, which also explains the parameters $x_i$ and $y_i$ necessary for the construction:

$28 \times 55 = 1540$
enter image description here

First, concentrate on the shape formed by the W pentominos alone. Note that it can extend indefinitely from the top left in two directions, and for each end, we have two choices for a 'tail'; a blunt end as seen at the bottom ($x_0 = 3$) and a sharp end at the right ($y_0 = 1$). It turns out that when the area formed by $x_1$ and $y_1$ is tiled by vertical rectangles, this only works when $y_0 = 1$ and $x_0 = 3$ (horizontal, it's the other way around); symmetry dictates it suffices to tackle just the vertical case. In the $3 \times 4$ case, $x_1$ is odd and $y_1$ is even; here, it's the other way around. They cannot have the same parity.

The only other rules for $x_i$ and $y_i$ are divisibility rules for both $a (= 3)$ and $b (= n)$. It seems to work just like magic:

$a |\, x_1$
$a |\, x_2$
$a |\, x_3 - 1$
$a |\, x_4 - 1$
$a |\, x_5$
$b |\, x_1 + 3$
$b |\, x_2 + 1$
$b |\, x_3$
$b |\, x_4$
$b |\, x_5 + 1$
$a |\, y_1 + 1$
$a |\, y_2$
$a |\, y_3 - 1$
$b |\, y_1$
$b |\, y_2 + 1$
$b |\, y_3$

The size of the solution is given by $(\sum_{i=0}^3 y_i + 3) \times (\sum_{i=0}^5 x_i + 2)$. To construct a solution for a given $a \times b$, just choose the smallest (non-zero) $x_i$ and $y_i$ which satisfy the equations; for $x_1$ and $y_1$ you have to check their parity.

For example, in the $3 \times 7$ case the smallest solution for $x_1$ is 18 and for $y_1$ = 14, but they're both even and we have to settle for $x_1 = 39$ (or $y_1 = 35$ but that will give a larger solution). This is the result:

$31 \times 70 = 2170$
enter image description here

The solution for $3 \times 10$ is rather small compared to the rectangle size and my program was able to verify (after a few weeks of calculation) that it's the minimal solution.

Interestingly, the $28 \times 55$ solution for $3 \times 5$ is not the smallest one. The one below is smaller and is generalizable for $3 \times n$ where $n$ is odd but not divisible by 3, but it's usually larger than the corresponding one for the previous family.

$35 \times 38 = 1330$
enter image description here

$\endgroup$
  • $\begingroup$ Yup. Two down, six to go. $\endgroup$ – theonetruepath Apr 15 '18 at 10:28
  • $\begingroup$ 1x2, 1x3, 1x4, 1x5 all minimal. Four more that I've found so far. $\endgroup$ – theonetruepath May 9 '18 at 10:03
  • $\begingroup$ I've found seven more, including a $1 \times 2k$ generalizable one. Will post them later today. $\endgroup$ – Glorfindel May 9 '18 at 17:12
  • $\begingroup$ Your 1x6 is smaller than mine which means I have to go find a bug. 1x7 is the same, also 1x8 and 2x5. My program hasn't reached the others yet. $\endgroup$ – theonetruepath May 10 '18 at 9:16
  • $\begingroup$ Heh. I noticed a strange one in mine, my initial 2x3 solution was 10x10, consisting of the currently displayed 10x7 solution + five 2x3 tiles on top of each other. It turns out I wrongfully discarded some possibilities. Luckily I spotted that before submitting :) $\endgroup$ – Glorfindel May 10 '18 at 9:21
1
$\begingroup$

@Glorfindel My program finally got to your generalised 1x2k for k=6 (1x12) and confirmed it is minimal yes...I guess it's likely that larger k might be minimal too. W_1x12_25x36

$\endgroup$
  • $\begingroup$ I upvoted, but just note, answering your own question is a shifty way to earn reputation... $\endgroup$ – Feeds Jul 1 '18 at 3:29

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.