The Eleven X Pentomino problem
Ed Pegg Jr
without overlap.
Putting 11 X pentominoes on a 8x8 toroidal grid without overlap is
impossible. Several polyformists have modified their programs to prove
this. Multiple long computer proofs are available.
I'm hoping to find a clever pigeonhole principle type proof. I haven't
found one, though, and a lot of very good problem solvers haven't
found one either, yet.
Does a short proof exist for this problem?
--Ed Pegg Jr, www.mathpuzzle.com
Jyrki Lahtonen
>
> It isn't too hard to put 10 X pentominoes on an 8x8 toroidal grid
> without overlap.
5 squares and an 'X pentomino' might more aptly be called a '+ pentomino'
(as what I would call an 'X pentomino' has a disconnected interior and
would immediately divide the problem into two separate parts concerning
white or black chessboard squares only)
>
> Putting 11 X pentominoes on a 8x8 toroidal grid without overlap is
> impossible. Several polyformists have modified their programs to prove
> this. Multiple long computer proofs are available.
>
> I'm hoping to find a clever pigeonhole principle type proof. I haven't
> found one, though, and a lot of very good problem solvers haven't
> found one either, yet.
I am not an expert on this type of problems, but might not a pigeonhole
type proof immediately extend to the infinite plane from the 8X8 torus?
As we immediately see that the plane can be fully tiled using these pentominoes,
there's no hope.
May be I misunderstood, what is meant by a "pigeonhole type proof" in this context?
I thought that would be something like the classical solutions to the problems
of "covering the chessboard with 2 diagonally opposite corner squares removed
with domino tiles" and "preservation of parity of various types of tiles, when
covering a rectangular area by 2x2 and 4x1 blocks"
>
> Does a short proof exist for this problem?
I can't help you there
>
> --Ed Pegg Jr, www.mathpuzzle.com
--
Jyrki Lahtonen, docent
Department of Mathematics,
University of Turku,
FIN-20014 Turku, Finland
http://users.utu.fi/lahtonen
tel: (02) 333 6014
Nick Wedd
<e...@mathpuzzle.com> writes
I observe that a 5x5 toroidal grid can be exactly covered by X
pentominoes. And so, therefore, can a 10x10 grid, etc.
I don't see how this helps, though.
Nick
--
Nick Wedd
MangoMan
> In article <3B67772B...@mathpuzzle.com>, Ed Pegg Jr
> <e...@mathpuzzle.com> writes
> >It isn't too hard to put 10 X pentominoes on an 8x8 toroidal grid
> >without overlap.
> >
> >Putting 11 X pentominoes on a 8x8 toroidal grid without overlap is
> >impossible. Several polyformists have modified their programs to prove
> >this. Multiple long computer proofs are available.
>
> I observe that a 5x5 toroidal grid can be exactly covered by X
> pentominoes. And so, therefore, can a 10x10 grid, etc.
>
I don't understand exactly what an 8x8 toroidal grid is?
Does it have area of 64 squares?
if so, how can 11 * 5 (squares/pentomino) = 55 squares cover it?
Is this problem limited to a "donut" shape?
MangoMan
Pentomino Fuzion Puzzles
http://home.earthlink.net/~kenzelt
Patrick Hamlyn
>Nick Wedd wrote:
>
>> In article <3B67772B...@mathpuzzle.com>, Ed Pegg Jr
>> <e...@mathpuzzle.com> writes
>> >It isn't too hard to put 10 X pentominoes on an 8x8 toroidal grid
>> >without overlap.
>> >
>> >Putting 11 X pentominoes on a 8x8 toroidal grid without overlap is
>> >impossible. Several polyformists have modified their programs to prove
>> >this. Multiple long computer proofs are available.
>>
>> I observe that a 5x5 toroidal grid can be exactly covered by X
>> pentominoes. And so, therefore, can a 10x10 grid, etc.
>>
>
>I don't understand exactly what an 8x8 toroidal grid is?
Toroidal means rows and columns both wrap. ie the X-pentominos can be placed
across the border. Or, there aren't any borders. Whichever you prefer.
>Does it have area of 64 squares?
yes
>if so, how can 11 * 5 (squares/pentomino) = 55 squares cover it?
Ed made no mention of covering the grid. There will be gaps. You just have to
place the pentominos without overlapping each other. Should be easy, since you
have 9 spare squares which you can leave uncovered :)
>Is this problem limited to a "donut" shape?
That's one way of representing it. I prefer to draw an 8x8 grid with a note that
it has the property that square A1 neighbours A2, A8, B1 and H1 etc. I find it
difficult to draw donut shapes on paper :>
--
Patrick Hamlyn posting from Perth, Western Australia
Windsurfing capital of the Southern Hemisphere
Nick Wedd
<ken...@earthlink.net> writes
>I don't understand exactly what an 8x8 toroidal grid is?
An 8x8 grid, wrapped around into a torus.
>Does it have area of 64 squares?
Yes.
>if so, how can 11 * 5 (squares/pentomino) = 55 squares cover it?
10 pentominoes can be placed so that they don't overlap, but then you
can't fit any more in.
I am the person who used the word "cover". You can put 5 X-pentominoes
on a 5x5 toroidal grid, and then there is no space left, so they do
cover it.
>Is this problem limited to a "donut" shape?
Yes.
Nick
--
Nick Wedd
Chas F Brown
Mmmmmm.... donut shaped X pentomino covering....
Cheers - Homer Simpson
---------------------------------------------------
C Brown Systems Designs
Multimedia Environments for Museums and Theme Parks
---------------------------------------------------
Jim Ferry
-------
I've come up with a simple proof. It uses a lemma whose proof
is unrelated to everything else, so I'll dispense with that first.
-----
Lemma: a polyomino with F squares admits at most Ceiling(F/2)
isolated squares, i.e., squares that have no vertices in common
with other isolated squares.
---
Proof of Lemma: Draw in all the edges and vertices of all the
squares in a polyomino. If there are F squares (or *faces*),
E edges, and V vertices, then
(1) V - E + F + G = 1,
where G is the genus of the polyomino (i.e., the number of holes).
This follows directly from the fact that V - E + F' = 2 for a
simple polyhedron. We simply set F' = F + G + 1: the holes and
the outside of the polyomino count as faces.
A polyomino has exactly 4F - N edges, where N is the number of
internal edges (i.e., those that connect squares). N must be
at least F-1 so that the polyomino is connected, so let
N = F-1 + X, X being the number of excess internal edges. Then
(2) E = 3F + 1 - X.
Combining (1) and (2) yields
V = 2F + 2 - (G + X). In particular, V >= 2F + 2.
Now let I be the number of isolated squares. I <= 4V since the
vertices of isolated squares are disjoint. Therefore
I <= Floor(V/4) <= Floor((F+1)/2) = Ceiling(F/2). Q.E.D.
-----
Main Proof: An 8x8 toroidal grid admits a checkerboard coloring.
A configuration with 11 crosses must have at least 6 crosses of
the same parity. We'll assume there are at least 6 BC-crosses
(Black Centered crosses), and examine the ramifications of
placing them without overlap.
First, let us re-tile the grid with the 32 2-squares (i.e.,
squares of area 2) that circumscribe the white squares and are
oriented at 45 degrees to the original grid. One can put four
of these squares together to make an 8-square. The possible
placements of these 8-squares on the new grid coincide with the
possible placements of BC-crosses on the original grid if we
identify each 8-square with the BC-cross it circumscribes.
(It may be helpful to draw an picture.)
Thus we have converted the problem of placing 6 BC-crosses
without overlap on the original grid to placing 6 8-squares
without overlap on the new grid. Any such placement leaves out
an area of 16 consisting of 8 2-squares, which we can view as a
collection of polyominoes. The 1-squares which these 2-squares
circumscribe are the possible locations of the centers of the
WC-crosses. WC-crosses centered there (and only there) will
not overlap with the BC-crosses. The question is, when will
they overlap with each other?
And the answer is, they will overlap iff their corresponding
2-squares share (at least) a vertex. Invoking the above lemma,
we see that if the placement of the six 8-squares leaves
polyominoes consisting of a1, a2, ..., and ak 2-squares (where
a1+a2+...+ak = 8), then the maximal number of non-overlapping
WC-crosses is
MWC = Ceiling(a1/2) + Ceiling(a2/2) + ... + Ceiling(ak/2)
= 4 + (the number of odd ai)/2.
We shall prove below that placing 6 8-squares can never leave
either a monomino nor a straight triomino. We'll now use these
facts to complete the proof.
First, note that if there are exactly 8 BC-crosses, there are
no leftover 2-squares for WC-crosses. If there are exactly 7
BC-crosses, there are 4 leftover 2-squares. For these to
contain 4 WC-crosses, each would have to be a monomino, but
monominoes cannot occur. This leaves the main case of 6 BC-
crosses and 8 left-over 2 squares in which 5 WC-crosses are to
be placed.
The above formula for MWC dictates that there must be at least
2 odd ai. Without the possibility of ai=1, this means that at
least one ai must be 3, and that there are at most 2 ai. This
in turn implies that all the polyominoes involved must actually
achieve the maximal number of isolated squares, which rules out
the possibility of the L-triomino. Therefore, the impossibility
of the straight triomino completes the proof.
---
Monomino Lemma:
To leave a monomino requires 4 8-squares, one to bound each side
of the monomino. There is only one configuration which does this
(up to symmetry). In this configuration, there are 4 possible
placements for a fifth 8-square, the centers of which are the
1-squares adjacent to the antipode of the monomino. Placing the
fifth 8-square at any one of these locations covers the other
three, leaving no room for the sixth 8-square.
Straight Triomino Lemma:
To leave a straight triomino requires 6 8-squares. There is only
one possible configuration. Trying to accomplish it on an 8 by 8
toroid results in overlap of the two 8-squares which hang off the
long sides of the triomino.
-----
Notes: the proof glosses over a few details of topology: the
I <= Ceiling(F/2) lemma is for an infinite plane, but we use it
on a toroid. However, polyominoes on a toroid are merely
polyominoes on a plane with extra connectivity, which can only
decrease I. Similarly, considerations about the number of
8-squares required to bound the monomino or straight triomino
were based on a plane, but it's easy to see that the 8x8 toroid
is too big for the 8-squares to wrap around and bound either
polyomino on 2 sides.
-------
| Jim Ferry | Center for Simulation |
+------------------------------------+ of Advanced Rockets |
| http://www.uiuc.edu/ph/www/jferry/ +------------------------+
| jferry@[delete_this]uiuc.edu | University of Illinois |
Jim Ferry
> V = 2F + 2 - (G + X). In particular, V >= 2F + 2.
G and X being non-negative, make that "V <= 2F + 2."