Polyomino question

[Dean Hickerson]

Franklin T. Adams-Watters asked:

> What is the smallest polyomino that contains all polyominos of size n?
... 
> 2n-2 is a simple lower bound, since fitting the general "line" polyomino
> requires n in a single row (or column), while the general "snake"
> polyomino has only 2 squares in any given row.
 
This bound can be improved by considering 'linear' polyominoes of other
slopes.  For  0 <= s <= 1,  let P(s,n) be an n-omino which approximates a
line of slope s.  E.g. the straight line polyomino is P(0,n), and the snake
is P(1,n).  P(1/2,n) looks like a subset of this:

ooo
  ooo
    ooo
      ooo
        ooo
          ooo
             ...

P(2/3,n) could be a subset of either of these; I don't know which will give
the best lower bound:

oooo                    ooo
   o                      oo
   oooo                    ooo
      o                      oo
      oooo                    ooo
         o                      oo
         oooo                    ooo
            o                      oo
            oooo                    ooo
                ...                    ...

P(1/2,n) can overlap P(0,n) in at most 3 squares, and overlap P(1,n) in at
most 6 squares, so any polyomino that contains P(0,n), P(1,n), and P(1/2,n)
has at least  n + (n-2) + (n-3-6) = 3n-11  squares.  

If we also include P(1/3,n), we need at least 4n-31 squares, if I've
maximized the intersections correctly:  

  slopes        maximum intersection
0       1               2
0       1/2             3
1       1/2             6
0       1/3             4
1       1/3             4
1/2     1/3             12

I'll leave it to someone else to figure out the best choice for P(s,n),
a general formula for the maximum intersection of P(s,n) and P(t,n),
and the choice of slopes which gives the best lower bound for n-ominoes.

Dean Hickerson
dean at math.ucdavis.edu