Problem of the Month (January 2007)

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

Problem #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?

Problem #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?

Problem #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

Problem #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.

Problem #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}