Exponents

Problem:

A 4x4x4 cube can be cut into unit cubes using 10 cuts. Can this be done in fewer cuts?


Note:

PIXIO makes magnetic cubes you can purchase. I wonder if these would be a fun way to explore the problem. I imagine you could make cuts using index cards, or something similar, by sliding the card between the magnets. I wonder if any other companies offer such a product. Ideally, the magnet should be just strong enough to hold the cuboid together, but weak enough to slice the cuboid without much force.


Solution:

A 4x4x4 cube can be divided into 64 unit cubes in 6 cuts. First, make 3 cuts to obtain 8 2x2x2 cubes. Stack them into a 2x2x16 block. Make 2 cuts to obtain 32 1x1x2 blocks. Stack them into a 1x32x2 block. Make 1 cut to obtain 64 unit cubes. Here's another solution, expressed more succinctly:

 1 4x4x4
 2 2x4x4
 4 1x4x4
 8 1x2x4
16 1x1x4
32 1x1x2
64 1x1x1

No solution has fewer than 6 cuts. Each cut, at best, doubles the number of pieces. But \(2^6 = 64,\) and thus, the fewest number of cuts must be 6.


Going further:

In our first solution, we made 6 cuts, but only 2 rearrangements. Is that the minimum possible? How many cuts would we need for an axbxc cuboid, to make a * b * c unit cubes? What is the minimum number of rearrangements?


What I know so far:

The last cut you make will cut some number of 1x1x2 blocks in half.

If we were to cut the axbxc cuboid into a * b * c unit cubes, without rearranging, it would take (a - 1) + (b - 1) + (c - 1) = a + b + c - 3 cuts. Thus, this is an upper bound on the minimum number of cuts required.

A 2x2x2 cube can be cut into unit cubes using a minimum of 3 cuts, and 0 rearrangements.

A 3x3x3 cube can be cut into unit cubes using a minimum of 6 cuts, and 0 rearrangements. We know 6 cuts are necessary because we have to free the center unit cube, which has 6 faces.

A 4x4x4 cube can be cut into unit cubes using 6 cuts, and 2 rearrangements. First, make 3 cuts to obtain 8 2x2x2 cubes. Stack them into a 2x2x16 block. Make 2 cuts to obtain 32 1x1x2 blocks. Stack them into a 1x32x2 block. Make 1 cut to obtain 64 unit cubes.

The last cut you make will cut some number of 1x1x2 blocks in half.

Every time a cut is made, each non-unit cuboid is broken into two smaller cuboids. Thus, if m and n are the minimum number of cuts for the first and second smaller cuboids respectively, for the initial cut, then max(m, n) + 1 is the minimum number of cuts for the entire cuboid. Let [axbxc] denote the minimum number of cuts for an axbxc cuboid. Also, for brevity, let [axbxc] @ [dxexf] = max([axbxc], [dxexf]) + 1. Then

[1x1x1] = 0
[1x1x2] = [1x1x1] @ [1x1x1] = 1
[1x1x3] = [1x1x1] @ [1x1x2] = 2
[1x1x4] = [1x1x2] @ [1x1x2] = 2
[1x1x5] = [1x1x3] @ [1x1x2] = 3
[1x1x6] = [1x1x3] @ [1x1x3] = 3
[1x1x7] = [1x1x4] @ [1x1x3] = 3
[1x1x8] = [1x1x4] @ [1x1x4] = 3
[1x1x9] = [1x1x5] @ [1x1x4] = 4
...

At this point, the pattern for [1x1xn] should be clear.


Sources:

Cubist Cuts by NRICH: The first part of this challenge also appears in Mathematics, A Human Endeavor by Harold R. Jacobs, on page 31. One of their diagrams is helpful, and doesn't appear on the NRICH page.