If we overlap rectangles of size 1xN, 2xN/2, 3xN/3, ... sqrtNxsqrtN, the resulting staircase structure will have area about N * (1 + 1/2 + 1/3 + ... + 1/sqrtN), roughly N * (log(sqrtN) + gamma), about N logN / 2. Another interesting family to try would be S-shaped ominoes, with three segments at right angles. Rich -----Original Message----- From: math-fun-bounces+rschroe=sandia.gov@mailman.xmission.com on behalf of Dean Hickerson Sent: Mon 2/27/2006 5:30 PM To: seqfan@ext.jussieu.fr; math-fun@mailman.xmission.com Subject: [math-fun] Re: Polyomino question 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 _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun