Separating the Pieces of a Rubiks Cube

Question

I recall coming across this problem in one of my classes senior year of high school. (We only did the first part).

Easy (and probably somewhere on the internet)

Taking a standard 3x3x3 Rubik's Cube, what is the minimum number of cuts needed to separate every piece, from all other pieces? (Into a total of 27 pieces)


Medium (and probably not somewhere on the internet)

Taking a standard 4x4x4 Rubik's Cube, what is the minimum number of cuts needed to separate every piece, from all other pieces? (Into a total of 64 pieces)


Hard

Taking a standard 5x5x5 Rubik's Cube, what is the minimum number of cuts needed to separate every piece, from all other pieces? (Into a total of 125 pieces)

Here are the rules for cutting:

1. Stacking cut pieces on top of each other is fine
2. Cuts must be straight and completely through the cube
3. You can't ruin the pieces in anyway by cutting them at weird angles

Disclaimer: I have guesses as to the answers of the harder version of the puzzles, but have not had my proofs verified

Answer 1

Theorem:

The minimum number of cuts to separate an $a\times b\times c$ block into $1\times 1\times 1$ blocks is $f(a)+f(b)+f(c)$, where $f(n)=\lceil\log_2 n\rceil$.

Proof:

Let the "age" of a block be the quantity $f(a)+f(b)+f(c)$ mentioned above. We first show that cutting a block with age $g$ leaves two blocks, with the "older" of the two having an age of at least $g-1$.

Suppose you cut an $a\times b\times c$ block along the $x$ axis into $a'\times b\times c$ and $a''\times b\times c$ blocks, where $a'\ge a''$. This means $a'\ge a/2$, so $\log_2 a'\ge (\log_2 a) - 1$, so $f(a')\ge f(a)-1$, proving the age of the larger block decreased by at most one.

This provides a lower bound: if the age of the initial block is $g$, then its takes $g$ cuts to make sure that every piece has an age of zero (namely, is a 1x1x1 block).

To attain this lower bound, at any point, line up all the pieces you have so far with a volume of more than 1, and cut them so their longest axis gets cut into as close to half has possible. This will leave a bunch of blocks who are all one year younger than their fathers.

Answer:

Since the ages of a $3$, $4$ and $5$ cube are $6, 6$ and $9$ respectively, these are the required number of cuts.

Answer 2

ANSWER:

For $n\ x\ n\ x\ n$ cube, you need $3\lceil log_2n\rceil$ cuts. (base 2, upper rounding).
This means:
$3x3x3$ - 6 cuts,
$4x4x4$ - 6 cuts,
$5x5x5$ - 9 cuts.

Proof:

If $n$ is a power of two, the way to cut through the pieces is obvious - every time stack the pieces on top of each other and split them in halves.
This shows that for power's of two, $3\lceil log_2(n)\rceil$ cuts are exactly enough.

In order to show that at least $3\lceil log_2n\rceil$ cuts are needed, we notice that after $k$ cuts, there is a piece with dimensions $(x,y,z)$, such that:
$\lceil log_2{\frac{n}{x}}\rceil+\lceil log_2{\frac{n}{y}}\rceil+\lceil log_2{\frac{n}{z}}\rceil \leq k$.

This can be proved easily with induction, using:
$\lceil log_2{\frac{2n}{y}}\rceil \leq1+\lceil log_2{\dfrac{n}{y}}\rceil.$

Since at the end all cubes should have dimensions $1x1x1$, we get:
$3\lceil log_2{n}\rceil \leq k$
and therefore we need at least $3\lceil log_2n\rceil$ cuts.

Answer 3

For the 3x3:

1. Make 2 cuts on each of the following 3 faces: Front, Left, Top. This leaves you with 27 cubes. You're done!

Total cuts = 6

---

For the 4x4:

1. Cut down the center of the top, left, and front faces. This leaves you with 8 2x2 cubes.
   Cuts used: 3

2. Stack the 8 2x2 cubes on top of each other and make 2 cuts on the top face. This leaves you with 32 1x2 pieces.
   Cuts used: 3 + 2 = 5

3. Arrange the 32 1x2 pieces in a line so that they can all be cut down the their center line with 1 cut. This leaves you with 64 small cubes. You're done!
   Cuts used: 3 + 2 + 1 = 6

Total cuts = 6

---

For the 5x5:

1. WIP