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