7
$\begingroup$

Can 42 1x2x4 cuboids be packed into a 7x7x7 cube without cutting any of them? Assume that all cuboids have their axes parallel to the axes of the big cube. I tried using https://www.jaapsch.net/puzzles/polysolver.htm but it didn't find any answer quickly enough. I also tried various coloring techniques to prove impossibility, but none seemed to work.

If it is impossible, is there any elegant proof?

41 cuboids is possible (image taken directly from Polyform Puzzle Solver): enter image description here

$\endgroup$
2
  • $\begingroup$ Similar: puzzling.stackexchange.com/questions/62780/… $\endgroup$
    – mathlander
    Mar 10 at 2:58
  • 2
    $\begingroup$ The analysis of the linked puzzle works on this one too, at least to some extent, so the 7 empty spots in a 42-piece solution are very restricted in their arrangement. The coordinates of each space is either all even or all odd, and no two spaces have any coordinate in common. $\endgroup$ Mar 10 at 10:34

1 Answer 1

8
$\begingroup$

Via integer linear programming, the maximum is

$41$.

For each of the $1008$ possible boxes $b$, let $C_b \subset [7] \times [7] \times [7]$ be the set of cells covered by $b$, and let binary decision variable $x_b$ indicate whether box $b$ is used. The problem is to maximize $\sum_b x_b$ subject to linear "packing" constraints $$\sum_{b: (i,j,k) \in C_b} x_b \le 1 \quad \text{for all $(i,j,k)\in [7]\times[7]\times[7]$}$$

The linear programming relaxation has maximum objective value

$41 + 9/11$,

achieved by the following fractional solution, where each row shows $C_b$ and $x_b$:

{(1,1,1),(1,1,2),(1,1,3),(1,1,4),(1,2,1),(1,2,2),(1,2,3),(1,2,4)} 1117/4576
{(1,1,4),(1,1,5),(1,1,6),(1,1,7),(1,2,4),(1,2,5),(1,2,6),(1,2,7)} 827/4576
{(1,2,1),(1,2,2),(1,2,3),(1,2,4),(1,3,1),(1,3,2),(1,3,3),(1,3,4)} 1265/4576
{(1,4,2),(1,4,3),(1,4,4),(1,4,5),(1,5,2),(1,5,3),(1,5,4),(1,5,5)} 388/4576
{(1,5,1),(1,5,2),(1,5,3),(1,5,4),(1,6,1),(1,6,2),(1,6,3),(1,6,4)} 365/4576
{(1,5,4),(1,5,5),(1,5,6),(1,5,7),(1,6,4),(1,6,5),(1,6,6),(1,6,7)} 1020/4576
{(1,6,1),(1,6,2),(1,6,3),(1,6,4),(1,7,1),(1,7,2),(1,7,3),(1,7,4)} 86/4576
{(1,6,4),(1,6,5),(1,6,6),(1,6,7),(1,7,4),(1,7,5),(1,7,6),(1,7,7)} 1430/4576
{(2,2,1),(2,2,2),(2,2,3),(2,2,4),(2,3,1),(2,3,2),(2,3,3),(2,3,4)} 586/4576
{(2,2,4),(2,2,5),(2,2,6),(2,2,7),(2,3,4),(2,3,5),(2,3,6),(2,3,7)} 807/4576
{(2,5,1),(2,5,2),(2,5,3),(2,5,4),(2,6,1),(2,6,2),(2,6,3),(2,6,4)} 1130/4576
{(3,1,3),(3,1,4),(3,1,5),(3,1,6),(3,2,3),(3,2,4),(3,2,5),(3,2,6)} 266/4576
{(3,2,2),(3,2,3),(3,2,4),(3,2,5),(3,3,2),(3,3,3),(3,3,4),(3,3,5)} 278/4576
{(3,4,2),(3,4,3),(3,4,4),(3,4,5),(3,5,2),(3,5,3),(3,5,4),(3,5,5)} 171/4576
{(3,4,3),(3,4,4),(3,4,5),(3,4,6),(3,5,3),(3,5,4),(3,5,5),(3,5,6)} 829/4576
{(3,6,1),(3,6,2),(3,6,3),(3,6,4),(3,7,1),(3,7,2),(3,7,3),(3,7,4)} 790/4576
{(3,6,2),(3,6,3),(3,6,4),(3,6,5),(3,7,2),(3,7,3),(3,7,4),(3,7,5)} 217/4576
{(3,6,3),(3,6,4),(3,6,5),(3,6,6),(3,7,3),(3,7,4),(3,7,5),(3,7,6)} 615/4576
{(4,3,1),(4,3,2),(4,3,3),(4,3,4),(4,4,1),(4,4,2),(4,4,3),(4,4,4)} 506/4576
{(4,3,4),(4,3,5),(4,3,6),(4,3,7),(4,4,4),(4,4,5),(4,4,6),(4,4,7)} 278/4576
{(4,6,1),(4,6,2),(4,6,3),(4,6,4),(4,7,1),(4,7,2),(4,7,3),(4,7,4)} 890/4576
{(4,6,4),(4,6,5),(4,6,6),(4,6,7),(4,7,4),(4,7,5),(4,7,6),(4,7,7)} 275/4576
{(5,1,2),(5,1,3),(5,1,4),(5,1,5),(5,2,2),(5,2,3),(5,2,4),(5,2,5)} 658/4576
{(5,1,3),(5,1,4),(5,1,5),(5,1,6),(5,2,3),(5,2,4),(5,2,5),(5,2,6)} 910/4576
{(5,3,2),(5,3,3),(5,3,4),(5,3,5),(5,4,2),(5,4,3),(5,4,4),(5,4,5)} 368/4576
{(5,3,3),(5,3,4),(5,3,5),(5,3,6),(5,4,3),(5,4,4),(5,4,5),(5,4,6)} 1443/4576
{(5,4,2),(5,4,3),(5,4,4),(5,4,5),(5,5,2),(5,5,3),(5,5,4),(5,5,5)} 300/4576
{(5,5,3),(5,5,4),(5,5,5),(5,5,6),(5,6,3),(5,6,4),(5,6,5),(5,6,6)} 319/4576
{(5,6,1),(5,6,2),(5,6,3),(5,6,4),(5,7,1),(5,7,2),(5,7,3),(5,7,4)} 569/4576
{(5,6,2),(5,6,3),(5,6,4),(5,6,5),(5,7,2),(5,7,3),(5,7,4),(5,7,5)} 722/4576
{(5,6,4),(5,6,5),(5,6,6),(5,6,7),(5,7,4),(5,7,5),(5,7,6),(5,7,7)} 868/4576
{(6,2,1),(6,2,2),(6,2,3),(6,2,4),(6,3,1),(6,3,2),(6,3,3),(6,3,4)} 905/4576
{(6,2,3),(6,2,4),(6,2,5),(6,2,6),(6,3,3),(6,3,4),(6,3,5),(6,3,6)} 110/4576
{(6,2,4),(6,2,5),(6,2,6),(6,2,7),(6,3,4),(6,3,5),(6,3,6),(6,3,7)} 1177/4576
{(6,5,4),(6,5,5),(6,5,6),(6,5,7),(6,6,4),(6,6,5),(6,6,6),(6,6,7)} 912/4576
{(7,1,1),(7,1,2),(7,1,3),(7,1,4),(7,2,1),(7,2,2),(7,2,3),(7,2,4)} 212/4576
{(7,1,4),(7,1,5),(7,1,6),(7,1,7),(7,2,4),(7,2,5),(7,2,6),(7,2,7)} 684/4576
{(7,2,1),(7,2,2),(7,2,3),(7,2,4),(7,3,1),(7,3,2),(7,3,3),(7,3,4)} 119/4576
{(7,2,4),(7,2,5),(7,2,6),(7,2,7),(7,3,4),(7,3,5),(7,3,6),(7,3,7)} 2135/4576
{(7,3,3),(7,3,4),(7,3,5),(7,3,6),(7,4,3),(7,4,4),(7,4,5),(7,4,6)} 266/4576
{(7,5,1),(7,5,2),(7,5,3),(7,5,4),(7,6,1),(7,6,2),(7,6,3),(7,6,4)} 950/4576
{(7,5,4),(7,5,5),(7,5,6),(7,5,7),(7,6,4),(7,6,5),(7,6,6),(7,6,7)} 167/4576
{(7,6,1),(7,6,2),(7,6,3),(7,6,4),(7,7,1),(7,7,2),(7,7,3),(7,7,4)} 1504/4576
{(1,1,2),(1,1,3),(1,2,2),(1,2,3),(1,3,2),(1,3,3),(1,4,2),(1,4,3)} 446/4576
{(1,1,5),(1,1,6),(1,2,5),(1,2,6),(1,3,5),(1,3,6),(1,4,5),(1,4,6)} 1083/4576
{(1,1,6),(1,1,7),(1,2,6),(1,2,7),(1,3,6),(1,3,7),(1,4,6),(1,4,7)} 931/4576
{(1,2,1),(1,2,2),(1,3,1),(1,3,2),(1,4,1),(1,4,2),(1,5,1),(1,5,2)} 147/4576
{(1,2,4),(1,2,5),(1,3,4),(1,3,5),(1,4,4),(1,4,5),(1,5,4),(1,5,5)} 636/4576
{(1,3,3),(1,3,4),(1,4,3),(1,4,4),(1,5,3),(1,5,4),(1,6,3),(1,6,4)} 237/4576
{(1,3,6),(1,3,7),(1,4,6),(1,4,7),(1,5,6),(1,5,7),(1,6,6),(1,6,7)} 192/4576
{(1,4,1),(1,4,2),(1,5,1),(1,5,2),(1,6,1),(1,6,2),(1,7,1),(1,7,2)} 1369/4576
{(1,4,2),(1,4,3),(1,5,2),(1,5,3),(1,6,2),(1,6,3),(1,7,2),(1,7,3)} 995/4576
{(1,4,5),(1,4,6),(1,5,5),(1,5,6),(1,6,5),(1,6,6),(1,7,5),(1,7,6)} 430/4576
{(1,4,6),(1,4,7),(1,5,6),(1,5,7),(1,6,6),(1,6,7),(1,7,6),(1,7,7)} 993/4576
{(2,1,2),(2,1,3),(2,2,2),(2,2,3),(2,3,2),(2,3,3),(2,4,2),(2,4,3)} 740/4576
{(2,1,5),(2,1,6),(2,2,5),(2,2,6),(2,3,5),(2,3,6),(2,4,5),(2,4,6)} 401/4576
{(2,4,5),(2,4,6),(2,5,5),(2,5,6),(2,6,5),(2,6,6),(2,7,5),(2,7,6)} 1364/4576
{(3,1,1),(3,1,2),(3,2,1),(3,2,2),(3,3,1),(3,3,2),(3,4,1),(3,4,2)} 1384/4576
{(3,1,6),(3,1,7),(3,2,6),(3,2,7),(3,3,6),(3,3,7),(3,4,6),(3,4,7)} 553/4576
{(3,2,3),(3,2,4),(3,3,3),(3,3,4),(3,4,3),(3,4,4),(3,5,3),(3,5,4)} 962/4576
{(3,2,6),(3,2,7),(3,3,6),(3,3,7),(3,4,6),(3,4,7),(3,5,6),(3,5,7)} 560/4576
{(3,3,1),(3,3,2),(3,4,1),(3,4,2),(3,5,1),(3,5,2),(3,6,1),(3,6,2)} 451/4576
{(3,4,6),(3,4,7),(3,5,6),(3,5,7),(3,6,6),(3,6,7),(3,7,6),(3,7,7)} 941/4576
{(4,1,1),(4,1,2),(4,2,1),(4,2,2),(4,3,1),(4,3,2),(4,4,1),(4,4,2)} 2139/4576
{(4,1,6),(4,1,7),(4,2,6),(4,2,7),(4,3,6),(4,3,7),(4,4,6),(4,4,7)} 642/4576
{(4,4,3),(4,4,4),(4,5,3),(4,5,4),(4,6,3),(4,6,4),(4,7,3),(4,7,4)} 228/4576
{(4,4,6),(4,4,7),(4,5,6),(4,5,7),(4,6,6),(4,6,7),(4,7,6),(4,7,7)} 1892/4576
{(5,1,1),(5,1,2),(5,2,1),(5,2,2),(5,3,1),(5,3,2),(5,4,1),(5,4,2)} 679/4576
{(5,1,6),(5,1,7),(5,2,6),(5,2,7),(5,3,6),(5,3,7),(5,4,6),(5,4,7)} 1049/4576
{(5,2,1),(5,2,2),(5,3,1),(5,3,2),(5,4,1),(5,4,2),(5,5,1),(5,5,2)} 504/4576
{(5,2,4),(5,2,5),(5,3,4),(5,3,5),(5,4,4),(5,4,5),(5,5,4),(5,5,5)} 278/4576
{(5,2,6),(5,2,7),(5,3,6),(5,3,7),(5,4,6),(5,4,7),(5,5,6),(5,5,7)} 463/4576
{(5,3,1),(5,3,2),(5,4,1),(5,4,2),(5,5,1),(5,5,2),(5,6,1),(5,6,2)} 348/4576
{(5,3,3),(5,3,4),(5,4,3),(5,4,4),(5,5,3),(5,5,4),(5,6,3),(5,6,4)} 405/4576
{(6,1,2),(6,1,3),(6,2,2),(6,2,3),(6,3,2),(6,3,3),(6,4,2),(6,4,3)} 322/4576
{(6,1,5),(6,1,6),(6,2,5),(6,2,6),(6,3,5),(6,3,6),(6,4,5),(6,4,6)} 1135/4576
{(6,4,2),(6,4,3),(6,5,2),(6,5,3),(6,6,2),(6,6,3),(6,7,2),(6,7,3)} 1475/4576
{(7,1,1),(7,1,2),(7,2,1),(7,2,2),(7,3,1),(7,3,2),(7,4,1),(7,4,2)} 2275/4576
{(7,1,2),(7,1,3),(7,2,2),(7,2,3),(7,3,2),(7,3,3),(7,4,2),(7,4,3)} 1006/4576
{(7,1,5),(7,1,6),(7,2,5),(7,2,6),(7,3,5),(7,3,6),(7,4,5),(7,4,6)} 451/4576
{(7,2,1),(7,2,2),(7,3,1),(7,3,2),(7,4,1),(7,4,2),(7,5,1),(7,5,2)} 504/4576
{(7,3,4),(7,3,5),(7,4,4),(7,4,5),(7,5,4),(7,5,5),(7,6,4),(7,6,5)} 553/4576
{(7,4,1),(7,4,2),(7,5,1),(7,5,2),(7,6,1),(7,6,2),(7,7,1),(7,7,2)} 164/4576
{(7,4,2),(7,4,3),(7,5,2),(7,5,3),(7,6,2),(7,6,3),(7,7,2),(7,7,3)} 525/4576
{(7,4,5),(7,4,6),(7,5,5),(7,5,6),(7,6,5),(7,6,6),(7,7,5),(7,7,6)} 786/4576
{(7,4,6),(7,4,7),(7,5,6),(7,5,7),(7,6,6),(7,6,7),(7,7,6),(7,7,7)} 2044/4576
{(1,1,1),(1,1,2),(1,1,3),(1,1,4),(2,1,1),(2,1,2),(2,1,3),(2,1,4)} 586/4576
{(1,1,2),(1,1,3),(1,1,4),(1,1,5),(2,1,2),(2,1,3),(2,1,4),(2,1,5)} 285/4576
{(1,1,4),(1,1,5),(1,1,6),(1,1,7),(2,1,4),(2,1,5),(2,1,6),(2,1,7)} 1030/4576
{(1,3,1),(1,3,2),(1,3,3),(1,3,4),(2,3,1),(2,3,2),(2,3,3),(2,3,4)} 340/4576
{(1,3,2),(1,3,3),(1,3,4),(1,3,5),(2,3,2),(2,3,3),(2,3,4),(2,3,5)} 679/4576
{(1,3,3),(1,3,4),(1,3,5),(1,3,6),(2,3,3),(2,3,4),(2,3,5),(2,3,6)} 510/4576
{(1,3,4),(1,3,5),(1,3,6),(1,3,7),(2,3,4),(2,3,5),(2,3,6),(2,3,7)} 909/4576
{(1,4,1),(1,4,2),(1,4,3),(1,4,4),(2,4,1),(2,4,2),(2,4,3),(2,4,4)} 550/4576
{(1,4,4),(1,4,5),(1,4,6),(1,4,7),(2,4,4),(2,4,5),(2,4,6),(2,4,7)} 947/4576
{(1,5,2),(1,5,3),(1,5,4),(1,5,5),(2,5,2),(2,5,3),(2,5,4),(2,5,5)} 160/4576
{(1,5,4),(1,5,5),(1,5,6),(1,5,7),(2,5,4),(2,5,5),(2,5,6),(2,5,7)} 1430/4576
{(1,7,1),(1,7,2),(1,7,3),(1,7,4),(2,7,1),(2,7,2),(2,7,3),(2,7,4)} 1007/4576
{(1,7,3),(1,7,4),(1,7,5),(1,7,6),(2,7,3),(2,7,4),(2,7,5),(2,7,6)} 192/4576
{(1,7,4),(1,7,5),(1,7,6),(1,7,7),(2,7,4),(2,7,5),(2,7,6),(2,7,7)} 423/4576
{(2,1,1),(2,1,2),(2,1,3),(2,1,4),(3,1,1),(3,1,2),(3,1,3),(3,1,4)} 389/4576
{(2,1,4),(2,1,5),(2,1,6),(2,1,7),(3,1,4),(3,1,5),(3,1,6),(3,1,7)} 1325/4576
{(2,2,1),(2,2,2),(2,2,3),(2,2,4),(3,2,1),(3,2,2),(3,2,3),(3,2,4)} 781/4576
{(2,2,4),(2,2,5),(2,2,6),(2,2,7),(3,2,4),(3,2,5),(3,2,6),(3,2,7)} 762/4576
{(2,6,4),(2,6,5),(2,6,6),(2,6,7),(3,6,4),(3,6,5),(3,6,6),(3,6,7)} 1516/4576
{(2,7,1),(2,7,2),(2,7,3),(2,7,4),(3,7,1),(3,7,2),(3,7,3),(3,7,4)} 1020/4576
{(2,7,4),(2,7,5),(2,7,6),(2,7,7),(3,7,4),(3,7,5),(3,7,6),(3,7,7)} 496/4576
{(3,1,2),(3,1,3),(3,1,4),(3,1,5),(4,1,2),(4,1,3),(4,1,4),(4,1,5)} 227/4576
{(3,1,3),(3,1,4),(3,1,5),(3,1,6),(4,1,3),(4,1,4),(4,1,5),(4,1,6)} 612/4576
{(3,3,2),(3,3,3),(3,3,4),(3,3,5),(4,3,2),(4,3,3),(4,3,4),(4,3,5)} 232/4576
{(3,3,3),(3,3,4),(3,3,5),(3,3,6),(4,3,3),(4,3,4),(4,3,5),(4,3,6)} 1084/4576
{(4,5,2),(4,5,3),(4,5,4),(4,5,5),(5,5,2),(5,5,3),(5,5,4),(5,5,5)} 192/4576
{(4,5,3),(4,5,4),(4,5,5),(4,5,6),(5,5,3),(5,5,4),(5,5,5),(5,5,6)} 808/4576
{(4,7,2),(4,7,3),(4,7,4),(4,7,5),(5,7,2),(5,7,3),(5,7,4),(5,7,5)} 721/4576
{(4,7,3),(4,7,4),(4,7,5),(4,7,6),(5,7,3),(5,7,4),(5,7,5),(5,7,6)} 192/4576
{(5,1,1),(5,1,2),(5,1,3),(5,1,4),(6,1,1),(6,1,2),(6,1,3),(6,1,4)} 896/4576
{(5,2,4),(5,2,5),(5,2,6),(5,2,7),(6,2,4),(6,2,5),(6,2,6),(6,2,7)} 848/4576
{(5,3,2),(5,3,3),(5,3,4),(5,3,5),(6,3,2),(6,3,3),(6,3,4),(6,3,5)} 402/4576
{(5,6,1),(5,6,2),(5,6,3),(5,6,4),(6,6,1),(6,6,2),(6,6,3),(6,6,4)} 1504/4576
{(5,6,4),(5,6,5),(5,6,6),(5,6,7),(6,6,4),(6,6,5),(6,6,6),(6,6,7)} 189/4576
{(5,7,1),(5,7,2),(5,7,3),(5,7,4),(6,7,1),(6,7,2),(6,7,3),(6,7,4)} 718/4576
{(5,7,4),(5,7,5),(5,7,6),(5,7,7),(6,7,4),(6,7,5),(6,7,6),(6,7,7)} 786/4576
{(6,1,1),(6,1,2),(6,1,3),(6,1,4),(7,1,1),(7,1,2),(7,1,3),(7,1,4)} 1015/4576
{(6,1,4),(6,1,5),(6,1,6),(6,1,7),(7,1,4),(7,1,5),(7,1,6),(7,1,7)} 1239/4576
{(6,3,1),(6,3,2),(6,3,3),(6,3,4),(7,3,1),(7,3,2),(7,3,3),(7,3,4)} 672/4576
{(6,3,4),(6,3,5),(6,3,6),(6,3,7),(7,3,4),(7,3,5),(7,3,6),(7,3,7)} 831/4576
{(6,4,4),(6,4,5),(6,4,6),(6,4,7),(7,4,4),(7,4,5),(7,4,6),(7,4,7)} 1029/4576
{(6,5,2),(6,5,3),(6,5,4),(6,5,5),(7,5,2),(7,5,3),(7,5,4),(7,5,5)} 548/4576
{(6,5,3),(6,5,4),(6,5,5),(6,5,6),(7,5,3),(7,5,4),(7,5,5),(7,5,6)} 956/4576
{(6,7,1),(6,7,2),(6,7,3),(6,7,4),(7,7,1),(7,7,2),(7,7,3),(7,7,4)} 164/4576
{(6,7,2),(6,7,3),(6,7,4),(6,7,5),(7,7,2),(7,7,3),(7,7,4),(7,7,5)} 446/4576
{(6,7,4),(6,7,5),(6,7,6),(6,7,7),(7,7,4),(7,7,5),(7,7,6),(7,7,7)} 1060/4576
{(1,1,1),(1,2,1),(1,3,1),(1,4,1),(2,1,1),(2,2,1),(2,3,1),(2,4,1)} 1554/4576
{(1,1,7),(1,2,7),(1,3,7),(1,4,7),(2,1,7),(2,2,7),(2,3,7),(2,4,7)} 572/4576
{(1,2,3),(1,3,3),(1,4,3),(1,5,3),(2,2,3),(2,3,3),(2,4,3),(2,5,3)} 976/4576
{(1,3,1),(1,4,1),(1,5,1),(1,6,1),(2,3,1),(2,4,1),(2,5,1),(2,6,1)} 275/4576
{(1,3,5),(1,4,5),(1,5,5),(1,6,5),(2,3,5),(2,4,5),(2,5,5),(2,6,5)} 106/4576
{(1,4,3),(1,5,3),(1,6,3),(1,7,3),(2,4,3),(2,5,3),(2,6,3),(2,7,3)} 492/4576
{(1,4,7),(1,5,7),(1,6,7),(1,7,7),(2,4,7),(2,5,7),(2,6,7),(2,7,7)} 941/4576
{(2,1,1),(2,2,1),(2,3,1),(2,4,1),(3,1,1),(3,2,1),(3,3,1),(3,4,1)} 826/4576
{(2,1,2),(2,2,2),(2,3,2),(2,4,2),(3,1,2),(3,2,2),(3,3,2),(3,4,2)} 434/4576
{(2,1,6),(2,2,6),(2,3,6),(2,4,6),(3,1,6),(3,2,6),(3,3,6),(3,4,6)} 700/4576
{(2,1,7),(2,2,7),(2,3,7),(2,4,7),(3,1,7),(3,2,7),(3,3,7),(3,4,7)} 189/4576
{(2,2,2),(2,3,2),(2,4,2),(2,5,2),(3,2,2),(3,3,2),(3,4,2),(3,5,2)} 98/4576
{(2,4,1),(2,5,1),(2,6,1),(2,7,1),(3,4,1),(3,5,1),(3,6,1),(3,7,1)} 690/4576
{(2,4,2),(2,5,2),(2,6,2),(2,7,2),(3,4,2),(3,5,2),(3,6,2),(3,7,2)} 1357/4576
{(2,4,6),(2,5,6),(2,6,6),(2,7,6),(3,4,6),(3,5,6),(3,6,6),(3,7,6)} 993/4576
{(2,4,7),(2,5,7),(2,6,7),(2,7,7),(3,4,7),(3,5,7),(3,6,7),(3,7,7)} 1927/4576
{(3,1,4),(3,2,4),(3,3,4),(3,4,4),(4,1,4),(4,2,4),(4,3,4),(4,4,4)} 796/4576
{(3,2,3),(3,3,3),(3,4,3),(3,5,3),(4,2,3),(4,3,3),(4,4,3),(4,5,3)} 796/4576
{(3,2,5),(3,3,5),(3,4,5),(3,5,5),(4,2,5),(4,3,5),(4,4,5),(4,5,5)} 664/4576
{(3,3,5),(3,4,5),(3,5,5),(3,6,5),(4,3,5),(4,4,5),(4,5,5),(4,6,5)} 638/4576
{(4,1,4),(4,2,4),(4,3,4),(4,4,4),(5,1,4),(5,2,4),(5,3,4),(5,4,4)} 456/4576
{(4,2,3),(4,3,3),(4,4,3),(4,5,3),(5,2,3),(5,3,3),(5,4,3),(5,5,3)} 734/4576
{(4,3,7),(4,4,7),(4,5,7),(4,6,7),(5,3,7),(5,4,7),(5,5,7),(5,6,7)} 1020/4576
{(5,1,1),(5,2,1),(5,3,1),(5,4,1),(6,1,1),(6,2,1),(6,3,1),(6,4,1)} 1449/4576
{(5,1,2),(5,2,2),(5,3,2),(5,4,2),(6,1,2),(6,2,2),(6,3,2),(6,4,2)} 2275/4576
{(5,1,7),(5,2,7),(5,3,7),(5,4,7),(6,1,7),(6,2,7),(6,3,7),(6,4,7)} 528/4576
{(5,3,5),(5,4,5),(5,5,5),(5,6,5),(6,3,5),(6,4,5),(6,5,5),(6,6,5)} 405/4576
{(5,4,1),(5,5,1),(5,6,1),(5,7,1),(6,4,1),(6,5,1),(6,6,1),(6,7,1)} 950/4576
{(5,4,6),(5,5,6),(5,6,6),(5,7,6),(6,4,6),(6,5,6),(6,6,6),(6,7,6)} 1621/4576
{(5,4,7),(5,5,7),(5,6,7),(5,7,7),(6,4,7),(6,5,7),(6,6,7),(6,7,7)} 1110/4576
{(6,1,3),(6,2,3),(6,3,3),(6,4,3),(7,1,3),(7,2,3),(7,3,3),(7,4,3)} 1182/4576
{(6,1,7),(6,2,7),(6,3,7),(6,4,7),(7,1,7),(7,2,7),(7,3,7),(7,4,7)} 335/4576
{(6,2,1),(6,3,1),(6,4,1),(6,5,1),(7,2,1),(7,3,1),(7,4,1),(7,5,1)} 614/4576
{(6,2,3),(6,3,3),(6,4,3),(6,5,3),(7,2,3),(7,3,3),(7,4,3),(7,5,3)} 504/4576
{(6,3,7),(6,4,7),(6,5,7),(6,6,7),(7,3,7),(7,4,7),(7,5,7),(7,6,7)} 1168/4576
{(6,4,1),(6,5,1),(6,6,1),(6,7,1),(7,4,1),(7,5,1),(7,6,1),(7,7,1)} 917/4576
{(6,4,3),(6,5,3),(6,6,3),(6,7,3),(7,4,3),(7,5,3),(7,6,3),(7,7,3)} 1093/4576
{(6,4,4),(6,5,4),(6,6,4),(6,7,4),(7,4,4),(7,5,4),(7,6,4),(7,7,4)} 1402/4576
{(6,4,5),(6,5,5),(6,6,5),(6,7,5),(7,4,5),(7,5,5),(7,6,5),(7,7,5)} 997/4576
{(1,1,1),(1,1,2),(2,1,1),(2,1,2),(3,1,1),(3,1,2),(4,1,1),(4,1,2)} 885/4576
{(1,1,2),(1,1,3),(2,1,2),(2,1,3),(3,1,2),(3,1,3),(4,1,2),(4,1,3)} 1257/4576
{(1,1,5),(1,1,6),(2,1,5),(2,1,6),(3,1,5),(3,1,6),(4,1,5),(4,1,6)} 105/4576
{(1,1,6),(1,1,7),(2,1,6),(2,1,7),(3,1,6),(3,1,7),(4,1,6),(4,1,7)} 600/4576
{(1,2,2),(1,2,3),(2,2,2),(2,2,3),(3,2,2),(3,2,3),(4,2,2),(4,2,3)} 404/4576
{(1,2,5),(1,2,6),(2,2,5),(2,2,6),(3,2,5),(3,2,6),(4,2,5),(4,2,6)} 784/4576
{(1,3,1),(1,3,2),(2,3,1),(2,3,2),(3,3,1),(3,3,2),(4,3,1),(4,3,2)} 502/4576
{(1,4,1),(1,4,2),(2,4,1),(2,4,2),(3,4,1),(3,4,2),(4,4,1),(4,4,2)} 681/4576
{(1,4,3),(1,4,4),(2,4,3),(2,4,4),(3,4,3),(3,4,4),(4,4,3),(4,4,4)} 492/4576
{(1,4,4),(1,4,5),(2,4,4),(2,4,5),(3,4,4),(3,4,5),(4,4,4),(4,4,5)} 986/4576
{(1,5,1),(1,5,2),(2,5,1),(2,5,2),(3,5,1),(3,5,2),(4,5,1),(4,5,2)} 1107/4576
{(1,6,2),(1,6,3),(2,6,2),(2,6,3),(3,6,2),(3,6,3),(4,6,2),(4,6,3)} 1716/4576
{(1,7,2),(1,7,3),(2,7,2),(2,7,3),(3,7,2),(3,7,3),(4,7,2),(4,7,3)} 1119/4576
{(1,7,5),(1,7,6),(2,7,5),(2,7,6),(3,7,5),(3,7,6),(4,7,5),(4,7,6)} 511/4576
{(1,7,6),(1,7,7),(2,7,6),(2,7,7),(3,7,6),(3,7,7),(4,7,6),(4,7,7)} 597/4576
{(2,1,3),(2,1,4),(3,1,3),(3,1,4),(4,1,3),(4,1,4),(5,1,3),(5,1,4)} 230/4576
{(2,1,6),(2,1,7),(3,1,6),(3,1,7),(4,1,6),(4,1,7),(5,1,6),(5,1,7)} 415/4576
{(2,3,3),(2,3,4),(3,3,3),(3,3,4),(4,3,3),(4,3,4),(5,3,3),(5,3,4)} 745/4576
{(2,3,6),(2,3,7),(3,3,6),(3,3,7),(4,3,6),(4,3,7),(5,3,6),(5,3,7)} 298/4576
{(2,5,1),(2,5,2),(3,5,1),(3,5,2),(4,5,1),(4,5,2),(5,5,1),(5,5,2)} 679/4576
{(2,5,4),(2,5,5),(3,5,4),(3,5,5),(4,5,4),(4,5,5),(5,5,4),(5,5,5)} 1516/4576
{(2,5,6),(2,5,7),(3,5,6),(3,5,7),(4,5,6),(4,5,7),(5,5,6),(5,5,7)} 278/4576
{(2,7,1),(2,7,2),(3,7,1),(3,7,2),(4,7,1),(4,7,2),(5,7,1),(5,7,2)} 73/4576
{(3,3,3),(3,3,4),(4,3,3),(4,3,4),(5,3,3),(5,3,4),(6,3,3),(6,3,4)} 479/4576
{(3,3,6),(3,3,7),(4,3,6),(4,3,7),(5,3,6),(5,3,7),(6,3,6),(6,3,7)} 430/4576
{(3,5,1),(3,5,2),(4,5,1),(4,5,2),(5,5,1),(5,5,2),(6,5,1),(6,5,2)} 668/4576
{(3,5,4),(3,5,5),(4,5,4),(4,5,5),(5,5,4),(5,5,5),(6,5,4),(6,5,5)} 758/4576
{(3,5,6),(3,5,7),(4,5,6),(4,5,7),(5,5,6),(5,5,7),(6,5,6),(6,5,7)} 464/4576
{(3,7,6),(3,7,7),(4,7,6),(4,7,7),(5,7,6),(5,7,7),(6,7,6),(6,7,7)} 423/4576
{(4,1,2),(4,1,3),(5,1,2),(5,1,3),(6,1,2),(6,1,3),(7,1,2),(7,1,3)} 68/4576
{(4,1,5),(4,1,6),(5,1,5),(5,1,6),(6,1,5),(6,1,6),(7,1,5),(7,1,6)} 1309/4576
{(4,1,6),(4,1,7),(5,1,6),(5,1,7),(6,1,6),(6,1,7),(7,1,6),(7,1,7)} 893/4576
{(4,2,2),(4,2,3),(5,2,2),(5,2,3),(6,2,2),(6,2,3),(7,2,2),(7,2,3)} 460/4576
{(4,2,5),(4,2,6),(5,2,5),(5,2,6),(6,2,5),(6,2,6),(7,2,5),(7,2,6)} 413/4576
{(4,4,1),(4,4,2),(5,4,1),(5,4,2),(6,4,1),(6,4,2),(7,4,1),(7,4,2)} 102/4576
{(4,4,4),(4,4,5),(5,4,4),(5,4,5),(6,4,4),(6,4,5),(7,4,4),(7,4,5)} 494/4576
{(4,5,1),(4,5,2),(5,5,1),(5,5,2),(6,5,1),(6,5,2),(7,5,1),(7,5,2)} 956/4576
{(4,5,6),(4,5,7),(5,5,6),(5,5,7),(6,5,6),(6,5,7),(7,5,6),(7,5,7)} 516/4576
{(4,6,2),(4,6,3),(5,6,2),(5,6,3),(6,6,2),(6,6,3),(7,6,2),(7,6,3)} 504/4576
{(4,6,5),(4,6,6),(5,6,5),(5,6,6),(6,6,5),(6,6,6),(7,6,5),(7,6,6)} 1472/4576
{(4,7,1),(4,7,2),(5,7,1),(5,7,2),(6,7,1),(6,7,2),(7,7,1),(7,7,2)} 1093/4576
{(4,7,2),(4,7,3),(5,7,2),(5,7,3),(6,7,2),(6,7,3),(7,7,2),(7,7,3)} 680/4576
{(4,7,5),(4,7,6),(5,7,5),(5,7,6),(6,7,5),(6,7,6),(7,7,5),(7,7,6)} 686/4576
{(1,1,3),(1,2,3),(2,1,3),(2,2,3),(3,1,3),(3,2,3),(4,1,3),(4,2,3)} 368/4576
{(1,1,4),(1,2,4),(2,1,4),(2,2,4),(3,1,4),(3,2,4),(4,1,4),(4,2,4)} 731/4576
{(1,1,5),(1,2,5),(2,1,5),(2,2,5),(3,1,5),(3,2,5),(4,1,5),(4,2,5)} 1246/4576
{(1,1,7),(1,2,7),(2,1,7),(2,2,7),(3,1,7),(3,2,7),(4,1,7),(4,2,7)} 445/4576
{(1,2,1),(1,3,1),(2,2,1),(2,3,1),(3,2,1),(3,3,1),(4,2,1),(4,3,1)} 493/4576
{(1,2,2),(1,3,2),(2,2,2),(2,3,2),(3,2,2),(3,3,2),(4,2,2),(4,3,2)} 1197/4576
{(1,2,6),(1,3,6),(2,2,6),(2,3,6),(3,2,6),(3,3,6),(4,2,6),(4,3,6)} 951/4576
{(1,2,7),(1,3,7),(2,2,7),(2,3,7),(3,2,7),(3,3,7),(4,2,7),(4,3,7)} 1801/4576
{(1,4,4),(1,5,4),(2,4,4),(2,5,4),(3,4,4),(3,5,4),(4,4,4),(4,5,4)} 340/4576
{(1,5,1),(1,6,1),(2,5,1),(2,6,1),(3,5,1),(3,6,1),(4,5,1),(4,6,1)} 695/4576
{(1,5,2),(1,6,2),(2,5,2),(2,6,2),(3,5,2),(3,6,2),(4,5,2),(4,6,2)} 45/4576
{(1,5,6),(1,6,6),(2,5,6),(2,6,6),(3,5,6),(3,6,6),(4,5,6),(4,6,6)} 511/4576
{(1,6,1),(1,7,1),(2,6,1),(2,7,1),(3,6,1),(3,7,1),(4,6,1),(4,7,1)} 1786/4576
{(1,6,3),(1,7,3),(2,6,3),(2,7,3),(3,6,3),(3,7,3),(4,6,3),(4,7,3)} 685/4576
{(1,6,4),(1,7,4),(2,6,4),(2,7,4),(3,6,4),(3,7,4),(4,6,4),(4,7,4)} 1438/4576
{(1,6,5),(1,7,5),(2,6,5),(2,7,5),(3,6,5),(3,7,5),(4,6,5),(4,7,5)} 1590/4576
{(2,1,1),(2,2,1),(3,1,1),(3,2,1),(4,1,1),(4,2,1),(5,1,1),(5,2,1)} 336/4576
{(2,1,3),(2,2,3),(3,1,3),(3,2,3),(4,1,3),(4,2,3),(5,1,3),(5,2,3)} 721/4576
{(2,1,5),(2,2,5),(3,1,5),(3,2,5),(4,1,5),(4,2,5),(5,1,5),(5,2,5)} 184/4576
{(2,2,5),(2,3,5),(3,2,5),(3,3,5),(4,2,5),(4,3,5),(5,2,5),(5,3,5)} 392/4576
{(2,3,5),(2,4,5),(3,3,5),(3,4,5),(4,3,5),(4,4,5),(5,3,5),(5,4,5)} 772/4576
{(2,4,3),(2,5,3),(3,4,3),(3,5,3),(4,4,3),(4,5,3),(5,4,3),(5,5,3)} 1326/4576
{(2,5,3),(2,6,3),(3,5,3),(3,6,3),(4,5,3),(4,6,3),(5,5,3),(5,6,3)} 492/4576
{(2,6,3),(2,7,3),(3,6,3),(3,7,3),(4,6,3),(4,7,3),(5,6,3),(5,7,3)} 61/4576
{(2,6,7),(2,7,7),(3,6,7),(3,7,7),(4,6,7),(4,7,7),(5,6,7),(5,7,7)} 192/4576
{(3,1,1),(3,2,1),(4,1,1),(4,2,1),(5,1,1),(5,2,1),(6,1,1),(6,2,1)} 756/4576
{(3,1,7),(3,2,7),(4,1,7),(4,2,7),(5,1,7),(5,2,7),(6,1,7),(6,2,7)} 266/4576
{(3,3,1),(3,4,1),(4,3,1),(4,4,1),(5,3,1),(5,4,1),(6,3,1),(6,4,1)} 544/4576
{(3,3,5),(3,4,5),(4,3,5),(4,4,5),(5,3,5),(5,4,5),(6,3,5),(6,4,5)} 516/4576
{(3,4,7),(3,5,7),(4,4,7),(4,5,7),(5,4,7),(5,5,7),(6,4,7),(6,5,7)} 406/4576
{(3,6,1),(3,7,1),(4,6,1),(4,7,1),(5,6,1),(5,7,1),(6,6,1),(6,7,1)} 164/4576
{(4,1,1),(4,2,1),(5,1,1),(5,2,1),(6,1,1),(6,2,1),(7,1,1),(7,2,1)} 460/4576
{(4,1,3),(4,2,3),(5,1,3),(5,2,3),(6,1,3),(6,2,3),(7,1,3),(7,2,3)} 1093/4576
{(4,1,4),(4,2,4),(5,1,4),(5,2,4),(6,1,4),(6,2,4),(7,1,4),(7,2,4)} 1426/4576
{(4,1,5),(4,2,5),(5,1,5),(5,2,5),(6,1,5),(6,2,5),(7,1,5),(7,2,5)} 893/4576
{(4,1,7),(4,2,7),(5,1,7),(5,2,7),(6,1,7),(6,2,7),(7,1,7),(7,2,7)} 1315/4576
{(4,2,1),(4,3,1),(5,2,1),(5,3,1),(6,2,1),(6,3,1),(7,2,1),(7,3,1)} 392/4576
{(4,2,6),(4,3,6),(5,2,6),(5,3,6),(6,2,6),(6,3,6),(7,2,6),(7,3,6)} 893/4576
{(4,2,7),(4,3,7),(5,2,7),(5,3,7),(6,2,7),(6,3,7),(7,2,7),(7,3,7)} 107/4576
{(4,5,1),(4,6,1),(5,5,1),(5,6,1),(6,5,1),(6,6,1),(7,5,1),(7,6,1)} 471/4576
{(4,5,2),(4,6,2),(5,5,2),(5,6,2),(6,5,2),(6,6,2),(7,5,2),(7,6,2)} 929/4576
{(4,5,6),(4,6,6),(5,5,6),(5,6,6),(6,5,6),(6,6,6),(7,5,6),(7,6,6)} 107/4576
{(4,6,1),(4,7,1),(5,6,1),(5,7,1),(6,6,1),(6,7,1),(7,6,1),(7,7,1)} 570/4576
{(4,6,5),(4,7,5),(5,6,5),(5,7,5),(6,6,5),(6,7,5),(7,6,5),(7,7,5)} 601/4576

The following dual variables provide a "coloring" that certifies optimality:

i j k dual 
1 1 2 3/11 
1 1 4 1/11 
1 1 6 3/11 
1 2 1 4/11 
1 2 2 1/11 
1 2 4 2/11 
1 2 5 4/11 
1 2 6 1/11 
1 3 4 4/11 
1 4 2 3/11 
1 4 3 4/11 
1 4 6 3/11 
1 4 7 4/11 
1 5 2 3/11 
1 5 4 1/11 
1 5 6 3/11 
1 6 1 4/11 
1 6 2 1/11 
1 6 4 2/11 
1 6 5 4/11 
1 6 6 1/11 
1 7 4 4/11 
2 1 1 4/11 
2 1 3 1/11 
2 1 4 2/11 
2 1 5 4/11 
2 1 7 1/11 
2 2 3 4/11 
2 2 7 4/11 
2 3 2 4/11 
2 3 3 1/11 
2 3 4 2/11 
2 3 6 4/11 
2 3 7 1/11 
2 4 1 3/11 
2 4 3 1/11 
2 4 5 3/11 
2 4 7 1/11 
2 5 1 4/11 
2 5 3 1/11 
2 5 4 2/11 
2 5 5 4/11 
2 5 7 1/11 
2 6 3 4/11 
2 6 7 4/11 
2 7 2 4/11 
2 7 3 1/11 
2 7 4 2/11 
2 7 6 4/11 
2 7 7 1/11 
3 1 4 4/11 
3 2 2 3/11 
3 2 3 2/11 
3 2 4 2/11 
3 2 6 3/11 
3 2 7 2/11 
3 3 2 3/11 
3 3 4 1/11 
3 3 6 3/11 
3 4 1 4/11 
3 4 2 1/11 
3 4 3 2/11 
3 4 5 4/11 
3 4 6 1/11 
3 4 7 2/11 
3 5 4 4/11 
3 6 2 3/11 
3 6 3 2/11 
3 6 4 2/11 
3 6 6 3/11 
3 6 7 2/11 
3 7 2 3/11 
3 7 4 1/11 
3 7 6 3/11 
4 1 2 4/11 
4 1 3 3/11 
4 1 6 4/11 
4 1 7 3/11 
4 2 1 3/11 
4 2 3 1/11 
4 2 5 3/11 
4 2 7 1/11 
4 3 1 4/11 
4 3 3 3/11 
4 3 5 4/11 
4 3 7 3/11 
4 4 4 4/11 
4 5 2 4/11 
4 5 3 3/11 
4 5 6 4/11 
4 5 7 3/11 
4 6 1 3/11 
4 6 3 1/11 
4 6 5 3/11 
4 6 7 1/11 
4 7 1 4/11 
4 7 3 3/11 
4 7 5 4/11 
4 7 7 3/11 
5 1 2 3/11 
5 1 4 1/11 
5 1 6 3/11 
5 2 1 4/11 
5 2 2 1/11 
5 2 4 2/11 
5 2 5 4/11 
5 2 6 1/11 
5 3 4 4/11 
5 4 2 3/11 
5 4 3 4/11 
5 4 6 3/11 
5 4 7 4/11 
5 5 2 3/11 
5 5 4 1/11 
5 5 6 3/11 
5 6 1 4/11 
5 6 2 1/11 
5 6 4 2/11 
5 6 5 4/11 
5 6 6 1/11 
5 7 4 4/11 
6 1 1 4/11 
6 1 3 1/11 
6 1 4 2/11 
6 1 5 4/11 
6 1 7 1/11 
6 2 3 4/11 
6 2 7 4/11 
6 3 2 4/11 
6 3 3 1/11 
6 3 4 2/11 
6 3 6 4/11 
6 3 7 1/11 
6 4 1 3/11 
6 4 3 1/11 
6 4 5 3/11 
6 4 7 1/11 
6 5 1 4/11 
6 5 3 1/11 
6 5 4 2/11 
6 5 5 4/11 
6 5 7 1/11 
6 6 3 4/11 
6 6 7 4/11 
6 7 2 4/11 
6 7 3 1/11 
6 7 4 2/11 
6 7 6 4/11 
6 7 7 1/11 
7 1 4 4/11 
7 2 2 3/11 
7 2 3 2/11 
7 2 4 2/11 
7 2 6 3/11 
7 2 7 2/11 
7 3 2 3/11 
7 3 4 1/11 
7 3 6 3/11 
7 4 1 4/11 
7 4 2 1/11 
7 4 3 2/11 
7 4 5 4/11 
7 4 6 1/11 
7 4 7 2/11 
7 5 4 4/11 
7 6 2 3/11 
7 6 3 2/11 
7 6 4 2/11 
7 6 6 3/11 
7 6 7 2/11 
7 7 2 3/11 
7 7 4 1/11 
7 7 6 3/11 

For this coloring, every $1\times2\times4$ box has sum of colors equal to $1$, and the sum of colors in the big cube is $41+9/11$, so you cannot pack more than $41+9/11$ disjoint boxes.

$\endgroup$
19
  • 1
    $\begingroup$ The largest possible value of $\sum_b x_b$ subject to the constraints. $\endgroup$
    – RobPratt
    Mar 10 at 3:18
  • 1
    $\begingroup$ Does this mean that each possible 1x2x4 cuboid adds up to at least 1 under the dual "coloring"? $\endgroup$
    – mathlander
    Mar 10 at 3:29
  • 2
    $\begingroup$ @mathlander Imagine you could put things like $\frac3{11}$ of a cuboid in the cube. If, despite this LP relaxation, you still can't pack (part-)cuboids summing to 42 whole cuboids, impossibility is already proven as the whole-cuboid packings are a strict subset of the part-cuboid packings. $\endgroup$ Mar 10 at 3:42
  • 1
    $\begingroup$ And then normal, real-valued linear programs like this are fairly easy to solve. To each such program is a dual, and optimal solutions to the dual correspond to optimal solutions in the primal, with the same objective value for each. $\endgroup$ Mar 10 at 3:43
  • 1
    $\begingroup$ The dual values for the cells in each cuboid add up to exactly $1$. $\endgroup$
    – RobPratt
    Mar 10 at 3:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.