Pentacube Problem: 5 times 2*2*5 Torsten Sillke -------------------------------- x x x x = 2*2 2*2*5n (for n=1..5) There are only 23 Pentacubes which fits into the 2*2*5 Box. Therefore the 2*2*30 Box is not possible, as one would need 24 Pentacubes. ==== BEGIN 5 times 2*2*5 impossible (K"unzell numbering used) Use the following weights for the 2*2*5 box: 2 1 0 1 2 2 1 0 1 2 2 1 0 1 2 2 1 0 1 2 This is the best weighting-function one can find. The maximal weight of the 20 heaviest pieces is equal the weight of the 5 boxes. One can now reject the remaining possibilities. Start with 61, which is the heaviest piece. This has to be used. The heaviest position is unique. a b c x 61 The 2*2*5 box after placing the 61. a b c x 61 a b c x 61 a b c 61 61 Which three other pieces could be in the same box? No piece get the maximal weight, unless it touches a 2*2 face. Therefore only the long pieces 11, 12, and 40 can fill the 3 cubes x. Each piece will fill one x, if it will lay with maximal weight. So this three pieces must be used. But this pieces are too heavy for the box. The remaining pieces don't have enough weigh for the other boxes. (Piece 37 can't be done too. See below.) Why is the weighting-function best possible? You can symmetrise a weighting-function, by taking the mean of all rotations of the given weighting-function. Now observe, that the symmetrised function can be not worse than the original function. (The mean is not greater than the maximum.) So an optimal weighting-function is of the form: a b c b a a b c b a a b c b a a b c b a Each box has (a,b,c) = (8,8,4) cubes. Now look for a counting solution for this boxes. Let the corresponding weights be wa, wb, and wc. The weight of a piece is the scalar product: (a,b,c)*(wa,wb,wc) = a*wa + b*wb + c*wc. As the weights need not be positive use w = (1,0,-1). The weight of the box according the this w is (8,8,4)*w = 4. The weight of (a,b,c) is therefore a-c. Possible arrangments of the pentacubes (with a-c maximal): This arrangments are possible with maximal weight. Each piece has a unique (a,b,c)-vector with maximal weight. (a,b,c) : a-c : Pentacubes ------------------------------ A = (4,1,0) : 4 : 61 B = (3,2,0) : 3 : 37 C = (3,1,1) : 2 : 41, 42, 81 D = (2,2,1) : 1 : 10, 11, 31, 32, 60, 71, 72 E = (1,3,1) : 0 : 12, 33, 34, 35, 36, 40, 51, 82 E'= (2,1,2) : 0 : 21, 22, 90 Find 5 combinations, which give (8,8,4). A + E + E + E' = (8,8,4) unique combination with A. B + D + E + E' = (8,8,4) unique combination with B. For the C there are two possibilities: 1. only one C in each box. C + D + D + E = (8,8,4) three times 2. one box contains two C. C + C + E + E = (8,8,4) C + D + D + E = (8,8,4) D + D + D + D = (8,8,4). So we found two counting solutions. But a counting-solutions shows that there is now symmetric weighting-function, which is better than even. And therefore there is no weighting-function at all, which will proof the non-existence of a packing. A refinment of the counting-solution towards a near-solution: 61, 90, 12, 51: 61 -1 90 90 90 61 -1 90 51 90 61 12 12 +1 12 61 61 51 +1 51 +1 is used twice: 12, 51 37, 10, 21, 36: 10 10 10 10 10 37 37 21 36 36 37 37 36 36 21 37 -1 21 +1 21 +1 is used twice: 21, 36 11, 40, 60, 42 40 40 60 60 60 42 42 42 60 60 42 40 40 40 11 42 11 11 11 11 The last two 2*2*5 boxes can be build from 4 times P5*2. Four pair of pentacubes forming a P5*2 (car): 31, 71 32, 72 33, 81 35, 41 This near-solution shows, there is no LP-Proof too, if one allows rational solutions. The integral LP-Problem is a representation of the packing problem. One gets a half-solution, if one computes the mean of two near solutions, e. g.: ( 61 -1 90 90 90 12 +1 12 12 61 ) ( 61 -1 90 51 90 51 +1 51 61 61 ) 1/2 * ( + ) ( 61 12 12 +1 12 90 90 90 -1 61 ) ( 61 61 51 +1 51 90 51 90 -1 61 ) ==== END 5 times 2*2*5 impossible