Tiling rectangles with N pentomino plus rectangles

Question

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

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

There are at least 22 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.

My program found another tiling for this one. So now there are thirteen left to find. Should I put hints on these as to the rectangles which have tilings? — theonetruepath, Apr 26 '18 at 10:54
This is identical to mine challenges, however, let it be. I decided not to post them, because they do not have so much solutions or have infinitely many. This one has infinitely many. — Somnium, May 07 '18 at 22:14

Jaap Scherphuis · Answer 1 · 2018-05-08T07:08:51.597

8

Here is my (now improved) solution for $2\times3$ rectangles plus N-pentomino(s):

It is a $7\times8$ rectangle, using four N-pentominoes and six $2\times3$ rectangles.

And here is my solution for $2\times5$ rectangles plus N-pentomino(s):

It is a $7\times10$ rectangle, using two N-pentominoes and six $2\times5$ rectangles.

Here are some more solutions, though for these I used computer assistance.

$1\times6$ rectangles plus N-pentomino(s):

It is an $8\times13$ rectangle, using 16 N-pentominoes and four $1\times6$ rectangles.

The solutions given by others for $1\times3$ and $1\times5$ generalise to give solutions for $1\times(5k+3)$ rectangles and $1\times 5k$ rectangles.

A $(5k+4)\times(10k+5)$ rectangle can be filled with $2k+1$ N-pentominoes and $10k+5$ rectangles of size $1\times(5k+3)$.
Similarly, a $(5k+1)\times 10k$ rectangle can be filled with $2k$ N-pentominoes and $10k$ rectangles of size $1\times 5k$.

Here is a solution for the $1\times7$ rectangle plus N-pentomino(s), which also generalises in the same way to $1\times(5k+2)$ :

It is an $(5k+3)\times(10k+5)$ rectangle, using $2k+1$ N-pentominoes and $10k+5$ rectangles of size $1\times(5k+2)$ .

There is also a family of solutions for $2\times(10k+7)$ rectangles.

A $(20k+16)\times(20k+15)$ rectangle can be filled with $8k+6$ N-pentominoes and $20k+15$ rectangles of size $2\times(10k+7)$.

edited May 08 '18 at 07:08

answered Apr 26 '18 at 11:20

Jaap Scherphuis

53,019
7
120
208

The 2x5 is minimal, but the 2x3 is not. So 12 left to find. – theonetruepath Apr 27 '18 at 00:27
@theonetruepath I have now improved the $2\times3$ solution. – Jaap Scherphuis Apr 28 '18 at 07:03
2x3 now minimal, as is the 1x6. There is a smaller 1x7. Your 1x3 generalisation to 1x8 (9x15) is minimal too. In fact a very similar design will give you the minimal 1x7 tiling. I'll do a summary at some point. – theonetruepath Apr 29 '18 at 08:19
Your 2x7 is not minimal either, although it's not far off. – theonetruepath Apr 29 '18 at 08:25
1x(5k+2) and 2x(10k+5) should be easily generalizable as well. – phenomist May 08 '18 at 06:51
I have now improved and generalised the 1x7 solution to 1x(5k+2). – Jaap Scherphuis May 08 '18 at 07:09
The 1x7 is now minimal. – theonetruepath May 08 '18 at 10:40

Glorfindel · Answer 2 · 2018-05-22T10:56:54.190

4

Here's an attempt for 1x4:

11x5 = 55 squares

and another one for 1x5:

10x6 = 60 squares

and one for 1x9:

14x14 = 196

and one for 1x10, smaller than the generalized 1x5k solution:

12x15 = 180

and one for 1x11; it looks like this sequence is somehow generalizable as well. N has a nice shape, it seems.

13x18 = 234

1x12:

18x16 = 288

Here is the minimal solution for $2 \times 7$, which generalizes to $2 \times (10k + 7)$ and is just a little bit smaller than the one discovered by Jaap:

15x15 = 255 (generalized: $(20k + 15) \times (20k + 15)$)

edited May 22 '18 at 10:56

answered Apr 23 '18 at 15:22

Glorfindel

28,033
9
96
142

Both optimal. My tiling for the 1x4 is slightly different (still a 5x11). Most of these tilings are unique. – theonetruepath Apr 23 '18 at 16:33
1x9 and 1x10 both optimal. 1x11 probably optimal... I will have to run my program on that to check, I went only to 10x10 – theonetruepath May 08 '18 at 09:44
13x18 for the 1x11 is optimal too. – theonetruepath May 08 '18 at 11:09
16x18 for the 1x12 also minimal – theonetruepath May 08 '18 at 12:00

Somnium · Answer 3 · 2018-05-08T14:05:12.820

2x2

This is smallest rectangle with N pentomino and O tetromino.

$8 \times 20$:

2x4

This is smallest rectangle with N pentomino and 2x4 rectangle:

$16 \times 16$:

3x4

This is smallest rectangle with N pentomino and 3x4 rectangle:

$14 \times 16$:

3x5

$16 \times 30$:

In general, there exists solution for each $2 \times n$ rectangle (note that these also give implicit solutions for all $1 \times n$ rectangles):

Generalized solution for $2 \times n$ for odd $n$:
Resulting rectangle will be $2n \times (2 + lcm(5, n))$

Generalized solution for $2 \times n$ for even $n$:
Resulting rectangle will be $(4 + n + kn) \times (2 + n + 2mn)$ where $k \equiv 2n^{-1} \pmod{5}$ and $m \equiv 3n^{-1} \pmod{5}$
This one also solves for odd $n$ because you can join two rectangles to get even length, so for now this is most general solution.

General solution for any rectangle with coprime sides $a \times b, a>1,b>1$:

Resulting rectangle will be $(an + bm) \times (an + bm - 1 + lcm(5, a, b))$ where $n \equiv a^{-1}\pmod{b}$ and $m \equiv b^{-1}\pmod{a}$

This gives $16 \times 30$ solution for $3 \times 5$, $22 \times 126$ solution for $3 \times 7$ and $21 \times 40$ solution for $3 \times 4$

2x2, 2x4, 3x4 all minimal. Minimality of the generalisations unclear... until my program gets a bit further — theonetruepath, May 08 '18 at 12:29
@theonetruepath Added 3x5, cannot check for minimality for now. Also added very general solution. — Somnium, May 09 '18 at 08:19
Your 3x5 is probably minimal, my program is up to area 456 now and a few more rectangles to check before I can confirm it. Progress is slow at these sizes... I like the general solution for axb with a,b co-prime. — theonetruepath, May 09 '18 at 09:40

score 3 · Answer 4 · answered Apr 17 '18 at 06:48

3

Let's give it a try:

$ 1 \times 2 $

Area: $2 \times 7 = 14$

$ 1 \times 3 $

Area: $4 \times 5 = 20$

answered Apr 17 '18 at 06:48

athin

34,177
4
70
221

Yup both are minimal. Nice colours! Only 14 to go... – theonetruepath Apr 17 '18 at 08:07

score 2 · Answer 5 · edited Apr 17 '18 at 06:53

2

A 4 x 4 area can be tiled by two N pentominos and three 1 x 2 rectangles.

1 1 n n
n n n 2
N N N 2
3 3 N N

A 5 x 5 area can be tiled by two N pentominos and five 1 x 3 rectangles.

1 1 1 n n
2 n n n 5
2 3 3 3 5
2 N N N 5
4 4 4 N N

edited Apr 17 '18 at 06:53

Glorfindel

28,033
9
96
142

answered Apr 17 '18 at 06:14

Blckknght

965
7
8

1

[Add spoiler tags please.] Neither of these is optimal. – theonetruepath Apr 17 '18 at 06:24

score 1 · Answer 6 · answered Jun 05 '18 at 21:20

Since the solutions are so widely spread across the answers, here's an attempt to put them all together in a Community Wiki answer. If somebody has a better way of formatting this inside a spoiler, be my guest.

$1 \times n$

1 x n solution found by, image
1 x 1 2 x 4 = 8 .theonetruepath
1 x 2 2 x 7 = 14 .athin
1 x 3 4 x 5 = 20 .athin
1 x 4 5 x 11 = 55 .Glorfindel
1 x 5 6 x 10 = 60 .Glorfindel
1 x 6 8 x 13 = 104 .Jaap Scherphuis
1 x 7 8 x 15 = 120 .Jaap Scherphuis
1 x 9 14 x 14 = 196 .Glorfindel
1 x 10 12 x 15 = 180 .Glorfindel
1 x 11 13 x 18 = 234 .Glorfindel
1 x 12 16 x 18 = 288 .Glorfindel
1 x 5k 5k+1 x 10k .Jaap Scherphuis
1 x 5k+2 5k+3 x 10k+5 .Jaap Scherphuis
1 x 5k+3 5k+4 x 10k+5 .Jaap Scherphuis

$2 \times n$

2 x n solution found by, image
2 x 2 8 x 20 = 160 .Somnium
2 x 3 7 x 8 = 56 .Jaap Scherphuis
2 x 4 16 x 16 = 256 .Somnium
2 x 5 7 x 10 = 70 .Jaap Scherphuis
2 x 7 15 x 15 = 225 .Glorfindel
2 x 2k see below (*) .Somnium
2 x 2k+1 4k+2 x 2+lcm(5,2k) .Somnium
2 x 10k+7 20k+15 x 20k+15 .Glorfindel

(*): solution size for $2 \times 2k$ is $(4 + 2k + 2lk) \times (2 + 2k + 4mk)$ where $l \equiv 4k^{-1} \pmod{5}$ and $m \equiv 6k^{-1} \pmod{5}$.

$3 \times n$ and others

3 x n solution found by, image
3 x 4 14 x 16 = 224 .Somnium
3 x 5 16 x 30 = 480 .Somnium
a x b (*) see below (*) .Somnium

(*): $a$ and $b$ must be coprime and greater than 1. The solution size is $(an + bm) \times (an + bm - 1 + lcm(5, a, b))$ where $n \equiv a^{-1}\pmod{b}$ and $m \equiv b^{-1}\pmod{a}$.

The 1x8 is missing, but the smallest solution is the generalized one for 1x5k+3 found by Jaap Scherphuis. — Glorfindel, Jun 05 '18 at 21:24
(I know the alignment doesn't work on mobile; please view this answer in full site mode.) — Glorfindel, Jun 05 '18 at 21:32

Tiling rectangles with N pentomino plus rectangles

6 Answers6

$1 \times n$

$2 \times n$

$3 \times n$ and others

Linked