3
$\begingroup$

Inspired by Polyomino T hexomino and rectangle packing into rectangle

See also series Tiling rectangles with F pentomino plus rectangles and Tiling rectangles with Hexomino plus rectangle #1

Previous puzzle in this series Tiling rectangles with Heptomino plus rectangle #3

Next puzzle in this series Tiling rectangles with Heptomino plus rectangle #6

The goal is to tile rectangles as small as possible with the given heptomino, in this case number 4 of the 108 heptominoes. 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 of the given heptomino will tile.

Example with the $1\times 1$ you can tile a $2\times 6$ as follows:

1x1_2x6

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

I found 31 more but lots of them can be found by 'expansion rules' or pattern variations. I considered component rectangles of width 1 through 11 and length to 32 but my search was far from complete.

List of known sizes:

  • Width 1: Lengths 1 to 15, 18, 22
  • Width 2: Lengths 2 to 9, 11, 15, 21
  • Width 3: Lengths 4, 5, 7
  • Width 4: Length 5

Most of these could be tiled by hand using logic rather than trial and error.

$\endgroup$
2
$\begingroup$

Here is a general solution for $2\times n$ rectangles, with $n$ odd and not divisible by $7$.

$2\times1$, in $2\times12$
enter image description here

$2\times3$, in $4\times40$
enter image description here

$2\times5$, in $6\times40$
enter image description here

and so on.

The size is $n+1$ by $2nk+10$, where $k\equiv n^{-1} \mod 7$.

Of course this general solution is not always optimal. Here are some better solutions:

$2\times1$

in $2\times9$
enter image description here

$2\times3$

in $8\times10$
enter image description here

Here is a general solution for $2\times n$ rectangles with $n$ even.

$2\times2$, in $4\times12$
enter image description here

$2\times4$, in $6\times26$
enter image description here

$2\times6$, in $8\times82$
enter image description here

$2\times8$, in $10\times26$
enter image description here

$2\times10$, in $12\times110$
enter image description here
and so on.

The size is $n+2$ by $2nk+10$, where $k\equiv (\frac{n}{2})^{-1} \mod 7$.

Again this general solution is not always optimal:

$2\times6$

in $8\times34$
enter image description here

Here is a general solution for $3\times n$ rectangles, where $n$ is not divisible by 3.


$3\times4$, in $8\times31$
enter image description here

$3\times5$, in $20\times38$
enter image description here

$3\times7$, in $14\times10$
enter image description here
and so on.

The size is $2nr$ by $lcm(7,n)+3$, where $r\equiv n^{-1} \mod 3$.

There is in fact a general solution for any $a\times b$ where $\gcd(a,b)=1$.

As $a$ and $b$ are co-prime, we can find positive $r$,$s$ such that $ra-sb=1$. This is equivalent to $(a-s)b-(b-r)a=1$. Doubling these equations, we can also find $t$,$u$ such that $ta-ub=2$ and $(a-u)b-(b-t)a=2$. The smallest $t$,$u$ are actually $t=(2r)\%b$ and $u=(2s)\%a$ where $\%$ is the modulo operator. This allows for the following solution:
enter image description here

$\endgroup$
  • $\begingroup$ 1x2=2x9, 2x2=4x12, 2x3=8x10, 2x4=6x26, 2x5=6x40, 2x6=8x34, 2x8=10x26 all minimal. 2x7 has a much smaller one than your generalisation, but 2x9=10x82, 2x11=12x54 and 2x15=16x40 are minimal (I think your formula gives those...). There is a nice smaller one for 2x21. Your 3x7=10x14 is minimal but 3x4 and 3x5 are not. Your axb generalisation seems to be minimal for 4x5=21x35. $\endgroup$ – theonetruepath Jun 24 '18 at 1:46
1
$\begingroup$

Let's start with a few generalizable $1 \times n$ solutions, similar to the ones here, corresponding to Type B, Type A resp. Type C:

enter image description here

Note that they can be subdivided, e.g. the first one into $1 \times 4$ and $1 \times 2$ (though the latter won't be optimal; I'll leave it for another contender); in general,

you'll need less rows as padding and the solution will have a height of $n + 1$.

Here are the solution sizes:

Type A (middle): uses $2k$ heptominoes, works when $n$ divides $7k$. Solution size is $(n + 1) \times (7k + n)$, or equivalently $(n + 1) \times (\text{lcm}(7,n) + n)$.
Type B (left): uses $2k+1$ heptominoes, works when $n$ divides $7k + 1$. Solution size is $(n + 1) \times (7k + 6)$. The minimum value of $k$ is $7^{-1} \pmod n$ (this is a so-called modular multiplicative inverse), so the solution size is $(n + 1) \times (7(7^{-1} \pmod n) + 6)$.
Type C (right): uses $2k+1$ heptominoes, works when $n$ divides $7k + 6$. Solution size is $(n + 1) \times (7k + 1 + 2n)$. The minimum value of $k$ is $7^{-1} \pmod n - 1$, so the solution size is $(n + 1) \times (7(7^{-1} \pmod n) - 6 + 2n)$.

$\endgroup$

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.