8
$\begingroup$

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

$\endgroup$
  • $\begingroup$ You don't need to make any cuts; just project the Rubik's Cube onto the floor multiple times (Proven by scientific experiment, the minimum amount of times you need to do this is about thrice). $\endgroup$ – Conor O'Brien Jul 16 '15 at 22:09
  • 1
    $\begingroup$ What is in the interior of these Rubik's cubes? More cubes? $\endgroup$ – Tyler Seacrest Jul 16 '15 at 22:35
  • $\begingroup$ @TylerSeacrest is that a real question? If it is please rephrase it, I'm not sure what you mean $\endgroup$ – qwertylpc Jul 16 '15 at 22:52
  • $\begingroup$ @TylerSeacrest, the problem states the pieces (27 pieces, 64 pieces, and 125 pieces), so yes. $\endgroup$ – itriedacrab Jul 16 '15 at 23:02
  • $\begingroup$ @qwertylpc: Thanks for adding the number of pieces, that clears it up. Nice problem! $\endgroup$ – Tyler Seacrest Jul 17 '15 at 2:56
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Does the xyz refer to the pre or post cut location? $\endgroup$ – qwertylpc Jul 17 '15 at 16:23
  • $\begingroup$ (x,y,z) corresonds to the post-cut dimensions of the block we consider. After the 0th cut, we have 0+0+0=0. After the 1st cut, we have 0+0+1=1 and so on. $\endgroup$ – Puzzle Prime Jul 17 '15 at 16:43
  • $\begingroup$ Still isn't clear to me $\endgroup$ – qwertylpc Jul 17 '15 at 16:44
  • $\begingroup$ Sorry, it is really a little bit vague. After 0 cuts (in the beginning) you have 1 piece which has dimensions (x,y,z)=(n,n,n) and then [log(n/x)]+[log(n/y)]+[log(n/z)]=0, which is fine. After the 1st cut you have 1 piece, which has dimensions (x,y) =(n,n) and third dimension z which is at least n/2. Then you get [log(n/n)]+[log(n/n)]+[log(n/z)]<=0+0+1=1, which is again fine. Continuing like this, you see that you will always have after the k-th cut a piece with dimensions (x,y,z) for which [log(n/x)]+[log(n/y)]+[log(n/z)]<=k. At the end all pieces have dimensions (1,1,1), so the claim follows. $\endgroup$ – Puzzle Prime Jul 17 '15 at 16:49
0
$\begingroup$

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
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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