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.

1.

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?

2.

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?

3.

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.

4.

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 an an n×1 rectangle can be tiled with 1×1 and 2×1 rectangles clearly satisfies the recurrence formula an = an-1 + an-2. What are the recurrence formulas for other small cases?

5.

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.

1.

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

Small Polyominoes
PolyominoesSmallest
Critical
Largest
Critical
none
 
Tetrominoes
PolyominoesSmallest
Critical
Largest
Critical
AL
AL
none
 
 AL
 AL (GS)
 
 
 
 
 AL
 AL
 none
   (GS) (GS)
   (GS) (GS)
   (GS)
   (GS) (GS)
Pentominoes
PolyominoesSmallest
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)


2.

Here are the known results.

Triominoes
PolyominoesInfinite Polyomino
 

Tetrominoes
PolyominoesInfinite Polyomino
 
 
  (GS)
   
   
   
1 or 2 Pentominoes
PolyominoesInfinite Polyomino
 
 
 
 
 
  (GS)
  (GS)
3 Pentominoes
PolyominoesInfinite Polyomino
   
    (GS)
   
   
    (GS)
   
    (GS)
   
   
    (GS)
   
   
    (GS)
    (GS)
   
   
    (GS)
   
   


3.

Here are the best known results.

n \ m45678
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)


4.

Here are the known results.

Width 1
PolyominoesCoefficientsSequence
  1 11, 2, 3, 5, 8, 13, 21
  1 0 11, 1, 2, 3, 4, 6, 9
  0 1 10, 1, 1, 1, 2, 2, 3
    1 1 11, 2, 4, 7, 13, 24, 44
  1 0 0 11, 1, 1, 2, 3, 4, 5
  0 1 0 10, 1, 0, 2, 0, 3, 0
    1 1 0 11, 2, 3, 6, 10, 18, 31
  0 0 1 10, 0, 1, 1, 0, 1, 2
    1 0 1 11, 1, 2, 4, 6, 9, 15
    0 1 1 10, 1, 1, 2, 2, 4, 5
      1 1 1 11, 2, 4, 8, 15, 29, 56
Width 2
PolyominoesCoefficientsSequence
1 11, 2, 3, 5, 8, 13, 21
  3 1 –12, 7, 22, 71, 228, 733, 2356
  1 1 3 1 –1 –11, 1, 4, 9, 16, 36, 81
  2 0 1 –2 1 –11, 2, 4, 7, 11, 26, 52
0 0 20, 0, 2, 0, 0, 4, 0
  1 4 21, 5, 11, 33, 87, 241, 655
  2 0 11, 2, 5, 11, 24, 53, 117
  0 0 30, 0, 3, 0, 0, 9, 0
  1 11, 2, 3, 5, 8, 13, 21
  1 21, 3, 5, 11, 21, 43, 85
  0 1 10, 1, 1, 1, 2, 2, 3
  0 1 20, 1, 2, 1, 4, 5, 6
  1 1 0 3 1 –2 –2 –1 0 11, 1, 1, 4, 9, 16, 25
  1 2 –1 2 0 –11, 2, 3, 8, 14, 30, 55
  0 1 2 2 –1 –3 0 –1 –1 10, 0, 1, 1, 0, 1, 4
  0 0 2 2 0 0 0 –10, 0, 2, 1, 0, 4, 6
0 0 0 20, 0, 0, 2, 0, 0, 0
  1 0 4 2 21, 1, 5, 11, 19, 43, 99
  1 1 4 21, 2, 7, 15, 32, 79, 185
  0 0 2 1 0 –10, 0, 1, 2, 0, 1, 6
  0 0 2 20, 0, 2, 2, 0, 4, 8
  1 1 1 1, 1, 3, 5, 9, 17, 31
  1 11, 2, 3, 5, 8, 13, 21
  0 0 10, 0, 1, 0, 0, 1, 0
  0 1 20, 0, 2, 0, 2, 4, 2


5.

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)


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.