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