```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
\
\
\        /              \
\      /                \
_\/  \/_                _\/

\               /
\             /
_\/         \/_

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?
```