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@math.ucdavis.edu