Problem of the Month (December 2018)

This month we investigate miscellaneous polyomino problems. We say P ⊆ Q if P can be packed inside Q. We say P ⊂ Q if P ⊆ Q and P ≠ Q.

Fix a polyomino P. We say a finite polyomino Q is critical if P ⊄ Q, and Q ⊂ R implies P ⊂ R. In other words, P won't fit inside Q, but if you add any square to Q then P will fit. Given P, is there a critical Q? If so, what is the smallest such Q? Is there a largest such Q, or are there arbitrarily large Q? What if P is a collection of polyominoes, none of which fit in Q, but any larger polyomino contains some polyomino from P?

Fix a n-omino P. Is there an infinite polyomino Q with the property that the only n-omino P with P ⊂ Q is P? What if P is a collection of polyominoes, which are the only n-ominoes that are subsets of Q?

What is the smallest polyomino that can be surround by exactly n copies of itself, with each of those copies being surrounded by exactly m copies of itself? Here "surrounded" means all the edges, but not necessarily the corner points.

How many ways are there to tile a rectangle with a set of polyominoes? In general, this is a hard problem. But the problem of how many ways an n×k rectangle can be tiled for fixed k with a fixed set of polyominoes can be solved by recurrence relations. For example, the number of ways a_n an n×1 rectangle can be tiled with 1×1 and 2×1 rectangles clearly satisfies the recurrence formula a_n = a_n-1 + a_n-2. What are the recurrence formulas for other small cases?

Given a polyomino, what is the shortest linear absolute value inequality in two variables whose solution set is that polyomino? Are such inequalities always possible?

ANSWERS

George Sicherman, Michael Peake, Gordon Atkinson, Kang Jin Cho, and Maurizio Morandi sent results.

Here are the best known results. Here "AL" stands for arbitrarily large finite polyominoes.

Small Polyominoes
Polyominoes Smallest
Critical Largest
Critical

none

Tetrominoes
Polyominoes Smallest
Critical Largest
Critical
AL

AL

none

AL
AL (GS)

AL
AL
none
   (GS) (GS)
   (GS) (GS)
   (GS)
   (GS) (GS)
Pentominoes
Polyominoes Smallest
Critical Largest
Critical
(GA) AL (GA)
(GS) (GS)
(GS)
? ?
(GS) (GS)
? ?
none (GA)
? ?
? ?
none (GA)
(GS) AL (GS)
? ?
(GA) AL (GS)
(GA) ?
(GA) ?
(GA) (GS)
(GA)
(GA) AL (GS)

Here are the known results.

Triominoes

Polyominoes Infinite Polyomino

Tetrominoes

Polyominoes Infinite Polyomino

(GS)

1 or 2 Pentominoes

Polyominoes Infinite Polyomino

(GS)
(GS)
3 Pentominoes

Polyominoes Infinite Polyomino

(GS)

(GS)

(GS)

(GS)

(GS)
(GS)

(GS)

Here are the best known results.

n \ m 4 5 6 7 8
3
(MM)
4
(GS)
(MM)
(GS)
5
(GS)
(GS)
(MM)
(GS)
6
(MM)
(GS)
(MM)
7
(GS)
(GS)
(MM)
8
(GS)
(MM)
(MM)
(GS)
9
(MM)
(GS)
10
(MM)
(GS)

n \ m	4	5	6	7	8
3					(MM)
4		(GS)		(MM)	(GS)
5	(GS)	(GS)		(MM)	(GS)
6	(MM)	(GS)			(MM)
7	(GS)		(GS)	(MM)
8	(GS)	(MM)	(MM)	(GS)
9		(MM)	(GS)
10		(MM)	(GS)

Here are the known results.

Width 1

Polyominoes Coefficients Sequence
1 1 1, 2, 3, 5, 8, 13, 21
1 0 1 1, 1, 2, 3, 4, 6, 9
0 1 1 0, 1, 1, 1, 2, 2, 3
1 1 1 1, 2, 4, 7, 13, 24, 44
1 0 0 1 1, 1, 1, 2, 3, 4, 5
0 1 0 1 0, 1, 0, 2, 0, 3, 0
1 1 0 1 1, 2, 3, 6, 10, 18, 31
0 0 1 1 0, 0, 1, 1, 0, 1, 2
1 0 1 1 1, 1, 2, 4, 6, 9, 15
0 1 1 1 0, 1, 1, 2, 2, 4, 5
1 1 1 1 1, 2, 4, 8, 15, 29, 56
Width 2

Polyominoes Coefficients Sequence
1 1 1, 2, 3, 5, 8, 13, 21
3 1 –1 2, 7, 22, 71, 228, 733, 2356
1 1 3 1 –1 –1 1, 1, 4, 9, 16, 36, 81
2 0 1 –2 1 –1 1, 2, 4, 7, 11, 26, 52
0 0 2 0, 0, 2, 0, 0, 4, 0
1 4 2 1, 5, 11, 33, 87, 241, 655
2 0 1 1, 2, 5, 11, 24, 53, 117
0 0 3 0, 0, 3, 0, 0, 9, 0
1 1 1, 2, 3, 5, 8, 13, 21
1 2 1, 3, 5, 11, 21, 43, 85
0 1 1 0, 1, 1, 1, 2, 2, 3
0 1 2 0, 1, 2, 1, 4, 5, 6
1 1 0 3 1 –2 –2 –1 0 1 1, 1, 1, 4, 9, 16, 25
1 2 –1 2 0 –1 1, 2, 3, 8, 14, 30, 55
0 1 2 2 –1 –3 0 –1 –1 1 0, 0, 1, 1, 0, 1, 4
0 0 2 2 0 0 0 –1 0, 0, 2, 1, 0, 4, 6
0 0 0 2 0, 0, 0, 2, 0, 0, 0
1 0 4 2 2 1, 1, 5, 11, 19, 43, 99
1 1 4 2 1, 2, 7, 15, 32, 79, 185
0 0 2 1 0 –1 0, 0, 1, 2, 0, 1, 6
0 0 2 2 0, 0, 2, 2, 0, 4, 8
1 1 1 1, 1, 3, 5, 9, 17, 31
1 1 1, 2, 3, 5, 8, 13, 21
0 0 1 0, 0, 1, 0, 0, 1, 0
0 1 2 0, 0, 2, 0, 2, 4, 2

Gordon Atkinson and Kang Jin Cho explained why every polyomino has a solution. The best known solutions are shown below:

Small Polyominoes

|x| + |x–1| + |y| + |y–1| = 2
|x| + |x–2| + |y| + |y–1| = 3
|x| + |x–3| + |y| + |y–1| = 4
a+b = |a–b|, where
a = |x–2| + |x| + |y–1| + |y| – 3
and b = |x–1| + |x| + |y–2| + |y| – 3
(MP) (GA)
|x| + |x–4| + |y| + |y–1| = 5
|x| + |x–2| + |y| + |y–2| = 4
a+b = |a–b|, where
a = |x–3| + |x| + |y–1| + |y| – 4
and b = |x–2| + |x–1| + |y–2| + |y| – 3
(MP) (GA)
a+b = |a–b|, where
a = |x–3| + |x| + |y–1| + |y| – 4
and b = |x–1| + |x| + |y–2| + |y| – 3
(MP) (GA)
a+b = |a–b|, where
a = |x–2| + |x| + |y–1| + |y| – 3
and b = |x–3| + |x–1| +|y–2| + |y–1| – 3
(GA)
Pentominoes

|x| + |x–5| + |y| + |y–1| = 6
a+b = |a–b|, where
a = |x–4| + |x| + |y–1| + |y| – 5
and b = |x–1| + |x| + |y–2| + |y| – 3
a+b = |a–b|, where
a = |x–2| + |x| + |y–2| + |y| – 4
and b = |x–3| + |x| + |y–1| + |y| – 4

(KJC)
a+b = |a–b|, where
a = |x–2| + |x| + |y–2| + |y–1| – 3
and b = |x–4| + |x–1| +|y–1| + |y| – 4
a+b = |a–b|, where
a = |x–2| + |x–1| + |y–3| + |y| – 4
and b = |x–3| + |x| +|y–1| + |y| – 4
|x| + |x–3| + |y| + |y–2| – 5 = a –|a|, where
a = |2x+y–5| +|2x–y–1| – 2
(MP)
a+b = |a–b|, where
a = |x–1| + |x| + |y–3| + |y| – 4
and b = |x–3| + |x| +|y–1| + |y| – 4

(KJC)
a+b = |a–b|, where
a = |x–1| + |x–2| + |y–3| + |y| – 4
and b = |x–3| + |x| + |y–1| + |y–2| – 4
a+b = |a–b|, where
a = |x–4| + |x| + |y–1| + |y| – 5
and b = |x–2| + |x–1| + |y–2| + |y| – 3

(KJC)

Alex Rower also did hexominoes.

If you can extend any of these results, please e-mail me. Click here to go back to Math Magic. Last updated 12/16/18.