[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
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
But that family doesn't cover all size N polyominoes. For example, N=6, and rounding all fractions up, this gives us a candidate cover: OOOOOO OOO OO But it isn't possible to fit: OOOO O O into this shape. Franklin T. Adams-Watters -----Original Message----- From: Schroeppel, Richard <rschroe@sandia.gov> 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. ... ___________________________________________________ Try the New Netscape Mail Today! Virtually Spam-Free | More Storage | Import Your Contact List http://mail.netscape.com
I was trying to establish a lower bound, like Dean. For that, I only need to show some subset of the polyominos that requires the alleged area. On the other hand, I haven't actually shown the required minimum, but merely guessed a subset and a shape. Continuing in this unrigorous vein, I'll guess that the set of S shapes needs area O(N sqrtN), and that generalized combs (a strip backbone, with tines of varying lengths and positions on the backbone) require nearly N^2, perhaps O(N^2-eps). As an upper bound, presumably we can show that every N-omino fits in a bounding box of total dimension N+1. The set of bounding boxes can be fit into a Nevada-shape of height N and width ceiling(N/2), with area about 3/8 * N^2. Rich -----Original Message----- From: math-fun-bounces+rschroe=sandia.gov@mailman.xmission.com on behalf of franktaw@netscape.net Sent: Mon 2/27/2006 8:04 PM To: math-fun@mailman.xmission.com Subject: Re: [math-fun] Re: Polyomino question But that family doesn't cover all size N polyominoes. For example, N=6, and rounding all fractions up, this gives us a candidate cover: OOOOOO OOO OO But it isn't possible to fit: OOOO O O into this shape. Franklin T. Adams-Watters -----Original Message----- From: Schroeppel, Richard <rschroe@sandia.gov> 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. ... ___________________________________________________ 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
participants (3)
-
Dean Hickerson -
franktaw＠netscape.net -
Schroeppel, Richard