March 17 Information

I drew this graphic to show how 6³ can be decomposed into 3³ + 4³ + 5³, and needed 3 + 9 + 1 = 13 cuboids. Is there a decomposition using fewer?

Thanks,
cmɢʟee⎆ τaʟκ 09:56, 17 March 2018 (UTC) reply

I tried this and 13 seems to be respectable at least. I'm guessing some kind of computer search will be necessary to completely solve the problem, i.e. find a solution with k pieces and prove that k is minimal. There is an obvious proof that at least 8 pieces are needed, but other than that I didn't make any progress. Not sure how many other people tried this on your previous post, but usually people don't usually answer unless they have a solution, or at least progress. It would be interesting to see if dropping the cuboid restriction makes the problem and easier. -- RDBury ( talk) 11:18, 17 March 2018 (UTC) reply

The problem is really nice, but I saw nothing worth sharing the first time around. If you admit the 5^3 is made out of a single piece, you can convince yourself by hand that 13 is unbeatable (if neither of the 3^3 and 4^3 contains a full square, then you need at least 6 pieces for each which means at least 13 bits in total; and if you place a 3*3 or a 4*4 square in the 6^3 cut, it constrains enough the rest of the cut), but I am not sure that I really saw all the branches, and there is no reason to assume the 5^3 is from a single piece.

This time, I made a bit of attempt for thinking about a computer solution, but I am rather pessimistic. Even leaving aside the fact that implementation is going to be a royal pain in the backside, I am not sure anything can run in reasonable time/space complexity. My best attempt would be centered on the following pseudocode, giving a recursive function to compute the ways to cut an arbitrary shape into a certain number of cuboids

def partition_shape_into_cuboids(shape, max_number_of_cuts)
  if max_number_of_cuts == 1
    if shape is a cuboid
      return {shape}
    else
      return {}  # no solution
  else
    for shape1, shape2 a partition of shape into two connex parts
      cut_1 = partition_shape_into_cuboids(shape1, floor(max_number_of_cuts/2))
      cut_2 = partition_shape_into_cuboids(shape2, ceil(max_number_of_cuts/2))
    return cartesian product cut_1 * cut_2  # cartesian product example: {a, b, c} * {x, y} -> {ax, bx, cx, ay, by, cy}

The OP's question can be solved by first computing partition_shape_into_cuboids(cube X*X*X, N) for X=3,4,5 and all N≤8 (it sounds fairly obvious that the two cubes with the smallest amount of fragments in the cut will take at least 4 fragments together, so the remaining cube needs to be less than 8 fragments if we want to beat the 13-fragment solution). This in turn requires to precompute all the subshapes that can fit within a 5*5*5 with a budget up to 4, using dynamic programming / memoization to store the small subproblems. Once that is done, we want to loop on the partitions of the 6*6*6 cube into three fragments of volume 3^3, 4^3 and 5^3, for each fragment see if it has a solution for budget ≤8 using one of the sets of the precomputed small budget. Obviously a smart implementation will try the smallest cube first (if the fragment that is supposed to rearrange into the 3^3 fails, no point in computing the others) and use memoization as well.

We divide and conquer our way into the budget from a relatively small value, so the recursion depth will be fairly limited. However the real question is how many ways there are to partition in the "splitting into fragments" steps; I have a feeling that while in the second step the volume constraint will help us, in the first step the answer is "a lot" (i.e. something exponential with the volume) which would make it intractable, but maybe looping on connex fragments is actually way much less than the obvious bound (2^volume).

Notice also that there is very little "geometry" input in the above, so maybe even a mathematically-simple observation might improve tremendously the viability of the computer solution. Tigraan ^{Click here to contact me} 00:46, 18 March 2018 (UTC) reply

Thank you very much, everyone. Indeed, I tried again and couldn't find anything better. For the graphic, this is also keeps the 5³ in one piece, so the rest form a shell on one side around it, making it easier to see. Thanks again for your efforts, cmɢʟee⎆ τaʟκ 00:06, 19 March 2018 (UTC) reply