prime packings of the L-pentomino: Torsten Sillke, BI, 18.05.93
list complete
update 1999: handed primes found by M. Reid
Prime: 2x5, 7x15,
3x5x5, 3x3xZ,
3x3x3x30, 3x3x3x45.
handed Primes: 2x5, 13x55, 15x39, 17x35, 19x25.
Impossible:
3xZ,
5xu with u odd,
3x3xN,
3x3x...x3x15,
3x3x...x3x5u with u not 0 (mod 3)
impossible handed rectangles:
{7,9,11}x5(2n+1), ??? correct ???
13x{15,25,35,45}, 15x{15,17,19,...,37}, 17x25
Proof: impossibility of 3xZ, trivial
Proof: impossibility of 5xu with u odd, <- 5*N dissects in 2*5 rectangles
Proof: impossibility of 3x3xN, dies out (backtrack)
Proof: impossibility of 3x3x...x3x15
Look at the one-dimensional projection. If the were a packing, then
there must be a non-negative integral solution of the following
linear system with x[25] odd: A*x = 0
A := array([
[2,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,-1]
[1,2,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,-1],
[1,1,2,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,-1],
[1,1,1,2,0,0,0,0,0,0,0,0,2,1,1,1,0,0,0,0,0,0,0,0,-1],
[0,1,1,1,2,0,0,0,0,0,0,0,0,2,1,1,1,0,0,0,0,0,0,0,-1],
[0,0,1,1,1,2,0,0,0,0,0,0,0,0,2,1,1,1,0,0,0,0,0,0,-1],
[0,0,0,1,1,1,2,0,0,0,0,0,0,0,0,2,1,1,1,0,0,0,0,0,-1],
[0,0,0,0,1,1,1,2,0,0,0,0,0,0,0,0,2,1,1,1,0,0,0,0,-1],
[0,0,0,0,0,1,1,1,2,0,0,0,0,0,0,0,0,2,1,1,1,0,0,0,-1],
[0,0,0,0,0,0,1,1,1,2,0,0,0,0,0,0,0,0,2,1,1,1,0,0,-1],
[0,0,0,0,0,0,0,1,1,1,2,0,0,0,0,0,0,0,0,2,1,1,1,0,-1],
[0,0,0,0,0,0,0,0,1,1,1,2,0,0,0,0,0,0,0,0,2,1,1,1,-1],
[0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,2,1,1,-1],
[0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,2,1,-1],
[0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,2,-1],
]);
The proof of Peter L. Montgomery (Internet: pmontgom@math.orst.edu),
that this system has no non-negative integral solution:
show (*) x[4] + x[8] + x[12] + x[13] + x[17] + x[21] = 0.
This can be checked by adding the first 15 rows of the matrix to get
x[1] + x[2] + ... + x[24] - 3x[25] = 0
(after division by 5). Subtract this equation from the sum of
the 4th, 8th, and 12th rows to complete the proof.
From the non-negativity it follows:
x[4] = x[8] = x[12] = x[13] = x[17] = x[21] = 0.
Now look the first equation. It becomes: 2 x[1] = x[25].
And therefore must x[25] be even. QED
Proof: impossibility of 3*3*...*3*5u with u not 0 (mod 3)
Look at the one-dimensional projection. Make a coloration alternatingly
with three colors: (a, b, c, a, b, c, ... ). According to this coloration
the L always gives (mod 2): (a,b,c) = (1,1,1). Therefore we must have
a=b=c (mod 2) for the entire box. But this implies u = 0 (mod 3). QED
Annotations:
2x5 rectangle:
a a a a b
a b b b b
7x15 has 2 solutions (not counting 2x5 exchanges):
a a a a a 1 1 1 1 2 2 2 2 b b 1 1 1 1 2 2 3 3 a a a a a b b
a a a a a 1 3 3 4 4 4 4 2 b b 1 4 4 5 2 6 3 7 a a a a a b b
c c d d e e 3 5 4 6 6 6 6 b b c c 4 5 2 6 3 7 7 7 7 8 9 b b
c c d d e e 3 5 7 7 7 7 6 b b c c 4 5 2 6 3 1 8 8 8 8 9 b b
c c d d e e 3 5 7 8 8 8 8 b b c c 4 5 5 6 6 1 1 1 1 2 9 b b
c c d d e e 9 5 5 8 f f f f f c c d d d d d 3 2 2 2 2 9 9 4
c c d d e e 9 9 9 9 f f f f f c c d d d d d 3 3 3 3 4 4 4 4
Note: D. Klarner, Packing a Rectangle with Congruent N-ominoes, JoCT 7 (1969)
107-115, gives in figur 12 an example of a 9x15 rectangle.
5xN dissects in 2x5 rectangles:
5xZ has several solutions (other than 2x5 blocks):
b b a a a a a b b b b b a a a a a b b b b
b a a a a a a b b b b b a a a a a b b
. . b a . . c c c c c c c c . . c c c c c b b b b . .
b a c d d d d d c c c c c c c b d d d d d
a a d d d d d c c c c b b b b d d d d d
The left and right part can be iterated. In the right part all
L-pentominoes are laying horizontally. (You can use the handed L.)
A tiling with period 11:
a a a a b b b b c c c c
d d a b b g g g g g c
d b b b b g g g g g c
d e e e e e f c c c c
d e e e e e f f f f
3x5x5 (trivial):
5 5 5 5 5 a x x x x a a b b a
5 5 5 5 5 dissects a x a b a x x x x a
5 5 5 5 5 b b a b a x a a b b
3x3xZ:
a a a a 3 3 3 3 3 3 3 3 3 a a a a
a 3 3 3 3 3 3 3 3 3 3 3 3 3 a
3 3 3 3 3 3 3 3 3 3 3 3 3
Hyperboxes:
the 3x3x3x30 and 3x3x3x45 can be packed with the
V5x3x30 and V5x3x45 and 2x5. So if you bent the V5
straight, you get a 5x3x30 and 5x3x45 box, where
the long arm of the L must not lay along the first axis.
These special 5x3x30 and 5x3x45 boxes can dissected into: A-A, A-B-A.
5 5 5 5 5 5 5 5 5 5 5 5 5 5 3 2 2 3 5 5 5 5 5 5 5 5 5 5 5 5 5 3 2
A: 5 5 5 5 5 5 5 5 5 5 5 5 5 5 3 2 B: 2 3 5 5 5 5 5 5 5 5 5 5 5 5 5 3 2
5 5 5 5 5 5 5 5 5 5 5 5 5 5 3 2 2 3 5 5 5 5 5 5 5 5 5 5 5 5 5 3 2
Handed L5:
Michael Reid found in 1998 all prime handed-L5 rectangles.
2x5, 13x55, 15x39, 17x35, 19x25.
The smallest odd rectangle with right handed L5 is 19x25:
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| | | | | | | | |
+ +--+--+--+ + +--+--+--+ + +--+--+--+ + +--+ +--+
| | | | | | | | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ + + + +
| | | | | | | | | | |
+ +--+--+--+ + +--+--+--+ + +--+--+--+ + + + + +
| | | | | | | | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ +--+ +
| | | | | | | | |
+ +--+--+--+ + +--+--+--+ + +--+--+--+ +--+--+--+--+
| | | | | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ +
| | | | | | | | | |
+ +--+ +--+ +--+ +--+ +--+--+--+ + +--+--+--+ +--+
| | | | | | | | | | | | | |
+ + + + + + + + +--+--+--+--+--+--+--+--+--+--+ +
| | | | | | | | | | | | |
+ + + + + + + +--+--+--+--+ + +--+--+--+--+ + +
| | | | | | | | | | | | | |
+--+ +--+ +--+ +--+--+--+--+ + + +--+--+--+ +--+ +
| | | | | | | | | | | |
+--+--+--+--+--+--+--+--+--+ +--+ + + +--+ +--+--+--+
| | | | | | | | | | |
+ +--+--+--+ + +--+ +--+--+--+--+--+ + +--+--+--+--+
| | | | | | | | | | |
+--+--+--+--+--+ + + + +--+--+--+ + +--+--+--+--+ +
| | | | | | | | | | |
+ +--+--+--+ + + + +--+--+--+--+--+--+--+--+--+ + +
| | | | | | | | | | |
+--+--+--+--+--+--+ +--+--+--+--+ + +--+--+--+ +--+ +
| | | | | | | | |
+ +--+--+--+ +--+--+--+--+--+ +--+--+--+--+--+--+--+--+
| | | | | | | | | |
+--+--+--+--+--+ +--+--+--+ +--+ +--+ +--+ +--+ +--+
| | | | | | | | | | | | | |
+ +--+--+--+ +--+--+--+--+--+ + + + + + + + + +
| | | | | | | | | | | | | |
+--+--+--+--+--+ +--+--+--+ + + + + + + + + + +
| | | | | | | | | | | | | |
+ +--+--+--+ +--+--+--+--+--+ +--+ +--+ +--+ +--+ +
| | | | | | | | | |
+--+--+--+--+--+ +--+ +--+--+--+--+--+--+--+--+--+--+--+
| | | | | | | | | | |
+ +--+--+--+ + + + + + +--+--+--+ + +--+--+--+ +
| | | | | | | | | | |
+--+--+--+--+--+ + + + +--+--+--+--+--+--+--+--+--+--+
| | | | | | | | | | |
+ +--+--+--+ +--+ +--+ + +--+--+--+ + +--+--+--+ +
| | | | | | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
References:
- David Klarner,
Packing a Rectangle with Congruent N-ominoes,
JoCT 7 (1969) 107-115,
gives in figur 12 an example of a 9x15 rectangle with L5.
- Michael Reid,
There are odd "one-sided" L pentominoes prime rectangles,
email from 1999-01-15