Re: [math-fun] Polyomino question
What is the smallest polyomino that contains all polyominos of size n?
For n = 4, there is a unique size 6 polyomino that works: OOOO OO
XX XXXX also works. it is clear that size 6 is the smallest possible, because the square tetromino and the straight one can overlap in at most two squares.
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.
X XXXXX XXX also works. it is easy to show that size 8 is indeed impossible. note that the "I" and "W" pentominoes can overlap in at most 2 squares, so at least 8 squares are required to accommodate even those two. there are only a handful of ways to overlap them, covering as few as 8 squares, and none of the resulting shapes contain the "X" pentomino: W W W W W W W W WW WW WW WW BBIII IBBII IIBBI IIIBB BBIII IBBII IIBBI IIIBB WW WW WW WW a simple back-of-the-envelope type calculations shows that the only 9-ominoes that work are the two above. what i did was: add a single square to each of the above octominoes in a way that would also accommodate the X pentomino, and check those shapes. there were 15 resulting 9-ominoes (one occurred twice) and only 2 contain all pentominoes. i also tried all ways of overlapping the I and W pentominoes in a single square (9 ways) but none of the shapes contains the X pentomino. i realize that this approach is prone to error, so it would be nice to have independent confirmation. i haven't examined the hexomino case yet, but it seems unlikely to succumb to such a simple analysis. mike
From: Michael Reid <reid@math.ucf.edu>
What is the smallest polyomino that contains all polyominos of size n?
For n = 4, there is a unique size 6 polyomino that works: OOOO OO
XX XXXX
also works. it is clear that size 6 is the smallest possible, because the square tetromino and the straight one can overlap in at most two squares.
No, OO OO won't fit in that one. ___________________________________________________ Try the New Netscape Mail Today! Virtually Spam-Free | More Storage | Import Your Contact List http://mail.netscape.com
Please ignore that. It does work. Franklin T. Adams-Watters 16 W. Michigan Ave. Palatine, IL 60067 847-776-7645 -----Original Message----- From: franktaw@netscape.net
From: Michael Reid <reid@math.ucf.edu>
What is the smallest polyomino that contains all polyominos of size n?
For n = 4, there is a unique size 6 polyomino that works: OOOO OO
XX XXXX
also works. it is clear that size 6 is the smallest possible, because the square tetromino and the straight one can overlap in at most two squares.
No, OO OO won't fit in that one. ___________________________________________________ Try the New Netscape Mail Today! Virtually Spam-Free | More Storage | Import Your Contact List http://mail.netscape.com _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun ___________________________________________________ Try the New Netscape Mail Today! Virtually Spam-Free | More Storage | Import Your Contact List http://mail.netscape.com
participants (2)
-
franktaw@netscape.net -
Michael Reid