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

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}

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

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