Polyomino question

[franktaw at netscape.net]

What is the smallest polyomino that contains all polyominos of size n?
 
For n = 1 or 2, the value is clearly n.  For n = 3, it's 4; either of the following will work:
OOO   OOO
O      O
 
For n = 4, there is a unique size 6 polyomino that works:
OOOO
OO
 
For n = 5, the best I can do is 9:
  O
OOOOO
OOO
I don't know if this is unique; I would be very surprised if 8 is possible.
 
For n = 6, I can get 12:
  OO
OOOOOO
OOOO
Again, this may not be unique, and might possibly be improved.
 
For n = 7, the best I've found is 17:
OOOOO
OOOOOOO
  OOO
   OO
I would not be at all surprised if there is a solution with 16, but I didn't find one.  If 17 is the best, it is not unique; some simple variants of this also work.
 
For n = 8 and beyond, I have no real idea.
----
We can establish a general upper bound from the consideration that a size n polyomino always fits in a k x (n+1-k) box for some k.  It follows that sum_{k=1}^{ceiling(n/2)) n+1-k = ceiling(n/2)*(n+floor(n/2)+1)/2 is an upper bound.  (This can be improved to ceiling(n/2)*(n+floor(n/2)-1)/2 + 1 by noting that, for k>1, the polyomino cannot occupy all four corners of the box.)  This is asymptotically 3/8 n^2.  From the very limited data above, it looks more like 1/4 n^2.  Even that the sequence grows quadratically is not certain, however.  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.
 
Franklin T. Adams-Watters
16 W. Michigan Ave.
Palatine, IL 60067
847-776-7645
___________________________________________________
Try the New Netscape Mail Today!
Virtually Spam-Free | More Storage | Import Your Contact List
http://mail.netscape.com
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.seqfan.eu/pipermail/seqfan/attachments/20060227/ac92ba0d/attachment.htm>