Torsten Sillke, FRA, 1998-09-01 The Domino Anti-slide Problem: (Frits G"obel, [1]) Put the 28 pieces of a 0-6 domino set into a 8x8 square such that no sliding is possible. It can be done, and we are sure there is no solution with less then 28 dominoes. In [2] a rigid packing of a rectangle with polyominoes is defined as (1) No piece or group of pieces can slide; (2) No piece can be added; (3) All of the pieces are aligned with the sides of the rectangle. The rule (2) excludes the empty packing of the rectangle if they are big enough. I think it is better (at least for 2-dimensional problems) to replace rule (2) by (2') The packing must be non empty. This may increase the number of solutions. Introduction: When CFF 34 we made a staff outing and on the bus trip I read this problem. With local reasoning I could solve it and saw that 8 holes are maximal. Later I refined the arguments to cover all rectangles. I will consturct an upper bound for the number of holes and will show that this bound can be reached. To classify all solutions or to show uniqueness to some cases more work has to be done. Solution: First let's show that 8 holes in a 8x8 square are maximal. Then make the following observations: - no hole can be at the border of the square. - the holes can't be edge or corner adjaced. That means that a 2x2 square can hold at most one hole. Tile the inner 6x6 square with 2x2 squares. All holes must be in this 6x6 square. As we have 9 of the 2x2 squares we can have at most 9 holes. As the number of holes must be even an anti-slide configuration can have at most 8 holes. This solves the problems as stated. Below we will also show that the 8-hole solution is unique. Now I will give a more detailed analysis which will solve this problem for all rectangles. The key observation is that local properties are sufficient. Property a: There is no hole configuration o o (neightbour holes) This contradicts rule (2). Now we know that all holes are isolated. Property b: There is no hole at the border (or in the corner). Assume we have a hole at the border: . o . ^ ^ ^ Try to fill the boundary of the hole from left to right. Then the oriantations of each domino is forthed to avoid siliding towords the hole upto the last one, where you could not avoid it. The same holds for a hole in a corner. Note: There is the exceptional empty 1-square. Property c: There is no hole configuration o o (diagonal neightbour holes) This follows as the position 'x' o x is not fillable. o Property d: There is no hole configuration o . o Try to fill 'x' in: o x o Then all dominoes around the two holes are forced. But the last one does not fit. Property e: There is no hole configuration o . o Try to fill 'x' in: o Then all dominoes around x the two holes are forced. o Property f: superadditivity Let the function h: polyominoes->N give the maximal number of holes which can have a polyomino subset in an anti-slide domino configuration. It holds the following inequality h(A) + h(B) >= h(A union B). Example: A: . . . B: . x . A union B: . x . x x x . x . x x x . . . . x . . x . 1 + 1 >= 1 Note: As h() is a maximal function there is no relation between h(A) + h(B) and h(A union B) + h(A intersection B). With the local properties and the superadditivity I will determine the h() function for rectangles where there is strict inequality for all rectangular dissections. Lemma: A hole in a rectangle has unique surrounding. The surrounding 3x3 square is sufficient for rigidity of this hole. Proof: Start filling an edge-neightbour of the hole. Then there is always a further forthed domino around the hole. Lemma: Given a hole at 'o'. Then a second hole cannot be at the positions marked 'x'. Every other position is possible. x x x x x x x x o x x x x x x x x Proof: The 'x' follow immideate from propeties 'a', 'c', 'd', or 'e'. The configuration o . . is possible . . o At all other places the 3x3 square surroundings don't interact. Lemma: An inner 2x2 rectangle contains at most one hole in a unique way. Proof: Follows immideate from propeties 'a', 'c'. The unique arrangement o . of 1 holes is a follows. . . Lemma: An inner 3x3 rectangle contains at most 2 holes in a unique way. Proof: Follows immideate from propeties 'a', 'c', 'd', or 'e'. The unique arrangement o . . of 2 holes is a follows. . . . . o . Lemma: An inner 2x5 rectangle contains at most 2 holes. Proof: cover the 2x5 rectangles by three rectangles as follows. a a b a a a a b a a Assume on the contrary that 3 holes are possible than each subrectangle must contain one hole. Upto symmetry there is only one possibility in rectangle 'b'. Choose the upper point and discarding all point with the help of property 'a', 'c', and 'd' we are left with only one configuration . . o . . but this is impossible . . o . . o . . . o as x is unfillable o . x . o This gives the contradiction. Therefore 2 holes are maximal. Lemma: An inner 3x5 rectangle contains at most 3 holes. Proof: cover the 3x5 rectangles by two rectangles as follows. a a b b b a a b b b a a b b b Assume on the contrary that 4 holes are possible than subrectangle 'a' contain 2 holes in unique position (upto symmetry). Swap the two rectangles and apply this argument for the rigth side too. Then we are left with two possible configurations. o . . . o o . . o . . . . . . . . . . . . o . o . . o . . o The first one contradicts property 'd' the second 'e'. This gives the contradiction. Therefore 3 holes are maximal. Lemma: An inner 4x6 rectangle contains at most 5 holes. Proof: cover the 4x6 rectangles by four rectangles as follows. a a a a a c a a a a a c b b b b b c b b b b b d Assume on the contrary that 6 holes are possible than the for rectangles 'a' to 'd' must contain their maximal number of holes. That means that in the corner at 'd' there must be a hole. But by symmetry this argument is valid for each corner. But if all corners are used every other place is discarded by one of the propeties 'a', 'c', 'd', or 'e'. Contradiction! Lemma: An inner 6x6 rectangle contains at most 8 holes in a unique way. Proof: Partition the 6x6 square into 3x3 squares. Each can have at most 2 holes. So we get at most 8 holes for the 6x6 square. Now find all 8 hole arrangements. There are four ways to select the 2 holes in the left upper 3x3 square (upto symmetry). Possible corner types: a------ b------ c------ d------ and their | . o . | . . o | . . o | o . . mirror | . . . | . . . | o . . | . . o images | . . o | . o . | . . . | . . . case a: . o . x x . The 'x' marked positions are forbidden in . . . x . . the right upper 3x3 square. . . o x x . . . . . . . But now no 2 holes can't be selected any . . . . . . more in the right upper 3x3 square. . . . . . . case b: . . o x x . The 'x' marked positions are forbidden in . . . x . . the right upper 3x3 square. . o . x x . . . . . . . But now no 2 holes can't be selected any . . . . . . more in the right upper 3x3 square. . . . . . . At this stage types 'a' and 'b' can't be in any 6x6 square. case c: . . o x x . The 'x' marked positions are forbidden in o . . x . . the right upper 3x3 square. . . . . x . . . . . . . Only type 'a' fits into the right upper 3x3 square. . . . . . . But this has been eliminated. . . . . . . At this stage only type 'd' can be used. case d: o . . x . . The 'x' marked positions are forbidden in . . o x x . the right upper 3x3 square. . . . x . . . . . . . . Type 'd' fits in one way only in the . . . . . . right upper 3x3 square. . . . . . . The same is valid for the next square in clockwise order. So we get only one solution with 8 holes o . . . . o This is the unique 8 holes pattern. . . o . . . It is part of the Knight-lattice. . . . . o . . o . . . . . . . o . . o . . . . o Corollary: The 8x8 rectangle contains at most 8 holes in a unique way. Now determine the maximal number of holes in subrectangles for two lattices: the Knight-lattice and a Square-lattice. Then show that the maximum of both functions is also an upper bound. The Knight-lattice: Let g5(x,y) be the maximal number of points in a subrectangle of size x times y of the lattice <(2,1),(-1,2)>. 0 1 2 3 4 table of g5(x,y) small values. +-------------- 0 | 0 0 0 0 0 1 | 0 1 1 1 1 2 | 0 1 1 2 2 3 | 0 1 2 2 3 4 | 0 1 2 3 4 As each rectangle of size (1,5) and (5,1) contains exactly one point we have the additivity relations in both arguments g5(x+5,y) = g5(x,y) + g5(5,y) = g5(x,y) + y g5(x,y+5) = g5(x,y) + g5(x,5) = g5(x,y) + x This give the formular g5(x,y) = [x/5] y + x [y/5] - 5 [x/5] [y/5] + g5( x mod 5, y mod 5 ). The Square-lattice: Let g3(x,y) be the maximal number of points in a subrectangle of size x times y of the lattice <(3,0),(0,3)>. As the rectangles are allined with the lattice we see at once g3(x,y) = [(x+2)/3][(y+2)/3] The Upper bound: Now show h(p,q) = max( g5(p,q), g3(p,q) ). Table h(.,.) of the maximal number of holes in every inner rectangle: 1 2 3 4 5 6 7 8 9 10 +----------------------------- 1 | 1* 1* 1* 2 2 2 3 3 3 4 2 | 1* 1* 2 2 2* 3 3 4 4 4 3 | 1* 2 2* 3 3* 4 5 5 6 6 4 | 2 2 3 4 4 5* 6 7 8 8 5 | 2 2* 3* 4 5 6 7 8 9 10 6 | 2 3 4 5* 6 8 9 10 11 12 7 | 3 3 5 6 7 9 10 12 13 14 8 | 3 4 5 7 8 10 12 13 15 16 9 | 3 4 6 8 9 11 13 15 17 18 10 | 4 4 6 8 10 12 14 16 18 20 First observe that g5(p,q) >= g3(p,q) if p>1 and q>1. So for p>1 and q>1 we have the additivity property h(5,q) + h(p,q) = h(5+p,q) as g5() has this property. Likewise h(3,1) + h(p,1) = h(3+p,1) as g3() has this property. The only values to check are the p<=6 and q<=6 cases. If h(p1,q) + h(p2,q) > h(p,q) for all p1, p2 with p1+p2=p we have will to check these values. In the table these values are stared. In these cases our lower bound might not be optimal. But the lemmas stated before show that the lower bound max( g5(p,q), g3(p,q) ) is correct. Holes of non integral size: Upto now it was assumed that the size of the holes must by integral. In the plane (and half-plane) we can place the pieces with no integral holes but if we have a border this cannot be the case. Lemma: The holes of an anti-slide configuration of the quadrant must have integral size. Proof: Assume we have a hole, were one side is non-integral. Select this border of the octant which is perpendicular to this non-integral hole side. Select a hole which is nearest to this border which non-integral hole width w and which is perpendicular to this border. Then we have the configuration | 1 1 2 2 2 2 |<-- e ---->1 1 2 2 2 2 | 1 1 . 1 1 | 1 1 . 1 1 |<-- f -->2 2 2 2 1 1 | 2 2 2 2 1 1 As e = f + w not both e and f can be integral. But all pieces and holes have integral side lengths in this orientation. This is a contradiction. So 2x4 or 3x6 rectangles have the same anti-slide solutions as dominoes. A non-integral anti-slide tiling of the half-plane: 1 1 2 2 1 1 2 2 1 1 . 1 1 2 2 . 2 2 1 1 . 1 1 2 2 . 2 2 1 1 . 1 1 2 2 . 2 2 1 1 1 1 . 1 1 2 2 . 2 2 1 1 1 1 . 1 1 2 2 . 2 2 1 1 . 1 1 1 1 . 1 1 2 2 . 2 2 1 1 . 1 1 1 1 2 2 . 2 2 1 1 . 1 1 3 3 3 3 1 1 2 2 . 2 2 1 1 . 1 1 3 3 3 3 5 5 5 5 2 2 1 1 . 1 1 5 5 5 5 6 6 6 6 5 5 5 5 2 2 1 1 . 1 1 5 5 5 5 6 6 6 6 3 3 3 3 1 1 3 3 3 3 4 4 4 4 3 3 3 3 3 3 3 3 1 1 3 3 3 3 4 4 4 4 3 3 3 3 Constructing the rectangles: If we want find rectangles with the biggest hole area the h-function will not be reached in every case as the hole area and the rectangle area must be equal modulo 2. After reducing h we get the following table. All reduced values are marked '-'. 3 4 5 6 7 8 9 10 11 12 +----------------------------- 3 | 1 0- 1 2 1- 2 3 2- 3 4 4 | 0- 0- 2 2 2 2- 2- 4 4 4 5 | 1 2 1- 2- 3 4 5 4- 5- 6 6 | 2 2 2- 4 4 4- 6 6- 8 8 7 | 1- 2 3 4 5 6 7 8 9 10 8 | 2 2- 4 4- 6 8 8-10 10-12 9 | 3 2- 5 6 7 8- 9-12 13 14 10 | 2- 4 4- 6- 8 10 12 12-14-16 11 | 3 4 5- 8 9 10-13 14-17 18 12 | 4 4 6 8 10 12 14 16 18 20 Now check that these anti-side rectangles can be build. For 4<=x<=y<=8 you can build them using the Knight-lattice. All bigger rectangles can be constructed by increasing these basic solutions in chunks of 5. For the rectangles 3*y use the square-lattice. Border conditions for the Knight-Lattice: Edge: There is one edge type for the Knight-Lattice. It is even. x x x x x x x . x x x x . x x x x . x x x x + + x x x ^ ^ ^ ^ ^ ^ ^ ^ Corner: There are five corner types for the Knight-Lattice. Four are even and one is odd. even corners: 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 ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ odd corner: x x x x . x x x x |- x x x |- x . x |- x x x ^ ^ ^ Example: From an inner 3x6 to a 5x8 rectangle There are 4 possible hole pattern for the 3x6 inner rectangle. (This can easily be found by the 3x3 dissction, and a 2x5 check.) . . o . . . o . . . . o o . . . o . o . . . . o o . . . . o . . . o . . . . . . . . . . . . . . . . . o . . . o . . . . . o . . . o . o . . o . The first two ones are based on the Knight-Lattice. The others are of a mixed type. The first don't give a 5x8 rectangle as it has two odd corners. The others are possible. Now the Knight-Lattice solution can be enlarged by 5. o . . . . o o . . . . o . . . . o . . . o . . -> . . . o . . . . o . . . o . . . . . o . . . . o . . . . As this doesn't change the corner type this is possible too. Extremal polyominoes for the h-function: holes = 1: x x x x x x x x x holes = 2: There are many extremal regions. We have infinitly many nonconnected ones, as we can take the union of two 1-hole regions. The two rectangles 3x3 and 2x5 are extremal. For the 2x5 rectangle this is no surprise as the region has constant hole-density in the knight-lattice. There can be no polyomino which tiles the plane that has a lower hole-density than the knight-lattice. Some extremal regions: (try to find all) 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 Table of optimal rectanges: width = 1: . This is the exceptional empty rectangle. width = 3: x x x x x x x x x x y y x x x y y y x x x y y y y x . x x x x x x . x y y x . x y . y x . x y y y y x x x x x x x x x x y y x x x y y y x x x y y y y parity problem avoid a hole in the 3*4 rectangle. width = 4: x x x x x x x x x x x x x x x x z z x x x x x x . x x . x x x x x x z z z z x x x z x x x y y y x x x . x z x . x y . y x . x x x z x x x y y y x x x z z z z z z z z z z z x x x z z z z z x x x z x x x y y y z x x x . x z z z x x x . x z x . x y . y z x . x x x z z z x . x x x z x x x y y y z x x x z z z z z x x x z z z z z z z z z z z z x x x z z z z z z x x x z z x x x y y y z z x x x z z z z z x x x . x z z z z x x x . x z z x . x y . y z z x . x z y y y z and x . x x x z z z z x . x x x z z x x x y y y z z x x x z y . y z other x x x z z z z z z x x x z z z z z z z z z z z z z z z z y y y z . . . z z x x x z z y y y z z x x x z z y y y z z z z x x x . x y y y . y x x x . x y y y . y z z z z x . x x x y . y y y x . x x x y . y y y z z z z x x x z z y y y z z x x x z z y y y z z z z z z 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 y . y x . x y . y x . x y . y x . x 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 z z z z z z z z z z z z z z z z z z z z z z z z A 4*n rectanlge can not have more than four 4*6 rectangles as four 4*6 ones can be replaced by five 4*5 ones which contain two holes more. width = 5: x x x z z z z z z z z x x x z x . x z z z x x x z but z x . x z as black:white not 1:1 x x x z z z x . x z not z x x x z z z z z z z x x x z z z z z z z z z z z z z z z z z z z z z z x x x z z x x x y y y x x x z z z z z z z z z z x . x z z x . x y . y x . x z z z x x x y y y x x x x z z x x x y y y x x x y y y x . x y . y x . x z z z z z z z z z z z z y . y x x x y y y x x x z z z z z z z z z z z z y y y z z z z z z x x x z z z z x x x z z z z x x x z z z z x x x z y y y x . x x x z z x . x x x x z x . x z z z z x . x z y . y x x x . x x x x x x x . x z x x x x y y y x x x x y y y z z x x x . x z x . x x x z z x . x y . y z x . x z z z z z z z x x x z x x x z z z z x x x y y y z x x x z z z x x x z z x x x x x x z y y y z x . x x x x . x x . x z y . y z x x x . x x x x x x x x y y y y z z x x x . x z z x . x z y . y z z z z x x x z z x x x z y y y x x x z z x x x z x . x x x x . x z x x x x . x x x x z x . x x x x . x z x x x z z x x x x x x z z x x x z z x x x z y y y z z z z z z z x x x z z z x . x x x x . x z z x . x z y . y z z z z x x x x . x x x z and x x x . x x x x z z x x x x y y y y z z z x . x x x x . x z many z z x x x . x z z z z x . x z y . y z z z x x x . x x x x z more. z z z z x x x z z z z x x x z y y y z z z z z x x x z z z z The 5*10 rectangle contains fewer holes than the 5*9 rectangle. This is of course a parity problem. width = 6: x x x y y y z z x x x z x . x y . y x x x . x z x x x y y y x . x x x x y y y x x x x x x x . x y . y x . x z x . x x x y y y x x x z x x x z z x x x y y y z z z x x x z z x x x y y y z x x x z z z z x . x y . y z x x x . x z z x . x y . y z x . x x x x z x x x y y y z x . x x x x z x x x y y y y x x x x . x z y y y x x x z x x x x . x z y y y z y . y z x . x x x z y . y x . x z z x . x x x z y . y z y y y z x x x x . x y y y x x x z z x x x z z z y y y z z z z z z z z x x x x x x y y y z z z z x x x z z z x x x y y y z z x x x z z z z z x . x y . y z z x x x . x z z z x . x y . y z z x . x x x x z z and x x x y y y z z x . x x x x z z x x x y y y y z x x x x . x z z other y y y x x x z z x x x x . x z z y y y z y . y z z x . x x x z z y . y x . x z z z x . x x x z z y . y z y y y z z x x x x . x z y y y x x x z z z x x x z z z z y y y z z z z z z z z z x x x z x x x y y y x x x z z z z x x x z z y y y z z x x x z x . x y . y x . x z x x x x . x x x y . y x x x . x z x x x y y y x x x z x . x x x x . x y y y x . x x x x y y y x x x y y y x x x x . x x x x y y y x x x x . x y . y x . x y . y x . x x x x . x z y . y z x . x x x y y y x x x y y y x x x z z x x x z y y y z x x x z z width = 7: x x x z z z z x . x x x z z x x x . x x x z x x x x . x z x . x x x x z x x x . x z z z z x x x z z x x x z z z z z x . x x x z z and x x x x . x x x other x . x x x x . x x z x . x x x x z z x x x . x z z z z z x x x z width = 8: x x x z z x x x x . x x x x . x x x x . x x x x z x x x x . x z z x . x x x x z x x x x . x x x x . x x x x . x x x x z z x x x x x x z z x x x z z z z z x x x z z x . x x x x . x z z x x x x . x x x x x x . x x x x z z x . x x x x . x z x x x x . x z z x x x x . x x x x examples z x . x x x x z z x . x x x x . x z x x x x . x x x z x x x . x x x x z x . x x x x . x z z z x x x . x z z x x x z z x x x z z z z z x x x z z width = 9: x x x y y y x x x z z x x x z z z z x . x y . y x . x z z x . x x x z z x x x y y y x x x z x x x x . x x x y y y x x x y y y z x . x x x x . x examples y . y x . x y . y x x x x . x x x x y y y x x x y y y x . x x x x . x z x x x y y y x x x x x x . x x x x z x . x y . y x . x z z x x x . x z z x x x y y y x x x z z z z x x x z z Extensions to 3-dim: This is already for dominoes not simple. Now holes can be at the surface too as the examples 2-cube with 2 holes and the 3-cube with 5 holes show [2, title-page]. If we drop rule (2) we will get a very simple 3 hole solution for the 3-cube. Exclude a column through the center. Other rectangular pieces: The straight tromino: In this case there the holes are not isolated but we have the following hole types 2 1 1 1 2 1 1 1 2 1 1 1 2 2 . . 2 2 . 2 2 . 2 2 . . 2 2 . 2 2 1 1 1 2 1 1 1 2 1 1 1 2 Example 14-square: x x x x z z z z z z x x x x x . . x x x x z z z x . . x x . . x . . x x x x x . . x x x x x . . x . . x x x x x z z x x x x x . . x . . x z z z x . . x x x x x . . x z z z x . . x . . x x x x x z z x x x x x . . x . . x z z z x . . x x x x x . . x z z z x . . x . . x x x x x z z x x x x x . . x . . x x x x x . . x x x x x . . x . . x x . . x z z z x x x x . . x x x x x z z z z z z x x x x The 2x3 hexomino: Several different hole types are possible. The borders get quite large now. I constructed the following examples by hand. They need no have the maximal hole-area. The hole density d = hole-area/rectangle-area. Example rectangles: 1 1 2 2 2 1 1 2 2 3 3 3 4 4 4 1 1 2 2 2 1 1 2 2 3 3 3 4 4 4 1 1 . 1 1 1 1 2 2 . . 2 2 1 1 2 2 2 1 1 4 4 4 3 3 3 2 2 1 1 2 2 2 1 1 4 4 4 3 3 3 2 2 1 1 1 1 1 3 3 4 4 2 2 2 1 1 1 4 4 1 1 1 3 3 4 4 2 2 2 1 1 1 4 4 2 2 2 3 3 4 4 1 1 1 4 4 . 4 4 2 2 2 . 2 2 2 1 1 1 4 4 1 1 1 4 4 3 3 2 2 2 4 4 . 4 4 1 1 1 4 4 3 3 1 1 1 4 4 1 1 1 2 2 2 4 4 3 3 1 1 1 4 4 1 1 1 2 2 2 1 1 1 2 2 2 3 3 4 4 1/d = 25 1 1 1 2 2 2 3 3 4 4 2 2 2 1 1 1 3 3 4 4 2 2 2 1 1 1 4 4 3 3 3 3 4 4 . . 4 4 3 3 3 3 4 4 . . 4 4 3 3 3 3 4 4 1 1 1 2 2 2 4 4 3 3 1 1 1 2 2 2 4 4 3 3 2 2 2 1 1 1 4 4 3 3 2 2 2 1 1 1 11x16 rectangle (14 + 6*27 = 11*16, 1/d = 12.6) 2 2 2 1 1 1 3 3 2 2 2 4 4 2 2 2 2 2 2 1 1 1 3 3 2 2 2 4 4 2 2 2 3 3 4 4 . . 3 3 1 1 1 4 4 1 1 1 3 3 4 4 1 1 1 . 1 1 1 3 3 1 1 1 3 3 4 4 1 1 1 3 3 . . 3 3 2 2 2 2 2 2 3 3 . . 3 3 . . 3 3 2 2 2 2 2 2 3 3 . . 3 3 1 1 1 4 4 3 3 1 1 1 3 3 1 1 1 . 1 1 1 4 4 3 3 1 1 1 4 4 1 1 1 3 3 . . 4 4 3 3 2 2 2 4 4 2 2 2 3 3 1 1 1 2 2 2 2 2 2 4 4 2 2 2 3 3 1 1 1 2 2 2 16x20 rectangle (20 + 6*50 = 16*20, 1/d = 16) 3 3 4 4 2 2 2 3 3 4 4 1 1 1 3 3 4 4 3 3 3 3 4 4 2 2 2 3 3 4 4 1 1 1 3 3 4 4 3 3 3 3 4 4 1 1 1 3 3 4 4 2 2 2 3 3 4 4 3 3 1 1 1 . 1 1 1 2 2 2 . 2 2 2 1 1 1 2 2 2 1 1 1 2 2 2 . 2 2 2 1 1 1 . 1 1 1 2 2 2 4 4 . 2 2 2 1 1 1 . 1 1 1 2 2 2 3 3 4 4 4 4 1 1 1 . 1 1 1 2 2 2 . 2 2 2 3 3 4 4 4 4 1 1 1 2 2 2 . 2 2 2 1 1 1 . 3 3 4 4 3 3 4 4 . 2 2 2 1 1 1 . 1 1 1 2 2 2 3 3 3 3 4 4 1 1 1 . 1 1 1 2 2 2 . 2 2 2 3 3 3 3 4 4 1 1 1 2 2 2 . 2 2 2 1 1 1 . 3 3 1 1 1 2 2 2 . 2 2 2 1 1 1 . 1 1 1 2 2 2 1 1 1 2 2 2 1 1 1 . 1 1 1 2 2 2 . 2 2 2 4 4 3 3 4 4 1 1 1 3 3 4 4 2 2 2 3 3 4 4 4 4 3 3 4 4 2 2 2 3 3 4 4 1 1 1 3 3 4 4 4 4 3 3 4 4 2 2 2 3 3 4 4 1 1 1 3 3 4 4 17x20 rectangle (4 + 6*56 = 17*20) 4 4 4 1 1 2 2 1 1 2 2 6 6 6 1 1 2 2 1 1 4 4 4 1 1 2 2 1 1 2 2 6 6 6 1 1 2 2 1 1 5 5 5 1 1 2 2 1 1 2 2 4 4 4 1 1 2 2 1 1 5 5 5 6 6 6 4 4 4 1 1 4 4 4 5 5 5 4 4 4 4 4 4 6 6 6 4 4 4 1 1 6 6 6 5 5 5 4 4 4 4 4 4 2 2 1 1 2 2 1 1 6 6 6 4 4 4 5 5 5 5 5 5 2 2 1 1 2 2 . 2 2 3 3 4 4 4 5 5 5 5 5 5 2 2 1 1 2 2 . 2 2 3 3 5 5 5 4 4 4 4 4 4 5 5 5 3 3 1 1 2 2 3 3 5 5 5 4 4 4 4 4 4 5 5 5 3 3 1 1 . 1 1 2 2 1 1 5 5 5 5 5 5 4 4 4 3 3 1 1 . 1 1 2 2 1 1 5 5 5 5 5 5 4 4 4 6 6 6 2 2 1 1 2 2 1 1 4 4 4 4 4 4 5 5 5 6 6 6 2 2 4 4 4 6 6 6 4 4 4 4 4 4 5 5 5 4 4 4 2 2 4 4 4 6 6 6 5 5 5 1 1 2 2 1 1 4 4 4 1 1 2 2 1 1 2 2 5 5 5 1 1 2 2 1 1 6 6 6 1 1 2 2 1 1 2 2 4 4 4 1 1 2 2 1 1 6 6 6 1 1 2 2 1 1 2 2 4 4 4 14x17 rectangle (16 + 6*37 = 14*17, 1/d = 14.9) 3 3 4 4 1 1 1 4 4 3 3 2 2 2 1 1 1 3 3 4 4 1 1 1 4 4 3 3 2 2 2 1 1 1 3 3 4 4 2 2 2 4 4 3 3 1 1 1 2 2 2 2 2 2 . 2 2 2 . 2 2 2 1 1 1 2 2 2 2 2 2 4 4 1 1 1 2 2 2 . . 3 3 4 4 1 1 1 4 4 1 1 1 . . 1 1 1 3 3 4 4 1 1 1 4 4 . . 2 2 2 1 1 1 3 3 4 4 4 4 3 3 1 1 1 2 2 2 . . 4 4 1 1 1 4 4 3 3 1 1 1 . . 1 1 1 4 4 1 1 1 4 4 3 3 . . 2 2 2 1 1 1 4 4 2 2 2 2 2 2 1 1 1 2 2 2 . 2 2 2 . 2 2 2 2 2 2 1 1 1 3 3 4 4 2 2 2 4 4 3 3 1 1 1 2 2 2 3 3 4 4 1 1 1 4 4 3 3 1 1 1 2 2 2 3 3 4 4 1 1 1 4 4 3 3 14x18 rectangle (24 + 6*38 = 14*18, 1/d = 10.5) 3 3 3 4 4 4 2 2 3 3 3 2 2 1 1 4 4 4 3 3 3 4 4 4 2 2 3 3 3 2 2 1 1 4 4 4 1 1 2 2 . . 2 2 4 4 4 2 2 1 1 3 3 3 1 1 2 2 4 4 4 . 4 4 4 3 3 3 . 3 3 3 1 1 2 2 4 4 4 3 3 3 . 3 3 3 1 1 2 2 4 4 4 3 3 3 . 3 3 3 1 1 . . 1 1 2 2 4 4 4 3 3 3 1 1 . . 1 1 . . 1 1 2 2 2 2 1 1 . . 1 1 . . 1 1 3 3 3 4 4 4 2 2 1 1 . . 1 1 3 3 3 . 3 3 3 4 4 4 2 2 1 1 3 3 3 . 3 3 3 4 4 4 2 2 1 1 3 3 3 . 3 3 3 4 4 4 . 4 4 4 2 2 1 1 3 3 3 1 1 2 2 4 4 4 2 2 . . 2 2 1 1 4 4 4 1 1 2 2 3 3 3 2 2 4 4 4 3 3 3 4 4 4 1 1 2 2 3 3 3 2 2 4 4 4 3 3 3 18x18 rectangle (12 + 6*52 = 18*18, 1/d = 27) x x x x x z z z z z z z z x x x x x x x x x x z z z z z z z z x x x x x x x . x x x x x z z z z z x x . x x x x x x x x x x z z z x x x x x x x x x x x x . x x x x x x x x x x x x z z z x x x x x x x x x x . x x z z z z z x x x x x . x x x x x x x z z z z z z x x x x x x x x x x x x z z z z z z x x x x x x x . x x z z z z z z z z x x . x x x x x x x z z z z z z x x x x x x x x x x x x z z z z z z x x x x x x x . x x x x x z z z z z x x . x x x x x x x x x x z z z x x x x x x x x x x x x . x x x x x x x x x x x x z z z x x x x x x x x x x . x x z z z z z x x x x x . x x x x x x x z z z z z z z z x x x x x x x x x x z z z z z z z z x x x x x 18x18 rectangle (36 + 6*48 = 18*18, 1/d = 9) 3 3 3 5 5 5 4 4 4 5 5 2 2 1 1 3 3 3 3 3 3 5 5 5 4 4 4 5 5 2 2 1 1 3 3 3 1 1 4 4 4 3 3 3 . 5 5 2 2 1 1 4 4 4 1 1 4 4 4 3 3 3 1 1 4 4 4 2 2 4 4 4 1 1 2 2 1 1 . . 1 1 4 4 4 2 2 3 3 3 5 5 2 2 1 1 . . 1 1 3 3 3 2 2 3 3 3 5 5 2 2 1 1 3 3 3 . 3 3 3 1 1 4 4 4 5 5 3 3 3 . 3 3 3 1 1 . . 1 1 4 4 4 1 1 3 3 3 1 1 . . 1 1 . . 1 1 3 3 3 1 1 4 4 4 1 1 . . 1 1 3 3 3 . 3 3 3 1 1 4 4 4 1 1 3 3 3 . 3 3 3 1 1 2 2 5 5 5 3 3 3 . 3 3 3 1 1 . . 1 1 2 2 5 5 5 3 3 3 1 1 . . 1 1 . . 1 1 2 2 2 2 1 1 . . 1 1 . . 1 1 3 3 3 4 4 4 2 2 1 1 . . 1 1 3 3 3 . 3 3 3 4 4 4 2 2 1 1 3 3 3 . 3 3 3 4 4 4 2 2 1 1 3 3 3 . 3 3 3 4 4 4 . 4 4 4 2 2 1 1 3 3 3 1 1 2 2 4 4 4 2 2 . . 2 2 1 1 4 4 4 1 1 2 2 3 3 3 2 2 4 4 4 3 3 3 4 4 4 1 1 2 2 3 3 3 2 2 4 4 4 3 3 3 14x23 rectangle (22 + 6*50 = 14*23, 1/d = 14.6) 1 1 4 4 4 2 2 3 3 3 1 1 4 4 4 3 3 3 1 1 3 3 3 1 1 4 4 4 2 2 3 3 3 1 1 4 4 4 3 3 3 1 1 3 3 3 1 1 3 3 3 2 2 . 2 2 1 1 . 1 1 4 4 4 1 1 . 1 1 2 2 3 3 3 . 1 1 2 2 . 2 2 1 1 4 4 4 3 3 3 1 1 2 2 1 1 2 2 1 1 2 2 . 2 2 1 1 . 1 1 3 3 3 1 1 2 2 1 1 2 2 1 1 . 1 1 2 2 . 2 2 1 1 4 4 4 3 3 3 3 1 1 2 2 . 2 2 1 1 . 1 1 2 2 1 1 4 4 4 3 3 3 3 4 4 4 1 1 2 2 1 1 . 1 1 2 2 . 2 2 1 1 3 3 3 3 4 4 4 1 1 2 2 . 2 2 1 1 . 1 1 2 2 1 1 2 2 1 1 3 3 3 1 1 . 1 1 2 2 . 2 2 1 1 2 2 1 1 2 2 1 1 3 3 3 4 4 4 1 1 2 2 . 2 2 1 1 . 3 3 3 2 2 1 1 . 1 1 4 4 4 1 1 . 1 1 2 2 . 2 2 3 3 3 1 1 3 3 3 1 1 3 3 3 4 4 4 1 1 3 3 3 2 2 4 4 4 1 1 3 3 3 1 1 3 3 3 4 4 4 1 1 3 3 3 2 2 4 4 4 1 1 17x17 rectangle (19 + 6*45 = 17*17, 1/d = 15.2) 3 3 4 4 1 1 1 4 4 3 3 2 2 2 1 1 1 3 3 4 4 1 1 1 4 4 3 3 2 2 2 1 1 1 3 3 4 4 2 2 2 4 4 3 3 1 1 1 2 2 2 2 2 2 . 2 2 2 . 2 2 2 1 1 1 2 2 2 2 2 2 4 4 1 1 1 2 2 2 . . 3 3 4 4 1 1 1 4 4 1 1 1 . . 1 1 1 3 3 4 4 1 1 1 4 4 . . 2 2 2 1 1 1 3 3 4 4 4 4 3 3 1 1 1 2 2 2 . . 4 4 1 1 1 4 4 3 3 1 1 1 . . 1 1 1 4 4 1 1 1 4 4 3 3 . . 2 2 2 1 1 1 4 4 2 2 2 2 2 2 1 1 1 2 2 2 . 2 2 2 . 2 2 2 2 2 2 1 1 1 3 3 4 4 2 2 2 4 4 3 3 1 1 1 3 3 . 3 3 4 4 1 1 1 4 4 3 3 1 1 1 3 3 . 3 3 4 4 1 1 1 4 4 3 3 3 3 . 3 3 4 4 5 5 3 3 4 4 3 3 4 4 3 3 1 1 1 4 4 5 5 3 3 4 4 3 3 4 4 3 3 1 1 1 4 4 5 5 3 3 4 4 3 3 4 4 12x17 rectangle (12 + 6*32 = 12*17, 1/d = 17) 4 4 4 1 1 2 2 1 1 3 3 3 4 4 4 1 1 4 4 4 1 1 2 2 1 1 3 3 3 4 4 4 1 1 3 3 3 1 1 2 2 1 1 4 4 4 1 1 . 1 1 3 3 3 . 3 3 3 2 2 4 4 4 1 1 4 4 4 2 2 1 1 3 3 3 2 2 . 2 2 1 1 4 4 4 2 2 1 1 . 1 1 2 2 . 2 2 . 2 2 1 1 2 2 1 1 . 1 1 . 1 1 2 2 . 2 2 1 1 4 4 4 2 2 1 1 . 1 1 3 3 3 2 2 1 1 4 4 4 2 2 4 4 4 1 1 3 3 3 . 3 3 3 2 2 . 2 2 4 4 4 2 2 1 1 2 2 3 3 3 2 2 4 4 4 3 3 3 2 2 1 1 2 2 4 4 4 2 2 4 4 4 3 3 3 2 2 1 1 2 2 4 4 4 10x12 rectangle (6 + 6*19 = 10*12, 1/d = 20) 4 4 4 1 1 2 2 3 3 3 4 4 4 1 1 2 2 3 3 3 3 3 3 1 1 2 2 4 4 4 3 3 3 . 3 3 3 4 4 4 2 2 1 1 3 3 3 5 5 5 2 2 1 1 . 1 1 5 5 5 2 2 1 1 . 1 1 . 1 1 4 4 4 2 2 1 1 . 1 1 4 4 4 2 2 4 4 4 1 1 2 2 . 2 2 4 4 4 2 2 2 2 4 4 4 3 3 3 2 2 2 2 4 4 4 3 3 3 2 2 10x27 rectangle (18 + 6*42 = 10*27, 1/d = 15) 3 3 3 5 5 5 4 4 4 1 1 2 2 3 3 3 5 5 5 4 4 4 1 1 2 2 1 1 4 4 4 3 3 3 . 1 1 2 2 1 1 4 4 4 3 3 3 2 2 4 4 4 1 1 . . 2 2 . . 2 2 4 4 4 2 2 4 4 4 2 2 . . 2 2 3 3 3 2 2 4 4 4 2 2 3 3 3 . 3 3 3 2 2 . 2 2 1 1 3 3 3 2 2 1 1 4 4 4 2 2 1 1 4 4 4 2 2 1 1 4 4 4 2 2 1 1 4 4 4 2 2 1 1 10x28 rectangle (22 + 6*43 = 10*28, 1/d = 12.7) m m 3 3 3 5 5 5 4 4 4 1 1 2 2 m m 3 3 3 5 5 5 4 4 4 1 1 2 2 m m . . 4 4 4 3 3 3 . 1 1 2 2 3 3 3 4 4 4 3 3 3 2 2 4 4 4 3 3 3 . . 2 2 . . 2 2 4 4 4 2 2 4 4 4 2 2 . . 2 2 3 3 3 2 2 4 4 4 2 2 3 3 3 . 3 3 3 2 2 . 2 2 1 1 3 3 3 2 2 1 1 4 4 4 2 2 1 1 4 4 4 2 2 1 1 4 4 4 2 2 1 1 4 4 4 2 2 1 1 27x27 rectangle (81 + 6*108 = 27*27, 1/d = 9) 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 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 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 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 . 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 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 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 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 (10+17i)x(10+17j) rectangle (i, j >= 1) 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 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 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 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 . 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 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 . 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 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 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 . . 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 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 . . 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 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 The 3x4 12-omino: It is more difficult to construct the border for this large piece. 24x27 rectangle (48 + 12*50 = 24*27, 1/d = 13.5) 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 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 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 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 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 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 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 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 Only the edge has been constructed for the highest hole density packing. . . . 2 2 2 . . . 2 2 2 . . . 2 2 2 4 4 4 4 . . 4 4 4 4 . . 4 4 4 4 2 2 2 4 4 4 4 2 2 2 . . . 2 2 2 . . . 2 2 2 . . . 2 2 2 4 4 4 4 . . 4 4 4 4 . . 4 4 4 4 . . 4 4 4 4 2 2 2 . . . 2 2 2 . . . 2 2 2 . . . 2 2 2 4 4 4 4 . . 4 4 4 4 . . 4 4 4 4 . . 4 4 4 4 2 2 2 . . . 2 2 2 . . . 2 2 2 . . . 2 2 2 . . . 2 2 2 4 4 4 4 . . 4 4 4 4 . . 4 4 4 4 2 2 2 . . . 2 2 2 . . . 2 2 2 . . . 2 2 2 . . . 2 2 2 4 4 4 4 . . 4 4 4 4 . . 4 4 4 4 2 2 2 . . . 2 2 2 . . . 2 2 2 . . . 2 2 2 . . . 2 2 2 4 4 4 4 . . 4 4 4 4 . . 4 4 4 4 2 2 2 4 4 4 4 2 2 2 . . . 2 2 2 . . . 2 2 2 . . . 2 2 2 4 4 4 4 . . 4 4 4 4 . . 4 4 4 4 . . 4 4 4 4 2 2 2 . . . 2 2 2 . . . 2 2 2 . . . 2 2 2 4 4 4 4 . . 4 4 4 4 . . 4 4 4 4 . . 4 4 4 4 2 2 2 . . . 2 2 2 . . . 2 2 2 . . . 2 2 2 1 1 1 2 2 2 4 4 4 4 . . 4 4 4 4 . . 4 4 4 4 2 2 2 . . . 2 2 2 . . . 2 2 2 1 1 1 2 2 2 1 1 1 2 2 2 4 4 4 4 . . 4 4 4 4 . . 4 4 4 4 2 2 2 . . . 2 2 2 1 1 1 2 2 2 1 1 1 2 2 2 1 1 1 2 2 2 4 4 4 4 . . 4 4 4 4 . . 4 4 4 4 2 2 2 1 1 1 2 2 2 1 1 1 2 2 2 1 1 1 2 2 2 1 1 1 2 2 2 4 4 4 4 . . 4 4 4 4 1 1 1 2 2 2 5 5 5 1 1 1 2 2 2 1 1 1 2 2 2 1 1 1 2 2 2 1 1 1 2 2 2 4 4 4 4 1 1 1 2 2 2 5 5 5 . 5 5 5 . . 1 1 1 2 2 2 1 1 1 2 2 2 1 1 1 2 2 2 3 3 3 3 1 1 1 2 2 2 5 5 5 . 5 5 5 4 4 4 4 3 3 3 3 1 1 1 2 2 2 1 1 1 2 2 2 3 3 3 3 1 1 1 2 2 2 5 5 5 . 5 5 5 4 4 4 4 3 3 3 3 . 5 5 5 . . 1 1 1 2 2 2 3 3 3 3 2 2 2 1 1 1 4 4 4 4 5 5 5 4 4 4 4 3 3 3 3 . 5 5 5 4 4 4 4 3 3 3 3 4 4 4 4 2 2 2 1 1 1 4 4 4 4 3 3 3 3 5 5 5 5 4 4 4 4 5 5 5 4 4 4 4 3 3 3 3 4 4 4 4 2 2 2 1 1 1 4 4 4 4 3 3 3 3 5 5 5 5 4 4 4 4 5 5 5 4 4 4 4 3 3 3 3 4 4 4 4 2 2 2 1 1 1 . 1 1 1 3 3 3 3 5 5 5 5 4 4 4 4 2 2 2 1 1 1 2 2 2 1 1 1 2 2 2 1 1 1 4 4 4 4 1 1 1 5 5 5 5 4 4 4 4 3 3 3 3 2 2 2 1 1 1 2 2 2 1 1 1 2 2 2 1 1 1 4 4 4 4 1 1 1 5 5 5 5 4 4 4 4 3 3 3 3 2 2 2 1 1 1 2 2 2 1 1 1 2 2 2 1 1 1 4 4 4 4 1 1 1 5 5 5 5 4 4 4 4 3 3 3 3 2 2 2 1 1 1 2 2 2 1 1 1 2 2 2 1 1 1 The 2x5 10-omino: It is difficult to construct the border for this large piece. Only the edge has been constructed for the highest hole density packing. 3 3 . . . . 3 3 . . . . 3 3 4 4 4 4 4 . 4 4 4 4 4 3 3 . . . . 3 3 . . . . 3 3 . . . . 3 3 . . . . 3 3 . . . . 3 3 4 4 4 4 4 . 4 4 4 4 4 3 3 . . . . 3 3 . . . . 3 3 . . . . 3 3 . . . . 3 3 . . . . 3 3 4 4 4 4 4 . 4 4 4 4 4 . 4 4 4 4 4 3 3 . . . . 3 3 . . . . 3 3 . . . . 3 3 . . . . 3 3 4 4 4 4 4 3 3 4 4 4 4 4 . 4 4 4 4 4 3 3 . . . . 3 3 . . . . 3 3 . . . . 3 3 . . . . 3 3 . . . . 3 3 4 4 4 4 4 . 4 4 4 4 4 3 3 . . . . 3 3 . . . . 3 3 . . . . 3 3 . . . . 3 3 . . . . 3 3 4 4 4 4 4 . 4 4 4 4 4 3 3 . . . . 3 3 . . . . 3 3 . . . . 3 3 . . . . 3 3 . . . . 3 3 4 4 4 4 4 . 4 4 4 4 4 3 3 . . . . 3 3 . . . . 3 3 . . . . 3 3 . . . . 3 3 . . . . 3 3 4 4 4 4 4 . 4 4 4 4 4 4 4 4 4 4 3 3 . . . . 3 3 . . . . 3 3 . . . . 3 3 . . . . 3 3 4 4 4 4 4 . 4 4 4 4 4 . 4 4 4 4 4 3 3 . . . . 3 3 . . . . 3 3 . . . . 3 3 1 1 2 2 3 3 1 1 2 2 3 3 4 4 4 4 4 . 4 4 4 4 4 3 3 . . . . 3 3 . . . . 3 3 1 1 2 2 3 3 1 1 2 2 3 3 1 1 2 2 3 3 4 4 4 4 4 . 4 4 4 4 4 3 3 . . . . 3 3 1 1 2 2 3 3 1 1 2 2 3 3 1 1 2 2 3 3 1 1 2 2 3 3 4 4 4 4 4 . 4 4 4 4 4 3 3 1 1 2 2 3 3 1 1 2 2 3 3 1 1 2 2 3 3 1 1 2 2 3 3 1 1 2 2 3 3 4 4 4 4 4 2 2 1 1 2 2 3 3 . 1 1 2 2 3 3 1 1 2 2 3 3 1 1 2 2 3 3 1 1 2 2 3 3 5 5 5 5 5 2 2 4 4 4 4 4 2 2 3 3 1 1 . 1 1 2 2 3 3 1 1 2 2 3 3 1 1 2 2 3 3 5 5 5 5 5 2 2 4 4 4 4 4 2 2 3 3 1 1 4 4 4 4 4 2 2 1 1 2 2 3 3 1 1 2 2 3 3 6 6 6 6 6 2 2 5 5 5 5 5 2 2 3 3 1 1 4 4 4 4 4 2 2 4 4 4 4 4 . 1 1 2 2 3 3 6 6 6 6 6 2 2 5 5 5 5 5 2 2 3 3 1 1 5 5 5 5 5 2 2 4 4 4 4 4 2 2 3 3 4 4 4 4 4 5 5 5 5 5 6 6 6 6 6 2 2 3 3 1 1 5 5 5 5 5 2 2 5 5 5 5 5 2 2 3 3 4 4 4 4 4 5 5 5 5 5 6 6 6 6 6 1 1 2 2 3 3 2 2 . . . 2 2 5 5 5 5 5 2 2 3 3 . 3 3 2 2 1 1 2 2 3 3 1 1 2 2 1 1 2 2 3 3 2 2 5 5 5 5 5 4 4 4 4 4 2 2 3 3 . 3 3 2 2 1 1 2 2 3 3 1 1 2 2 1 1 2 2 3 3 2 2 5 5 5 5 5 4 4 4 4 4 2 2 3 3 . 3 3 2 2 1 1 2 2 3 3 1 1 2 2 1 1 2 2 3 3 2 2 4 4 4 4 4 5 5 5 5 5 4 4 4 4 4 3 3 2 2 1 1 2 2 3 3 1 1 2 2 1 1 2 2 3 3 2 2 4 4 4 4 4 5 5 5 5 5 4 4 4 4 4 3 3 2 2 1 1 2 2 3 3 1 1 2 2 The 3x5 15-omino: Further complications occur in this case. References: [1] Frits G"obel, Bernhard Wiezorke; Problems for Einstein, CFF 34, Oct. 1994, 8-9 [2] Annecke Treep; Anti-slide... a winner!, CFF 35, Dec. 1994, 28 and title-page [3] Bill Sands; The Gunport Problem, Mathematics Magazine 44 (1971) 193-196 The Gunport Problem: What is the maximum number of 1-by-1 "holes" that can be obtained by arranging dominoes on an m-by-n field? [4] Martin Gardner; Knotted Doughnuts, Freeman, 1986, Chap 15.1: The Gunport Problem [5] A. Gyarfas, J. Lehel, Zs. Tuza; Clumsey Packing of Dominoes, Disc. Math. 71:1 (1988) 33-46 [6] Erich Friedman; Rigid Rectangles in Squares, http://www.stetson.edu/~efriedma/rigidrect/ [7] Ed Pegg Jr.; Put 28 dominoes into an 8x8 square so that none of the dominoes can slide. Arrange a set of dominoes to satisfy the above puzzle so that there are 21 pips on each row, column, and main diagonal. http://mathpuzzle.com/domsol.html -- mailto:Torsten.Sillke@uni-bielefeld.de http://www.mathematik.uni-bielefeld.de/~sillke/