prime boxes of the v-pentomino: Torsten Sillke 03.03.93 updates: 3x11x15, 3x13x15, 3x7x{25, 30, 35} (12.07.94) (the 'p' indecates a prime box) 3d-complete: 12.07.94 2d-complete: 01.08.98 open problem: classify the ZxZ packings 2-dim: ------ Zx 5p, ... 5n 3-dim: ------ 3x5x 6p, 8p, 12, 14, 16, ... {12, 14, 16}+6n 4x5x 6p, 7p, 8p, 9p, 10p, 11p, ... {6..11}+6n 5x5x 6p, 9p, 10p, 11p, 12p, 13p, 14p, ... {9..14}+6n 6x5x 3p, 4p, 5p, ... {3..5}+3n 7x5x 4p, 6, 7p, 8, 9p, ... {6..9}+4n 8x5x 3p, 4p, 6, 7, 8, ... {6..8}+3n 9x5x 4p, 5p, 6, 7p, ... {4..7}+4n 10x5x 4p, 5p, 6, 7, ... {4..7}+4n 11x5x 4p, 5p, 6, 7, ... {4..7}+4n kx5x with k >= 12. kx5xh is tilable: I) h = 3..5 : see h*5*k II) h > 6 : k = {6..11}+6n all kx5xh are tilable 3x10x 6, 8, 9p, 10p, 11p, 12, 13p, ... {8..13}+6n 4x10x 4p, 5p, 6, 7, ... {4..7}+4n 5x10x 4p, 5p, 6, 7, ... {4..7}+4n 6x10x 3, 4, 5, ... {3..5}+3n 7x10x 4, 5, 6, 7, ... {4..7}+4n kx10x with k >= 8. k*10*h 3x15x 6, 8, 9p, 10, 11p, 12, 13p, ... {8..13}+6n 4x15x 4p, 5, 6, 7, ... {4..7}+4n 5x15x 4, 5, 6, 7, ... {4..7}+4n 6x15x 3, 4, 5, ... {3..5}+3n 7x15x 4, 5, 6, 7, ... {4..7}+4n (all k*5r*h found with k>=4 and r>=2) 3x20x 5, 6, 7p, 8, 9, ... {5..9}+5n 3x25x 6, 7p, 8, 9, 10, 11, ... {6..11}+6n 3x30x 5, 6, 7p, 8, 9, ... {5..9}+5n 3x35x 6, 7p, 8, 9, 10, 11, ... {6..11}+6n 3xNx 5, 6, 7, 8, 9, ... {5..9}+5n 4xNx 4, 5, 6, 7, ... {4..7}+4n 5xNx 3, 4, 5, ... {3..5}+3n 3xZx 4p, 5, 6, 7, ... {4..7}+4n 4xZx 4, 5, 6, 7, ... {4..7}+4n 5xZx 3, 4, 5, ... {3..5}+3n 3x3x5x 4p, 5p, 6, 7? 3x4x5x 3p, 4p, 5? 3x5x5x 3p, 4?, 5? 4x4x5x 3p, 4?, 5? 4x5x5x 3?, 4?, 5? 5x5x5x 3?, 4?, 5? 3x3x10x 4, 5?, 6, 3x3x15x 3?, 3x3x3x5x 3? Impossible: 2xNxN as NxN is impossible 3x3xZ if the center is filled, the corners are separated. 3x3xN dies out after 7 steps 3x4xN dies out after 15 steps 3x5xu (u = odd) border-sets of the partial packings of 3*u pieces computed 3x5x4, 3x5x10 4x4x5, 4x5x5, 5x5x{5, 7, 8} 3x7x{10, 15} 3x3x3x{5, 10, 15} Annotations: a a a b a b b b a . . b = a . . b this is the O-symmetry a b b b a a a b solution counts are without O-symmetry 5 5 5 5 5 5 5 5 5 5 5 has 2 solutions 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 has 21 solutions 5 5 5 5 5 5 5 (no O-sym correction) 5 5 5 5 5 5 5 both figures from above give the 5x7x7 3x5x6 and 3x5x8 have each 2 solutions. 3x9x10 is unique (containing no O) . 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 gives a 3x4xZ Tiling the halve plane NxZ: Thm: The NxZ tilings dissectes into 5xZ stripes. This follows from the following propositions. Prop1: Border is of the form . . . 1 1 1 2 2 2 1 1 1 2 2 2 . . . ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ <- the border Proof: impossible config: x x x x . x . ^ ^ as |. .| can filled only by the wing configuration ^ ^ x x x y y y x y |x y| ^ ^ Prop2: Border is of the form 2 1 2 1 2 1 2 1 2 1 2 1 2 2 2 1 1 1 2 2 2 1 1 1 2 2 2 1 1 1 ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ <- the border Proof: impossible config: x y x . . y x x x y y y ^ ^ ^ ^ ^ ^ ^ There is a wing configuration at '.'. w w w w w w x w w y . x w w y . x x x y y y ^ ^ ^ ^ ^ ^ ^ Now there is an impossible wing configuration at '.'. Prop3: Border is of the form 3 3 3 3 3 3 3 3 3 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 2 2 2 1 1 1 2 2 2 1 1 1 2 2 2 1 1 1 ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ <- the border Proof: Each valley has the length 4 and must be filled 3+1. If one leg of the piece '3' goes to the right, all further right legs will go to the right. Therefore the only case which have to been excluded is 3 3 3 3 3 3 2 1 3 2 1 3 2 1 2 1 3 . . . 2 1 . . . 3 2 1 2 2 2 1 1 1 2 2 2 1 1 1 2 2 2 1 1 1 ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ <- the border Filling the '.' gives case a: 3 3 3 4 4 3 3 3 2 1 3 . . 4 2 1 . . 4 3 2 1 2 1 3 4 4 4 2 1 4 4 4 3 2 1 2 2 2 1 1 1 2 2 2 1 1 1 2 2 2 1 1 1 ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ <- the border case b: 3 3 3 4 4 3 3 3 2 1 3 . . 4 2 1 4 . . 3 2 1 2 1 3 4 4 4 2 1 4 4 4 3 2 1 2 2 2 1 1 1 2 2 2 1 1 1 2 2 2 1 1 1 ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ <- the border case c: 3 3 3 4 4 3 3 3 2 1 3 4 . . 2 1 . . 4 3 2 1 2 1 3 4 4 4 2 1 4 4 4 3 2 1 2 2 2 1 1 1 2 2 2 1 1 1 2 2 2 1 1 1 ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ <- the border In all three cases we get wing configuration at '.'. But these are impossible or isolate some squares. Prop4: Border is of the form 4 x x x 4 x x x 4 x x x 4 x x x 4 x x x 4 x x x 4 x x x 4 4 4 x x x 4 4 4 x x x 4 4 x x x x x x x x x x x x x x x x x x ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ <- the border Proof: impossible configs case a: impossible double wings configurations x x x 4 x x x 4 x x x x x x 4 . . x x x . . 4 x x x x x x 4 4 4 x x x 4 4 4 x x x x x x x x x x x x x x x x x x x x x ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ <- the border case b: x x x 4 x x x 4 x x x x x x . . 4 x x x 4 . . x x x x x x 4 4 4 x x x 4 4 4 x x x x x x x x x x x x x x x x x x x x x ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ <- the border Filling all wing configurations leaves a 5xZ strip minus one square. This will be shown in Prop6. Prop5: At the border is a 5xZ strip. y y y y y y y y y y y y y y y y y y y x x x y y y x x x y y y x x x y y y x x x y y y x x x y y y x x x y y y x x x y y y x x x y y y x x x y y x x x x x x x x x x x x x x x x x x ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ <- the border This gives two solutions for the 5xZ strip. y y y y y y y y y y y y y y y y y y y 1 1 1 2 y y 1 1 1 2 y y 1 1 1 2 y y 1 x x 2 y y 1 x x 2 y y 1 x x 2 y 2 1 x x 2 2 2 1 x x 2 2 2 1 x x 2 2 x x x x x x x x x x x x x x x x x x y y y y y y y y y y y y y y y y y y 2 1 1 1 y y 2 1 1 1 y y 2 1 1 1 y y 2 1 x x y y 2 1 x x y y 2 1 x x y y 2 1 x x 2 2 2 1 x x 2 2 2 1 x x 2 2 x x x x x x x x x x x x x x x x x x Prop6: No NxZ plus one border square. C O N J E C T U R E Proof: 2 1 1 1 2 1 2 2 2 ^ ^ ^ 1 ^ ^ ^ ^ ^ case a: 2 3 1 1 1 2 . . 3 1 2 2 2 3 3 3 ^ ^ ^ 1 ^ ^ ^ ^ ^ ^ after playing some forthed moves we get (6 must avoid the wing). 6 6 6 5 6 5 6 4 4 4 4 4 4 5 5 5 2 4 4 3 1 1 1 2 4 4 3 1 2 2 2 3 3 3 ^ ^ ^ 1 ^ ^ ^ ^ ^ ^ The left corner is impossible to fill see prop7. case b: 2 3 3 1 1 1 2 3 . . 3 1 2 2 2 3 3 3 3 3 3 ^ ^ ^ 1 ^ ^ ^ ^ ^ ^ after playing some forthed moves we get the impossible wings at '.'. 4 4 4 4 4 4 2 3 4 4 3 . 1 1 1 2 3 4 4 3 . 1 2 2 2 3 3 3 3 3 3 ^ ^ ^ 1 ^ ^ ^ ^ ^ ^ case c: 2 3 3 1 1 1 2 3 . . . . 3 1 2 2 2 3 3 3 3 3 3 ^ ^ ^ 1 ^ ^ ^ ^ ^ ^ ^ ^ ^ case c1: 4 2 3 4 3 1 1 1 2 3 4 4 4 3 1 2 2 2 3 3 3 3 3 3 ^ ^ ^ 1 ^ ^ ^ ^ ^ ^ ^ ^ ^ after playing some forthed moves we get 9 9 9 7 8 9 7 6 6 6 6 6 6 8 9 7 7 7 4 6 6 5 5 5 8 8 8 2 3 4 6 6 5 3 1 1 1 2 3 4 4 4 5 3 1 2 2 2 3 3 3 3 3 3 ^ ^ ^ 1 ^ ^ ^ ^ ^ ^ ^ ^ ^ The left corner is impossible to fill see prop7. case c2: 4 2 3 4 3 1 1 1 2 3 4 4 4 3 1 2 2 2 3 3 3 3 3 3 ^ ^ ^ 1 ^ ^ ^ ^ ^ ^ ^ ^ ^ after playing some forthed moves we get 8 8 8 6 7 8 6 5 5 5 5 5 5 7 8 6 6 6 5 5 4 7 7 7 2 3 5 5 4 3 1 1 1 2 3 4 4 4 3 1 2 2 2 3 3 3 3 3 3 ^ ^ ^ 1 ^ ^ ^ ^ ^ ^ ^ ^ ^ The left corner is impossible to fill see prop7. case c3: 4 4 4 2 3 4 3 1 1 1 2 3 4 . . . 3 1 2 2 2 3 3 3 3 3 3 ^ ^ ^ 1 ^ ^ ^ ^ ^ ^ ^ ^ ^ after playing some forthed moves we get one of the following x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x ^ ^ ^ x ^ ^ ^ ^ ^ ^ ^ ^ ^ x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x ^ ^ ^ x ^ ^ ^ ^ ^ ^ ^ ^ ^ and further case checking ... ????? Now there are further cases to consider v v v 2 x x x x x x v 4 w w w w w w 2 x x x x x x x v 4 3 1 w w 2 2 2 x x x x x x x 4 4 3 1 w w x x x x x x x x x x 3 3 3 1 1 1 x x x x x x x x x x ^ ^ ^ ^ ^ ^ x ^ ^ ^ ^ ^ ^ ^ ^ ^ v v v 2 x x x x x v 4 w w w w w w 2 x x x x x x x v 4 3 1 w w 2 2 2 x x x x x x x 4 4 3 1 w w x x x x x x x x x x 3 3 3 1 1 1 x x x x x x x x x x ^ ^ ^ ^ ^ ^ x ^ ^ ^ ^ ^ ^ ^ ^ ^ v v v 2 x x x x x x x v 4 w w w w w w 2 x x x x x x x x x v 4 3 1 w w 2 2 2 x x x x x x x x x 4 4 3 1 w w x x x x x x x x x x x x 3 3 3 1 1 1 x x x x x x x x x x x x ^ ^ ^ ^ ^ ^ x ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ Prop7: No corner (at least 6) possible Proof: |. |. . |. . . this points can not be covered with V5. |. . . . |. . . . . |. . . . . . ^ ^ ^ ^ ^ ^ after playing some forthed moves we get |3 3 3 |3 . |3 2 |1 2 4 but now filling both '.' will isolate some squares. |1 2 2 2 . 4 |1 1 1 4 4 4 ^ ^ ^ ^ ^ ^ Note: A smaller corner can be filled. 9 9 9 6 6 6 9 3 3 3 6 9 |3 6 7 |3 4 7 |1 4 7 7 7 8 8 8 |1 4 4 4 5 5 5 8 |1 1 1 2 2 2 5 8 ^ ^ ^ ^ ^ 2 5 2 Tiling the plane ZxZ: In addition to coverings by 5xZ strips we have for example: Type I. a a a a b a b b b a a b a a a a a a b a diagonal strips b a b b b b b b a b a b a a a a a a b a a b b b a b a a a a Type II. b b b b a a b b a a a b a b b b a a b b b a b a a a diagonal strips b b a a a b a b b b a a a a Type III. a a a b b b c a a a a d b c a b b b c a d b c c c diagonal strip a a a d b c a d d d c a d b c c c c a d d d c c c Type IV. a b a b a a a b b b b b b a a a filling crosses b a b a a b a b a a a b b b b b b a a a b a c d b a c d c c c d d d d d d c c c d c d c Type V. c c c a b c c c c a b c c a a a b b b c c b b b a a a c filling crosses c b a c c c c b a c c c c c c a b c c c c a b c c a a a b b b c c b b b a a a c c b a c c c c b a d d d c c c a b d d d d a b d d a a a b b b d d b b b a a a d d b a d d d d b a d d d Coloring planar figures: ------------------------ the x (mod 3) coloring: 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 Each placing of the V5 fits an odd number of squares in ervery color. the x (mod 2) coloring: 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 Each placing of the V5 fits 1 (mod 3) squares in every color.