<HTML><BODY><DIV style='font-family: "Verdana"; font-size: 10pt;'><DIV>
<DIV><FONT face="courier new, courier, mono">What is the smallest polyomino that contains all polyominos of size n?</FONT></DIV>
<DIV><FONT face="Courier New"></FONT> </DIV>
<DIV><FONT face="Courier New">For n = 1 or 2, the value is clearly n. For n = 3, it's 4; either of the following will work:</FONT></DIV>
<DIV><FONT face="Courier New">OOO OOO</FONT></DIV>
<DIV><FONT face="Courier New">O O</FONT></DIV>
<DIV><FONT face="Courier New"></FONT> </DIV>
<DIV><FONT face="Courier New">For n = 4, there is a unique size 6 polyomino that works:</FONT></DIV>
<DIV><FONT face="Courier New">OOOO</FONT></DIV>
<DIV><FONT face="Courier New">OO</FONT></DIV>
<DIV><FONT face="Courier New"></FONT> </DIV>
<DIV><FONT face="Courier New">For n = 5, the best I can do is 9:</FONT></DIV>
<DIV><FONT face="Courier New"> O</FONT></DIV>
<DIV><FONT face="Courier New">OOOOO</FONT></DIV>
<DIV><FONT face="Courier New">OOO</FONT></DIV>
<DIV><FONT face="Courier New">I don't know if this is unique; I would be very surprised if 8 is possible.</FONT></DIV>
<DIV><FONT face="Courier New"></FONT> </DIV>
<DIV><FONT face="Courier New">For n = 6, I can get 12:</FONT></DIV>
<DIV><FONT face="Courier New"> OO</FONT></DIV>
<DIV><FONT face="Courier New">OOOOOO</FONT></DIV>
<DIV><FONT face="Courier New">OOOO</FONT></DIV>
<DIV><FONT face="Courier New">Again, this may not be unique, and might possibly be improved.</FONT></DIV>
<DIV><FONT face="Courier New"></FONT> </DIV>
<DIV><FONT face="Courier New">For n = 7, the best I've found is 17:</FONT></DIV>
<DIV><FONT face="Courier New">OOOOO</FONT></DIV>
<DIV><FONT face="Courier New">OOOOOOO</FONT></DIV>
<DIV><FONT face="Courier New"> OOO</FONT></DIV>
<DIV><FONT face="Courier New"> OO</FONT></DIV>
<DIV><FONT face="Courier New">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.</FONT></DIV>
<DIV><FONT face="Courier New"></FONT> </DIV>
<DIV><FONT face="Courier New">For n = 8 and beyond, I have no real idea.</FONT></DIV>
<DIV><FONT face="Courier New">----</FONT></DIV>
<DIV><FONT face="Courier New">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.</FONT></DIV>
<DIV> </DIV>
<DIV><FONT face="courier new, courier, mono">Franklin T. Adams-Watters<BR>16 W. Michigan Ave.<BR>Palatine, IL 60067<BR>847-776-7645</FONT></DIV></DIV></DIV>
<hr style="MARGIN-TOP:10px" >
<b>Try the New Netscape Mail Today!</b><br />
Virtually Spam-Free | More Storage | Import Your Contact List<br /><a href="http://mail.netscape.com">http://mail.netscape.com</a>
</BODY></HTML>