Black and white tiles in the shower at a Palo Alto Hyatt got me working on
random polyominoes. I think it's a great topic for high school algebra
class. Paraphrasing from a short, unpublished paper I wrote in 1988:
b = number of tiles in body of figure (= order of polyomino)
n = number of tiles in neighborhood to define figure
r = number of distinct orientations
p = probability of a tile being figure color
q = 1-p = probability of a tile being background color
P = probability of finding a given figure in any orientation and "centered"
on a specified tile = r p^b q^n
A convenient set to analyze is the polyominoes through order 5. Some have
identical b, n and r values, and therefore have the same chance of
occurring for all p. For example, the T and Z tetrominoes have b=4, n=8,
and r=4. Because of cases like this, the 21 polyominoes through order 5
are described by only 16 probability equations.
For each of the 16 classes, it is not hard to find the p and P where the
chance of occurrence peaks, and where its curve touches or crosses the
curves of the other classes. It's easy to generalize the method to several
colors, or to non-connected figures.
Some problems, most of which I don't know the answer to, are:
1. If we look only for black polyominoes on a white background, the P curve
for most polyominoes is asymmetric. For polyominoes with b=n, it is
symmetric. An easy example is the 4X4 16-omino. Is there a lower-order
polyomino whose P curve is symmetric? Are there any other 16-ominoes with
a symmetric P curve? What is the smallest irregular (define: r=8)
polyomino with a symmetrical curve?
2. Is there any polyiamond or polyhex whose b, n and r values are the same
as those of some polyomino?
3. The point at p=1/2 where the P curves for four classes of polyomino
intersect is difficult to graph, because of the relative values of the
curves. What scaling of the axes would show the area around this point
clearly? (Members of those 4 classes are: straight tetromino; L pentomino;
T, U & Z pentominoes; X pentomino.)
4. For polyominoes of any given order, there is a minimum and a maximum n.
Consider a histogram of the n values for a given b. Is this histogram
always unimodal, for every b? If so, what is the most common n, as a
function of b, as b increases without bound? If not, what is the smallest
order of polyomino with a multimodal histogram?
5. What is the smallest order polycube whose P curve is symmetric? What
are the two smallest polycubes whose P curves intersect?
6. It is easy to show that p of the peak = b / (b+n). Using this, it is
easy to show that the peak likelihood is P_peak = r (b^b n^n) /
(b+n)^(b+n). The symmetry of this formula in b and n leads to the
following conclusion. Consider two polyominoes, the b of one equal to the
n of the other, and vice versa. The symmetry of the P_peak equation tells
us that the likelihood curves of the two shapes have the same maximum
value. Can you find any such pairs of polyominoes? Better yet, can you
find a way of generating an infinite family of such pairs? One idea is
pairs of rectangles, but this does not work to make an infinite family.
With some effort, you can show there are only 5 integer rectangle pairs
where the area of one is the perimeter of the other, and vice versa:
1 X 34 and 7 X 10
1 X 38 and 6 X 13
1 X 54 and 5 X 22
2 X 10 and 4 X 6
2 X 13 and 3 X 10
(The related 3-dimensional problem of surface-volume pairs of bricks is
much harder. Rich Schroeppel and Dean Hickerson worked some theory on
this. My computer search found there are 246 pairs of different bricks,
plus 10 bricks whose S = V.)
