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

Shape	Touching 3 others			Touching 4 others
Shape	any	1 point	edge	any	1 point	edge
	4	10 (MM)	14 (EP)	25 (BG)	48 (BG)	∞
	4	8	8	15	24 (MM)	24
	4	8	8	10	16	20
	4	8	8	15 (CP)	22	24 (MM)
	4	6 (MM)	8	10	12 (MM)	20 (MM)
	4	8	6 (CP)	10 (CP)	16 (MM)	16
	4	6	6	10	12 (MM)	12
	4	6 (CP)	6	10 (MM)	14	16
	4	6 (MM)	4 (OR)	?	?	?
	4	4	∞	5	5	∞
	4	4	14 (MM)	5	5	∞
	12 (CP)	12 (CP)	16	∞	∞	∞
	16	16	∞	∞	∞	∞