Problem of the Month (November 2005)

Given a shape S and a positive integer n, what is the smallest number of non-overlapping congruent copies of S that can be arranged in the plane so that each copy of S touches exactly n others? The answer often depends on what we mean by "touch". This can mean "touch at at least one point", "touch at exactly one point", or "touch along part of an edge".

For example, 4 squares can touch 3 others at at least one point, 12 squares can touch 3 others at exactly one point, and 14 squares can touch 3 others along part of an edge:

touching

touching at 1 point

touching along an edge
(found by Ed Pegg)

Can you show that 25 squares can each touch 4 other squares? Can you show that 48 squares can each touch 4 other squares in exactly 1 point? Can you show that no finite collection of squares can each touch 4 squares along an edge? What are the corresponding minimum numbers for other shapes? Another way to look at this is: For a given planar regular graph, what is the smallest polyomino that can be arranged to have that adjacency graph? For definiteness, here we require the shapes to conform to the square grid and to touch along part of an edge. For example, there is a 8-omino that can realize the smallest 3-regular graph:

(found by Olexandr Ravsky)

What are the smallest polyominoes (or other polyforms) that can realize the other small planar 3-regular and 4-regular graphs?


ANSWERS

For various shapes, here are the fewest known that can be arranged so that each touches exactly 3 or 4 others:

Fewest Number Known of a Shape to
Have Regular Adjacency Graph
ShapeTouching 3 othersTouching 4 others
any1 pointedgeany1 pointedge
41214 (EP) 25 (BG)48 (BG)
488 152624
488 101620
488 15 (CP)2232
48 (GS)8 101624
486 (CP) 10 (CP)1816
466 101612
46 (CP)6 141416
4?4 (OR) ???
4455
4416 55
12 (CP)12 (CP)16
1616

EP = Ed Pegg
BG = Branko Grünbaum
OR = Olexandr Ravsky
CP = Corey Plover GS = George Sicherman

For the small planar 3-regular graphs, here are the smallest known polyforms that can have this adjacency graph:

Smallest Known Polyominoes and Polyhexes
to Have Given 3-Regular Adjacency Graph
GraphMin SizePolyomino ArrangementMin SizePolyhex Arrangement
8 (OR) 4 (GS)
4 (CP) 4 (CP)
9 ??
5 4
3 2
3 3
3 3
5 3
4 4
5 4
5 4
5 3
12 ??
14 ??
3 (JD) 2

OR = Olexandr Ravsky
GS = George Sicherman
CP = Corey Plover
JD = Joe DeVincentis

For the small planar 4-regular graphs, here are the smallest known polyominoes that can have this adjacency graph:

Smallest Known Polyominoes and Polyhexes
to Have Given 4-Regular Adjacency Graph
GraphMin SizePolyomino ArrangementMin SizePolyhex Arrangement
????
6 6 (GS)
????
14 (JD) 6
????
????
????
????
8 (JD)??

GS = George Sicherman
JD = Joe DeVincentis


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