From: reid@durban.berkeley.edu (michael reid)
Newsgroups: sci.math
Subject: Re: polyomino classification
Keywords: polyomino
Date: 14 Apr 92 11:43:48 GMT
Organization: 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.math
From: umatf071@unibi.hrz.uni-bielefeld.de (0105)
Subject: prime boxes of the Y-pentomino
Date: Fri, 20 Nov 92 19:25:50 GMT
Organization: Universitaet Bielefeld
Keywords: 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?