From:reid@durban.berkeley.edu (michael reid)Newsgroups:sci.mathSubject:Re: polyomino classificationKeywords:polyominoDate:14 Apr 92 11:43:48 GMTOrganization:University of California, Berkeley

In article <3007@cvbnetPrime.COM> dwilson@cvbnet.prime.com (David Wilson x5694 4-1600) writes: > I was wondering about the ability to tile certain figures with > polyominoes. The figures I am interested in, with cartesian > descriptions, are: > rectangle (r) [0, a] X [0, b] > halfstrip (hs) R+ X [0, b] > strip (s) R X [0, b] > angled strip (as) ([0, a] X R+) U (R+ X [0, b]) > quadrant (q) R+ X R+ > halfplane (hp) R X R+ > three-quarter plane (tp) (tp)(R X R+) U (R+ X R) > plane (p) R X R you should read the following article: solomon golomb, tiling with polyominoes, journal of combinatorial theory, volume 1, (1966), pages 280-296. he considers all the above possibilities (except for the three-quarter plane), as well as the possibility that the polyomino tiles a larger copy of itself. from his examples, it's clear that he allows the use of mirror images; however, the implications do not change under this interpretation. here's the diagram of implications he gives: rectangle / | / | / v / / half strip / / | / | / v / \/_ bent strip itself | | \ v \ \ quadrant & strip \ \ / \ \ / \ _\/ \/_ _\/ quadrant strip \ / \ / _\/ \/_ half plane | | v plane | | v nothing most of the implications are immediate (e.g. quadrant ==> half plane, since the half plane may be tiled with two quadrants). the only non-obvious implications are: itself ==> quadrant, and bent strip ==> (quadrant &) strip. i will leave these to the reader to prove. if we add the "three-quarter plane" we have the implications: quadrant ==> three-quarter plane ==> plane the first implication is immediate, but i need the axiom of choice to deduce the second. (if anyone can prove the second without the axiom of choice, please let me and sci.math know.) as a hint, try to prove that if a polyomino can cover an N-by-N square for all N (no overlap, and pieces may hang over the edges of the square), then it tiles the plane. i don't know if the implication three-quarter plane ==??==> half plane is valid, but there are a number of potential implications that haven't yet been ruled out, even though there's no apparent reason they should hold. (e.g. itself ==??==> rectangle) [many lines deleted for brevity] > I have been unable to find polyominoes in sets other than these > five, or to fill in the ? in the above table. There may be general golomb classifies all (except the infamous y hexomino) polyominoes of order<6, and finds that many of these sets are unrepresented. > implications I have not worked out (e.g., does a polyomino tiling > the half strip necessarily tile a rectangle?). It would make an > interesting study. indeed.

Newsgroups:sci.mathFrom:umatf071@unibi.hrz.uni-bielefeld.de (0105)Subject:prime boxes of the Y-pentominoDate:Fri, 20 Nov 92 19:25:50 GMTOrganization:Universitaet BielefeldKeywords:tiling

Torsten Sillke, Bielefeld List of all prime rectangles and boxes for the Y-pentomino (.:..). A 'p' following a number indecates a prime box. Rectangles with the Y-pentomino: 10: 5p, 10, 14p, 15, 16p, 19, 20, 21, 23p, 24, 25, 26, 27p, 24-27 + 5*n 15: 10, 14p, 15p, 16p, 17p, 19p, 20, 21p, 22p, 23p, 24-33 + 10*n 20: 5, 9p, 10, 11p, 13p, 14, 15, 16, 17p, 14-17 + 5*n 25: 10, 14, 15, 16, 17p, 18p, 19, 20, 21, 22p, 23p, 24, 25, 26, 27 30: 5, 9p, 10, 11p, 13p, 14, 15, 16, 17, 14-17 + 5*n 35: 10, 11p, 13p, 14, 15, 16, 17, 18p, 19, 20, 21, 22, ... 40: 5, 9, 10, 11, 13, 14, 15, 16, 13-16 + 5*n 45: 9p, 10, 11p, 13p, 14, 15, 16, ... 50: 5, 9, 10, 11, 12p, 13, 9-13 + 5*n 55: 9p, 10, 11, 12p, 13, 14, 15, 16, ... 60: 5, 9, 10, 11, 12p, 13, 14, 15, 16, ... 65: 9, 10, 11, 12p, 13, 14, 15, 16, ... 70: 5, 9, 10, 11, 12p, 13, 14, 15, 16, ... 75: 9, 10, 11, 12p, 13, 14, 15, 16, ... 80: 5, 9, 10, 11, 12p, 13, 14, 15, 16, ... 85: 9, 10, 11, 12p, 13, 14, 15, 16, ... 90: 5, 9, 10, 11, 12p, 13, 14, 15, 16, ... 95: 9, 10, 11, 12p, 13, 14, 15, 16, ... 100: 5, 9, 10, 11, 12, 13, 14, 15, 16, ... /no new prime /all primes found Strips (one side open) with the Y-pentomino: 5p, 6p, 8p, 9p, 10, 11, 12, 8-12 + 5n Strips (two sides open) with the Y-pentomino: 2p, 4, 5p, 4-5 + 2n Boxes with the Y-pentomino: 2 5: 6p, 8p, 10, 11p, 12, 13p, 14, 15p, 10-15 + 6n 3 5: 4p, 8, 9p, 10, 11p, 8-11 + 4n 4 5: 3p, 4p, 5p, 3-5 + 3n 5 5: 4p, 5p, 6p, 7p, 4-7 + 4n 6 5: 2p, 4, 5p, 4-5 + 2n 7 5: 4, 5p, 6, 7p, 4-7 + 4n 8 5: 2p, 3, 2-3 + 2n 9 5: 3p, 4, 5, 3-5 + 3n k 5: 2, 3, 2-3 + 2n (k>10) see 2 5: k, and 3 5: k 2 10: 4p, 5, 6, 7p, ... 3 10: 4, 5, 6p, 7p, ... 2 15: 4p, 5p, 6, 7p, ... 3 15: 4, 5, 6p, 7p, ... /all primes found Impossible hyperboxes with the Y-pentomino: 2*..*2*3*..*3*n (and strip on side open) 2*..*2*3*..*3*5*5 When did I get the results: New (August 1992) 10*23, 10*27, 15*17, 15*19, 15*21, 20*13, 20*17 (September 1992) 30*11, 30*13, 25*17, 35*11, 45*11, 45*9, 55*9, 35*13, 45*13 (October 1992) 15*23, 18*25, 18*35, 3*5*9, 3*5*11, 5*5*6, 5*5*7, 5*7*7, 2*7*10, 3*6*10, 2*7*15 (November 1992) 3*7*10, 3*7*15 Annotations: 15*15 16 solutions without H-symmetry 20*13 1 solution without H-symmetry Question: ========= -- What are the prime rectangles for the one-sided Y-pentomino (.:..), L-pentomino (:...), and P-pentomino (::.)? The case of the L-tetromino is solved. Known prime rectangles: Y-pentomino: 5*10 L-pentomino: 2*5 P-pentomino: 2*5 -- Why is there no 8*5n rectangle tileable with Y-pentominoes? -- Where are the prime hyperboxes? -- Is there anyone interested?