From - Thu Jun 17 09:39:12 1999
From: rhoads@paul.rutgers.edu (Glenn)
Newsgroups: rec.puzzles
Subject: Polyomino Tiling Problems
Date: 15 Jun 1999 15:20:55 -0400
Organization: Rutgers University LCSR
Message-ID: <7k692n$bei$1@paul.rutgers.edu>
Definitions:
An n-omino (Polyomino) is formed by attaching n unit squares together
at their edges. E.g. the following is an 8-omino (the Xs represent
unit squares)
XXXXX
XX
X
A set of polyominoes "tiles the plane" if we can cover the entire plane
with copies of the polyominoes in this set so that no two polyominoes
overlap (like a jigsaw puzzle). Note that you are allowed to flip a
polyomino over.
Problems:
1.) Tile the plane usings a 4x4 square and at least one copy of the
following 9-omino.
X X
XXXX
X X
X
2.) Tile the plane using at least one copy of each of the following
polyominoes.
X XXXX
XXX X XX
X XX
X
3.) What is the unique smallest polyomino in which you must flip some
copies over in order to tile the plane?
The tilings in problems 1 and 2 are new and original.
For problem 3, I can give a hint or two to narrow things down
if necessary.
Enjoy!
--
Glenn C. Rhoads email: rhoads@paul.rutgers.edu
Comp. Science Dept. web: http://remus.rutgers.edu/~rhoads/
Rutgers University phone: (732) 445-4869
-----------------------------------------------------------------
Subject: Re: Polyomino Tiling Problems
Date: 17 Jun 1999 14:38:47 GMT
From: whuang@ugcs.caltech.edu (Wei-Hwa Huang)
Organization: California Institute of Technology, Pasadena
Newsgroups: rec.puzzles
References: 1
rhoads@paul.rutgers.edu (Glenn) writes:
>1.) Tile the plane usings a 4x4 square and at least one copy of the
>following 9-omino.
>X X
>XXXX
> X X
> X
>2.) Tile the plane using at least one copy of each of the following
>polyominoes.
> X XXXX
>XXX X XX
> X XX
> X
>3.) What is the unique smallest polyomino in which you must flip some
>copies over in order to tile the plane?
1. The following figure tiles the plane without rotation or reflection.
a a
aaaa
aba
....bab
....bbbb
....bccb
....cc
ddddc
dcccc
dd
dd
2. The following figure tiles the plane without rotation or reflection.
ddd
ddd x
c daaaaxxx
ccdabbaax
ccddcbaa
ccccb a
bbb
bbb
3. All polyominoes up to 5 tile without reflection easily. I think all
the hexominoes tile without reflection. There is at least one
septomino that doesn't tile the plane, so I suspect the answer is a
septomino.
--
Wei-Hwa Huang, whuang@ugcs.caltech.edu, http://www.ugcs.caltech.edu/~whuang/
---------------------------------------------------------------------------
Is there a metonym in this sentence?
-----------------------------------------------------------------
From: rhoads@paul.rutgers.edu (Glenn)
The tilings are a lot prettier than the ascii picture.
I put up a gif of them at
http://remus.rutgers.edu/~rhoads/tiling1.gif
http://remus.rutgers.edu/~rhoads/tiling2.gif
>3. All polyominoes up to 5 tile without reflection easily. I think all
> the hexominoes tile without reflection.
Correct.
>There is at least one septomino that doesn't tile the plane,
>so I suspect the answer is a septomino.
I've always used the term heptomino for the 7-ominos but
yes, at least one heptomino doesn't tile the plane (to be
precise, 4 do not tile the place. One of these 4 has a hole.)
Your suspicion is correct; the answer is a hepomino/septomino.
-----------------------------------------------------------------
Subject: Polyomino Tiling Problem: Helpful info.
Date: 21 Jun 1999 00:28:13 -0400
From: rhoads@paul.rutgers.edu (Glenn)
Organization: Rutgers University LCSR
Newsgroups: rec.puzzles
The remaining problem is
3.) What is the unique smallest polyomino in which you must flip some
copies over in order to tile the plane?
As mentioned previously, the answer is a heptomino (7-omino).
You can eliminate most of the heptominoes very quickly by making use
of the "Conway criterion" and thus avoid the tediousness of checking
all the heptominoes by hand.
Def: A polygon satisfies the Conway criterion if you can divide up the
perimeter into six segments labeled clockwise A,B,C,D,E,F such that
1) A and D are translations of each other (A and D could be empty)
2) B, C, E, and F are symmetric with respect to a 180 degree rotation
about their center point. (at least of each of the pairs B-C and E-F
must be non-empty)
Thm. Any polygon satisfying the Conway criterion tiles the plane
without flipping the polygon over.
To illustrate this theorem, consider the following randomly chosen
heptomino.
--y
| y
--yyyyy
| | | |
-------
| |
y---x
y | |
yyyyy
This heptomino satisfies the conway criterion. The y-segments are
translations of each other. The left segment is symmetric with
respect to a 180 degree rotation (one of B or C is empty). The
other piece can be broken up into two pieces that have 180 degree
symmetry -- I've marked the point where you break up this piece
into two with an x.
To tile the plane, translate this heptomino so that the parallel
y-segments "line up" and then repeat this to get an infinite strip.
C
CCC
C
BCC
BBB
B
ABB
AAA
A
AA
Take a copy of this strip, rotate it 180 degrees, and fit it next to
the original strip so that the segments with 180 degree rotational
symmetry line up.
C DD
CCCD
CDDD
BCCEED
BBBE
BEEE
ABBFFE
AAAF
AFFF
AA F
Now you have a two-piece wide infinite strip that tiles the plane
by translation.
All the heptominoes except seven satisfy the Conway criterion. One
of these has a hole which obviously can't tile the plane. This
leaves six remaining heptominoes. You can check these six by hand
to determine which is the one that you must flip over in order to
tile the plane (note: three of these remaining six do not tile the
plane and two can tile the plane without flipping over any copies).
--
Glenn C. Rhoads email: rhoads@paul.rutgers.edu
Comp. Science Dept. web: http://remus.rutgers.edu/~rhoads/
Rutgers University phone: (732) 445-4869
3.) What is the unique smallest polyomino in which you must flip some
copies over in order to tile the plane?
As mentioned before, the smallest polyomino is a heptomino (7-omino).
We can eliminate the one heptomino with a hole since it obviously
doesn't tile the plane. Of the remaining 107 heptominoes, all of
them satisfy the "Conway criterion" and hence tile the plane without
flipping a copy over EXCEPT the following six heptominoes. (I.e.
The answer is one of the following heptominoes.)
XX XX X X X X
X X XX XXXX XX X
XX X X X X XXXX
XX X XX X X X
XX X XX
Which one is it?
--
Glenn C. Rhoads email: rhoads@paul.rutgers.edu
Comp. Science Dept. web: http://remus.rutgers.edu/~rhoads/
Rutgers University phone: (732) 445-4869
-----------------------------------------------------------------
Subject: Re: Polyomino Tiling Problem: BIG hint
Date: 30 Jun 1999 01:44:42 -0400
From: reid@cauchy.math.brown.edu (michael reid)
Organization: Brown University
Newsgroups: rec.puzzles
[...]
* *
****
*
the basic translational unit being
aab
abbbb
aabccb
daadcc
ddddc
dcc
the answer is:
* *
*****
+--+ + +--+ + +--+ +--+--+--+--+--+--+--+ +--+ + +--+ + +--+--+
| | | | | | | | | | | | | | |
+--+--+ +--+ + +--+ + +--+--+ +--+ +--+--+ + +--+ + +--+ +--+-
| | | | | | | | | | | | | | | |
+ +--+--+ + +--+ + +--+ +--+--+--+--+--+--+--+ +--+ + +--+ + +-
| | | | | | | | | | | | | |
+--+--+--+--+ +--+ + +--+ + +--+--+ +--+ +--+--+ + +--+ + +--+
| | | | | | | | | | | | | | |
+ +--+ +--+--+ + +--+ + +--+ +--+--+--+--+--+--+--+ +--+ + +--+
| | | | | | | | | | | | | |
+--+--+--+--+--+--+ +--+ + +--+ + +--+--+ +--+ +--+--+ + +--+ +
| | | | | | | | | | | | | |
+--+--+ +--+ +--+--+ + +--+ + +--+ +--+--+--+--+--+--+--+ +--+ +
| | | | | | | | | | | | |
+ +--+--+--+--+--+--+--+ +--+ + +--+ + +--+--+ +--+ +--+--+ + +-
| | | | | | | | | | | | | | |
+ + +--+--+ +--+ +--+--+ + +--+ + +--+ +--+--+--+--+--+--+--+ +-
| | | | | | | | | | | | |
+ +--+ +--+--+--+--+--+--+--+ +--+ + +--+ + +--+--+ +--+ +--+--+
| | | | | | | | | | | | | |
+ +--+ + +--+--+ +--+ +--+--+ + +--+ + +--+ +--+--+--+--+--+--+-
| | | | | | | | | | | | | |
+--+ + +--+ +--+--+--+--+--+--+--+ +--+ + +--+ + +--+--+ +--+ +-
| | | | | | | | | | | | | | |
+--+ + +--+ + +--+--+ +--+ +--+--+ + +--+ + +--+ +--+--+--+--+-
| | | | | | | | | | | | | |
+ + +--+ + +--+ +--+--+--+--+--+--+--+ +--+ + +--+ + +--+--+ +-
| | | | | | | | | | | | | | | |
+--+ +--+ + +--+ + +--+--+ +--+ +--+--+ + +--+ + +--+ +--+--+-
| | | | | | | | | | | | | | |
+--+--+ + +--+ + +--+ +--+--+--+--+--+--+--+ +--+ + +--+ + +--+-
| | | | | | | | | | | | | |
+--+--+--+ +--+ + +--+ + +--+--+ +--+ +--+--+ + +--+ + +--+ +-
| | | | | | | | | | | | | | | |
+--+ +--+--+ + +--+ + +--+ +--+--+--+--+--+--+--+ +--+ + +--+ +
| | | | | | | | | | | | | |
+--+--+--+--+--+ +--+ + +--+ + +--+--+ +--+ +--+--+ + +--+ + +-
the basic translational unit being
d
dd
d
d
aaaaacddc
abbaccccc
b
b
bb
b
if i counted correctly, there are 39 heptominoes that tile the plane
by translation only, 62 that tile using 180 degree rotations ("conway
tilers"), 3 that tile in other ways, and 4 that don't tile at all.
the last 7 are those that glenn gave above, and the one with a hole.
the third heptomino with an interesting tiling is
** **
***
a translational unit is
b
bb
b
bb
aabaa
aaa
mike