From: Yura Aksyonov [SMTP:aksyonov@starlab.ifmo.ru]
Date: 1999-02-22
Subject: Y-pentomino
Hello Torsten!
> >But I still have some questions about one-sided Y-pentomino and in your
> >results this problem is still opened. It is easy to prove that boxes can
> >be only (5*M)x(5*N) and since there is known 5x10 prime, other primes
> >can be just (10*M+5)x(10*N+5).
> How did you prove this?
Fairly easy to prove:
Consider pentominos that adjacent to a border with I4 part. They can't be
placed uninterruptedly, also they can't be separated by more than one cell.
# # #1
#1 #1 #11
#11 #11 #1
#1x #1 #1
#1x #1 #x
#2x or #x or #x
#21 #x #x
#2 #2 #2
#2 #22 #22
# #2 #2
#2 #2
In place xxx no Y-pentominos can be placed (actually in second variant they
can but without continuation).
So boundary Y-pentominos can be separated ONLY by one cell.
Consider also that corner Y-pentominos can be placed only like this:
###### but not like this: ######
#a #aaaa
#aa #xxa
#a #
#a
#
Consequently both sides of box should divide by 5, only (5*M)x(5*N) rectangle
may be filled with Y-pentominos. Furthermore there's set of fixed Y-pentominos
placed at border. Here's example with 10x5 box:
abbbb
aa.bc
a...c
a..cc
....c
d....
dd..e
d...e
df.ee
ffffe
Fixed pentominos somehow accelerate computing.
The fact number two is even simplier. There is known prime 5x10, all not odd
(5*M)x(5*N) boxes can be composed of 5x10 prime, so other primes may be only
odd i.e. (10*M+5)x(10*N+5).
[...]
Finally few words about myself. I'm Yura Aksyonov, male, age 21, 5th year student
of St. Petersburg (Russia) Institute of Fine Mechanics and Optics (IFMO). My
speciality is programming and my special interest is amusing mathematics.
Regards
Yura
-----------------------------------------------------------------------
From: Yura Aksyonov [SMTP:aksyonov@starlab.ifmo.ru]
Subject: Handed Y-pentomino problem is solved
Date: 1999-03-06
Hello Torsten.
Finally I proved impossibility of tiling (5+10*N)x(5+10*N)
box with handed Y-pentominos. The proof is again very
simple. And I like it, it's beautiful.
============================================================
First, consider dissection of rectangle into crosses (maybe
they're called X-pentominos but I don't know). As example I
show the dissection of 15x15 rectangle.
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|00|00|00 00 00| |00|00 00 00| |00|00 00 00|
+ +--+--+ +--+ +--+--+ +--+ +--+--+ +--+
|00 00| |00| | |00| | |00|00|
+ +--+ +--+--+ +--+ +--+--+ +--+ +--+--+
|00| aa | | | | | | |00|
+--+--+ +--+ +--+--+ +--+ +--+--+ +--+ +
|00| | | | | | | | |00 00|
+--+ +--+--+ +--+ +--+--+ +--+ +--+--+ +
| | | | | | | | |00|
+--+ +--+ +--+--+ +--+ +--+--+ +--+ +--+
|00| | | | | | | | |
+ +--+--+ +--+ +--+--+ +--+ +--+--+ +--+
|00 00| | | | | | | | |00|
+ +--+ +--+--+ +--+ +--+--+ +--+ +--+--+
|00| | | | | | | |00|
+--+--+ +--+ +--+--+ +--+ +--+--+ +--+ +
|00| | | | | | | | |00 00|
+--+ +--+--+ +--+ +--+--+ +--+ +--+--+--+
| | | | | | | | |00|
+--+ +--+ +--+--+ +--+ +--+--+ +--+ +--+
|00| | | | | | | | |
+ +--+--+ +--+ +--+--+ +--+ +--+--+ +--+
|00 00| | | | | | | | |00|
+ +--+ +--+--+ +--+ +--+--+ +--+ +--+--+
|00| | | | | | | |00|
+--+--+ +--+ +--+--+ +--+ +--+--+ +--+--+
|00|00| | |00| | |00| |00|00|
+--+ +--+--+ +--+ +--+--+ +--+ +--+--+--+
|00 00 00|00| |00 00 00|00| |00 00 00|00|00|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
Fig. 1.
All partial crosses are covered by fixed pentominos (I
mentioned them in previous proof) and other area consist of
complete crosses.
There is formula for getting the number of crosses in 5Mx5N
rectangle.
5x5 - 1
5x10 - 4
5x15 - 7
5x5N - 3N - 2
5Mx5N - M*(3N - 2) + (M - 1)*2N = 5MN - 2M - 2N
Now I claim that if there's possible tiling, all pentominos
except border ones can be paired so each pair covers pair of
adjacent crosses. And since for odd rectangle there is odd
number of crosses, no tiling is available for it.
To prove pairness of pentominos consider empty cross, upper
and left crosses of which are covered. Consider the most
left cross with given characteristics (if there are some of
them, consider highest). On the fig. 1 corresponding cross
is marked with aa.
Now, let's work with the chosen cross. First fact is that
cross to the southwest is filled, otherwise chosen cross is
not most left with given characteristics. I showed it on
fig. 2.
|00| |00 00 00| | |
+--+ +--+--+ +--+ +--+
|00 00 00|xx|00| |
+--+ +--+ +--+--+ +--+
|00|00| | | |
+ +--+--+ +--+ +--+--+
00 00| | | | |
+ +--+ +--+--+ +--+ +
|00| | | |
+--+--+ +--+ +--+--+ +
| | | | | | |
+--+ +--+--+ +--+ +--+
| | | | |
Fig. 2.
Now consider pentomino that covers xx cell. There are at
most two variants of placing it (depending on whether lower
and right crosses are free or not).
First variant:
|00| |00 00 00| | |
+--+ +--+--+ +--+ +--+
|00 00 00|11|00| |
+--+ +--+ +--+--+ +--+
|00|00|22 11 11| | |
+ +--+--+ +--+ +--+--+
00 00|22|11| | |
+ +--+ +--+--+ +--+ +
|00|22 22 11| | |
+--+--+ +--+ +--+--+ +
| | |22| | | |
+--+ +--+--+ +--+ +--+
| | | | |
Fig. 3.
There is only one variant to place second pentomino. And 1
and 2 covers exactly two crosses.
Second variant:
|00| |00 00 00| | |
+--+ +--+--+ +--+ +--+
|00 00 00|11|00| |
+--+ +--+ +--+--+ +--+
|00|00|11 11 11|11| |
+ +--+--+ +--+ +--+--+
00 00| |xx| | |
+ +--+ +--+--+ +--+ +
|00| | | |
+--+--+ +--+ +--+--+ +
| | | | | | |
+--+ +--+--+ +--+ +--+
| | | | |
Fig. 4.
Here are five variants to place second pentomino that
covers xx cell:
1) 1 2) 1 3) 1 4) 1 5) 1
1111 1111 1111 1111 1111
2222 2222 2 2 2
2 2 2222 22 2
2 22
2 2
3, 4 and 5 variants are obviously impossible.
And 1 is impossible too:
000100
001111
002222
0xxx2
It is impossible to cover xxx cells.
So, again only one variant is possible (second). And again
two pentominos covers exactly two crosses.
That's it. I proved that if it's possible to fill rectangle
with pentominos, interior ones could be combined into pairs.
Consequently no odd tiling is possible.
============================================================
Now consider 10x10 rectangle.
+--+--+--+--+--+--+--+--+--+--+
|00|00|00 00 00| |00|00 00 00|
+ +--+--+ +--+ +--+--+ +--+
|00 00| |00| | |00|00|
+ +--+ +--+--+ +--+ +--+--+
|00| | | | |00|
+--+--+ +--+ +--+--+ +--+ +
|00| | | | | |00 00|
+--+ +--+--+ +--+ +--+--+ +
| | | | | |00|
+--+ +--+ +--+--+ +--+ +--+
|00| | | | | |
+ +--+--+ +--+ +--+--+ +--+
|00 00| | | | | |00|
+ +--+ +--+--+ +--+ +--+--+
|00| | | | |00|
+--+--+ +--+ +--+--+ +--+--+
|00|00| | |00| |00|00|
+--+ +--+--+ +--+ +--+--+--+
|00 00 00|00| |00 00 00|00|00|
+--+--+--+--+--+--+--+--+--+--+
Fig. 5.
Tiling of crosses with Y-pentominos is equivalent of tiling
following area with "dominos":
oo
oooo
oooo
oo
There are 8 variants. And for any other area tiling can be
reduced to tiling some other area with "dominos".
For example, tiling of NxN quadrant is equivalent to tiling
of following area:
oo
ooooo
ooooooo
oooooooooo
oooooooooooo
. . . . .
No wonder that you couldn't classified NxN tilings, there
are really lots of variants.
============================================================
And finally, I don't understand your statement about n*N
strips:
"if it tiles a n*N (strip) -> 5|n" ???
For one side open strips n can be 5, 10, 15 ...
But for two side open strips n can be 2, 4, 5, 6, 7, ...
(all naturals except 1 and 3)
============================================================
Now I think all problems of handed Y-pentomino are solved.
Regards,
Yura