Problem of the Month (January 2007)

This month we examine three problems about overlapping polyominoes on a square lattice.

1. Consider a numbered polyomino P, a polyomino with positive integers in each square. Can copies of P be arranged in the plane so that wherever two copies intersect: 1) the numbers in the squares agree, 2) the numbers indicate how many copies of P intersect there, and 3) no two copies of P lie exactly on top of one another? If so, we call this a numbered polyomino intersection. For example, the smallest possible numbered domino intersections are shown below.

What are the minimal arrangements for numbered triominoes? numbered tetrominoes? other polyforms?

2. Consider a polyomino P. We say its non-intersection set is the set of areas that are impossible to achieve by intersecting 2 copies of P in the plane. For a given n, what non-intersection sets are possible? What about other polyforms?

3. An intersecting plane cover is a cover of the plane using copies of one polyomino so that every square is covered exactly twice, and different copies of the polyomino intersect in at most one square. Which polyominoes have intersecting plane covers? What about other polyforms?


ANSWERS

1.

Here are the known numbered intersections for small polyominoes.

Numbered Domino Intersections

12

13

22

14

23

Numbered Straight Triomino Intersections

112

121

113

122

212

114

213

222

133

144

Numbered Bent Triomino Intersections

112

121

113

122

212

114

123

213

222

124

214

133

313

223

232

224

242

233

144

225

333

244

226

227

228

444

Numbered Square Tetromino Intersections

1112

1122

1222

1232

1242

Numbered Straight Tetromino Intersections

1112

1121

1122

1212

1221

2112

1113

1222

2122

1213

2113

1114

2222

1133

1242

1144

1333

1444

Jeremy Galvagni noticed that any straight n-omino numbered with 1's and 2's has a polyomino intersection, by placing them at various locations in an n×n square.


2.

Here are the non-trivial non-intersection sets for small polyominoes.

Polyomino Non-Intersection Sets

4
{3}

5
{3,4}

{4}

6
{5}

7
{5,6}

{5}

{6}

8
{5,6,7}

{5,6}

{5,7}

{6,7}

{5}

{6}

{7}

9
{5,6,7,8}

{5,7,8}

{6,7,8}

{5,7}

{5,8}

{6,7}

{6,8}

{7,8}

{6}

{7}

{8}

10
{5,6,8,9}

{5,7,8,9}

{6,7,8,9}

{5,7,9}

{5,8,9}

{6,7,8}

{6,7,9}

{6,8,9}

{7,8,9}

{5,8}

{6,8}

{6,9}

{7,8}

{7,9}

{8,9}

{7}

{8}

{9}

11
{6,7,8,9,10}

{5,7,8,10}

{5,8,9,10}

{6,8,9,10}

{7,8,9,10}

{5,7,10}

{5,8,10}

{5,9,10}

{6,9,10}

{7,8,9}

{7,8,10}

{7,9,10}

{8,9,10}

{5,9}

{6,9}

{7,8}

{7,9}

{7,10}

{8,9}

{8,10}

{9,10}

{7}

{8}

{9}

{10}

12
{3,5,6,9,10,11}

{5,6,8,9,10,11}

{5,7,8,9,10,11}

{5,6,8,9,11}

{5,6,9,10,11}

{5,7,9,10,11}

{6,8,9,10,11}

{7,8,9,10,11}

{5,6,9,11}

{5,7,10,11}

{5,8,9,11}

{5,9,10,11}

{6,9,10,11}

{7,8,9,10}

{7,8,9,11}

{7,8,10,11}

{7,9,10,11}

{8,9,10,11}

{5,9,10}

{6,8,11}

{6,9,11}

{7,8,9}

{7,8,10}

{7,8,11}

{7,9,10}

{7,9,11}

{7,10,11}

{8,9,10}

{8,9,11}

{8,10,11}

{9,10,11}

{7,8}

{7,9}

{7,10}

{7,11}

{8,9}

{8,10}

{8,11}

{9,10}

{9,11}

{10,11}

{7}

{8}

{9}

{10}

{11}

George Sicherman found non-intersection sets for small polyiamonds and polyhexes.

Polyiamond Non-Intersection Sets

4

5

6

7

8

9

10

11

Polyhex Non-Intersection Sets

4

5

6

7

8

9


3.

Sune Kristian Jakobsen found the covers for the pentominoes and showed that the others are impossible. How many of the hexominoes are possible?

Here are the small intersecting plane covers.

Intersecting Plane Covers

2

3

4

5


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