Puzzle

How many cuts are necessary to cut an n x n x n cube into 1 x 1 x 1 cubes? Existing cuboids may be stacked together for cutting. So one cut may go through multiple existing cuboids.

Source

Do not remember.

Solution

For the general a x b x c cuboid, we need f(a) + f(b) + f(c) cuts, where f(y) = ⌈ log y / log 2 ⌉. This can be proved by induction. Note that at any point, the "largest" cuboid requires the most steps; others can be sliced in parallel with this cuboid. When the "largest" cuboid has dimensions a x b x c, there are exactly 3 choices: to slice along one of the three sides. For a lying in the range (2^i, 2^(i+1)], any cut that results in the new "largest cuboid" being z x b x c, where z lies in the range (2^(i-1), 2^i], is optimal. This is because f(z) for all these z's is identical. For example, for 10 x 34 x 98 cuboid, any of the following could be the maximal cuboid for the remaining steps:

5 x 34 x 100

6 x 34 x 100

7 x 34 x 100

8 x 34 x 100

10 x 17 x 100

10 x 18 x 100

10 x 19 x 100

... and so on till

10 x 32 x 100

10 x 34 x 49

10 x 34 x 50

10 x 34 x 51

10 x 34 x 52

.. and so on till

10 x 34 x 64.

© Copyright 2008—2017, Gurmeet Manku.