cutting the cube

Hi everyone,I got this puzzle and but I cannot solve it,can anyone please help me?

For a $3\times 3$ cube, it requires 6 cuts to cut it into 27 cubes.
Can the number of cuts be reduced if the cube can be piled together after each cut?
If it can be done, then find the solution for a $4\times 4$ cube and then give the general formula for a $n\times n$ cube.

Please help me,I found it is really not easy to visualising the situation.

I think I have got for $4\times 4\times 4$ cube,which is 6 times as well,in simple words,each direction requires two cuts.

However,I cannot generalise $n\times n\times n$ ,it is a bit hard to find the partern,I think it has something to do with $2^n$ ,but I cannot derive a general formula.

Can anyone help me please? Any solution for the generalised formular? Thanks a lot.

I think we can get an upper bound for the minimum number of cuts with piling allowed.

Let n = 2^r * k

where k is odd. Claim: Minimum number of cuts is at most (r + k - 1)^3.

Explanation for n=6. Suppose the cube is oriented with one corner at the origin and the opposite corner at (6,6,6). Make the cut along the plane x=3. Then take one piece and stack it on top of the other, and make two cuts at x=1 and x=2. Then reassemble into the original cube position and repeat for the other two dimensions.

For n=12 we would cut in half and pile twice before cutting in thirds.

This can't be the minimum though, because consider n=5. Cube oriented with corner at (0,0,0) and corner at (5,5,5). Cut along x=2. Then take the piece that's farther from the origin and pile it on top of the other piece flush with the yz-plane with a part hanging over the edge. Then make a cut at x=1. Then make the final cut for that direction. Thus we can cut up n=5 in at most 3^3 slices.

For n=7 we can cut at x=3 and x=6, then pile the two same-size pieces and cut twice.

I think this gives us an algorithm for a new upper bound. Set variable c initially at 0. Let n_0 = n. If n_0 is even, add one to c. Else, add 2 to c. Let n_1 = floor(n_0 / 2). If n_1 is 1, stop. Else, continue the same process. (And so on.) Then we have upper bound c^3.

This *might* be the sequence for c-values: http://www.research.att.com/~njas/sequences/A003313

But I suspect it's not the same sequence since it seems we have a simple recurrence

c(1) = 0
if 1 < n odd: c(n) = 2 + c((n-1)/2)
if 1 < n even: c(n) = 1 + c(n/2)

and this is not mentioned on OEIS. I thought the OEIS sequence worth mentioning because possibly my algorithm is suboptimal and OEIS's sequence is an optimal version; not sure without doing further testing. ("minimal number of multiplications required to compute n-th power" sounds like it could very well be an equivalent problem.)

I think in order to do better than this we would have to consider rotating pieces, and I can't think of how this might be done. Possibly this bound is the final answer.

Hello, tsang!

The first part is a classic puzzle.

Quote:

$\text{For a }3\times 3 \times 3\text{ cube, it requires 6 cuts to cut it into 27 unit cubes.}$

$\text{Can the number of cuts be reduced if the pieces}$
. . $\text{can be piled together after each cut?}$

The answer is no.

Explanation:

. . Consider the unit cube in the very center of the large cube.

. . It requires a minmum of 6 cuts to cut it free.

My answer is...

Quote:

Originally Posted by tsang

Hi everyone,I got this puzzle and but I cannot solve it,can anyone please help me?

For a $3\times 3$ cube, it requires 6 cuts to cut it into 27 cubes.
Can the number of cuts be reduced if the cube can be piled together after each cut?
If it can be done, then find the solution for a $4\times 4$ cube and then give the general formula for a $n\times n$ cube.

Please help me,I found it is really not easy to visualising the situation.

Hi, this is my first post on the forum and it is going to be a bit long!

First, the number of cuts for a 3X3X3 cube cannot be less than six cuts. You shall understand why by the end of this post.

However, the number of cuts for any cube of size k x k x k can be reduced if the pieces are piled together. For a 4X4X4 cube, only six cuts would be required. I shall now try and give a clear explanation as to how I solved it. And before I continue, from now on I am going to express a cube simply as '333' instead of '3X3X3' as it's much easier to type it that way. Also, each unit element, i.e. a 111 cube shall be called a minicube for convenience!

So, let's first experimentally cut a 333 cube. This is how I would do it to minimize the number of cuts. Each line represents a new cut and the corresponding sizes of pieces. Also, for clarity, once we obtain the smallest possible piece of 111, I shall not carry it over to the next line.

Given: 333
Cut 1: 332 331
Cut 2: 331 331 321 311
Cut 3: 321 311 321 311 311 311 211 111
Cut 4: 311 311 211 111 311 311 211 111 211 111 111 111 111
Cut 5: 211 111 211 111 111 111 211 111 211 111 111 111 111 111 111 111
Cut 6: 111 111 111 111 111 111 111 111

Basically in cut 1, a 3X3X3 cube is cut into two pieces, one of dimensions 3X3X2 and another 3X3X1. Then in cut 2, 3X3X2 was cut into two pieces each of 3X3X1. But 3X3X1 was also cut into 3X2X1 and 3X1X1. Physically, this is how it would be; think of a bar of tofu of size 333. You cut of a slice of tofu of size 331, turn it 90 degrees and put it on top of the remaining part of size 332 and then cut through both pieces together. Totally, if you count the '111's above, you should get 3X3X3 = 27 of them.

Of course, in different cube sizes etc, you may or may not have to turn the pieces through 90 degrees... (don't ponder about this point, it's a bit trivial actually for the time being).

Now, I shall explain the logic behind why I cut it like this, but not before showing a 4X4X4 cube which has an even number of cubes, which will help in my explanation.

Given: 444
Cut 1: 442 442
Cut 2: 441 441 441 441
Cut 3: 421 421 421 421 421 421 421 421
Cut 4: 411 411 411 411 411 411 411 411 411 411 411 411 411 411 411 411
Cut 5: 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211
Cut 6: 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111

Total 111's = 4X4X4 = 64

So, how did we do this? First of all, what is the goal? So let's start with each minicube.

Number of sides or faces a minicube has = 6
For a k x k x k cube, exposed surface area of the whole cube is = 6 x (k^2)
Total number of parts in a k x k x k cube = k x k x k
Surface area of all the individual parts put together is = 6 x (k^3)
Therefore, hidden surface area = 6 x (k^3) - 6 x (k^2)

Now, this equation is not of much importance further in the proof. But it shows that there is a hidden surface area that cannot be seen.

These minicubes are touching each other on their 'faces'. Some are touching others on all six faces while the outer corner most ones touch only on 3 faces. Many of these faces, are next to each other and form plains. For example, in a 3x3x2 part, there is a plain of a surface area of 9 square units, between the two 3x3x1 parts. Now, to minimize the total number of cuts, I need to ensure that I cut through the cube(s) such that I maximize the number of faces in each cut, so I should cut along large plains. For example, in a 3x3x2 part, the largest plain is a 3x3 plain. So, I should cut along this plain, not along the 3x2 plain.
Hence, for each cut I make, I should stack my parts in such a way that I cut through the biggest plains in each part!

So going back to our 333 example, the first cut became 332 and 331. The biggest plain in 332 is a 3x3 plain and the biggest plain in a 331 is a 3x1 plain. Therefore the 331 part which is basically a plate of 3x3 minicubes (unit thickness) shall be turned 90 degrees, then kept on top of 332 SUCH THAT, plain 3x1 in 331 is aligned with plain 3x3 in 332. Then, we shall make a SINGLE cut through both plains together!!

There is a second condition to minimizing the number of cuts. Always try and cut towards the center of the part. For example. Take 444. There are two ways we could have cut this in the first cut:

442 442 (which is what we did)
441 443 (which I recommend against)

Why? Now the biggest plain in each of the 442's is 4x4. Therefore, in the next cut we shall cut through two areas of 4x4 each in one stroke. Therefore total area cut through in cut 2 would be = 4x4 + 4x4 = 32 sq units.
But in case 2, the largest area in 443 is 4x4 while in 441 is ONLY 4x1. Therefore, total area in cut 2 would be = 4x4 + 4x1 = 20 sq units ONLY!!!

So what are we trying to do, you give me a cube. I am trying to cut it into as many equal sizes such that I finally get the individual minicubes. So a 444, becomes 442 etc till it reaches 111. But in a k x k x k cube where 'k' is odd, obviously I can't make equal parts, i.e. a 333 can only become 3x3x2 and 3x3x1 and NOT 3x3x1.5 and 3x3x1.5. Correct?

Furthermore, in a cube, for example 444, I want to reduce each DIMENSION by dividing it. How many times do I want to divide it? Till I get a unit dimension, which is the dimension of a minicube. So, I want, 444 to become 442 then 441. So how many cuts did that take for one dimension to become from 4 to 1? 2 cuts. Hence, we need to keep cutting till each dimension gets reduced to a unit dimension. So if each dimension takes 2 cuts, how many will 3 dimensions take? Obviously: 3x2 = 6 cuts!!!

Similarly, let's 'cut' the number 5 till it reduces to 1:

Given: 5
Cut 1: 3 2
Cut 2: 2 1 1 1
Cut 3: 1 1 1 1 1

So how many cuts did it take for 5 to reduce to 5 unit dimensions? 3 cuts. So for 3 dimensions? 9 cuts. Which is the minimum number of cuts required to reduce a 555 cube by cutting it while stacking the parts, to produce 125 minicubes. Try it, it works.

Now see the 444 example again below:

Given: 444
Cut 1: 442 442
Cut 2: 441 441 441 441
Cut 3: 421 421 421 421 421 421 421 421
Cut 4: 411 411 411 411 411 411 411 411 411 411 411 411 411 411 411 411
Cut 5: 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211
Cut 6: 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111

Total 111's = 4X4X4 = 64

444 takes 2 cuts for the right-most dimension to reduce to 1. Then 2 more for the middle dimension to reduce to 1. And 2 more for the left-most. Totally 6. And the fact that it works is proven by the individual parts shown above.

Now, if we agree on the logic, we need to create a generalized equation for a k x k x k cube like you asked.

Now look at the numbers below. The first row is the 'k' dimension of the cube. The second row, is the number of cuts required for EACH dimension:

k : 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
Cuts: 1 2 2 3 3 3 3 4 4 4 4 4 4 4 4 5

Realized a trend?

No. of times 3 cuts required = 1 = 2^0
No. of times 6 cuts required = 2 = 2^1
No. of times 9 cuts required = 4 = 2^2
No. of times 12 cuts required = 8 = 2^3

The geometric series is,

$2^0, 2^1, 2^2, 2^3 ...$

where r, the multiplier is '2' obviously.

And of course, I am assuming the trend continues!

So for geometric series for n variables, the sum of the series is:

$= (1 - r^n)/(1 - r) = Y$ (Y some variable...)

where r = 2 and n is the sum till the nth variable.

Rearranging the equation:

$r^n = 1 - Y*(1-r)$

Take log on both sides:

$n*log(r) = log(1 - Y*(1-r))$

OR

$n = (log(1 - Y*(1-r)))/(log(r))$

which is basically log(1 - Y*(1-r)) to the base of r (but I don't know how to make the 2 come in the 'base' position next to log on a computer!).

Now why do I want n and what is Y?

Now let Y = k -1, where k is nothing but the dimension of our cube! I shall explain why soon.

$n = (log(1 - (k-1)*(1-r)))/(log(r))$

or

$n = (log(1 - (k-1)*(-1)))/(log(2))$
$n = (log(k))/(log(2))$

Now what is our range of values for k? 2, 3, 4, 5....

So Y = (k-1), represents the position of each element, which is 1,2,3,4.....

Again:

k: 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
Cuts: 1 2 2 3 3 3 3 4 4 4 4 4 4 4 4 5
(k-1):1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

So if the sum of the geometric series (1 - 2^n)/(1 - 2) = (k-1) = 7, for example, then what is 'n' giving me? 'n' gives me the cuts per dimension, i.e. 3!! BUT!!! n will go into decimal points for most points. So for that we need to enclose our cut equation in a roundup function. For example for k = 7, (k-1) = 6. Without round up we will get n as 2.81. So we round it up to the next highest integer of 3, which is what is required. Therefore:

$Cut per dimension = roundup(n) = roundup[(log(k))/(log(2))]$

Sidenote: Sorry but I don't know how to put roundup brackets in here around the function so I just wrote roundup!

THEREFORE, total number of cuts required per cube is simply:

$CUTS = 3*roundup[(log(k))/(log(2))]$

Check it out, you will get the following result:
Cuts: 3 6 6 9 9 9 9 12 12 12 12 12 12 12 12 15

Sidenote: Some might have questions over my logic of multiplying the number of cuts per 3. This doubt might be because in odd number cases like in 333, the middle dimension starts changing 'before' the right-most dimension, unlike in the 444 example where the middle dimension starts changin after the right-most dimension reaches a value of '1'. So look at 333 below again:

Given: 333
Cut 1: 332 331
Cut 2: 331 331 321 311
Cut 3: 321 311 321 311 311 311 211 111
Cut 4: 311 311 211 111 311 311 211 111 211 111 111 111 111
Cut 5: 211 111 211 111 111 111 211 111 211 111 111 111 111 111 111 111
Cut 6: 111 111 111 111 111 111 111 111

Notice that the middle dimension starts changing for some cubes, but does not complete till another two cuts. The test; make a 555 yourself. It works. It takes 9 cuts.

I hope you my solution is useful for you and I hope to see others cross-checking this as feedback would be great. And after that extremely long post, I'm tired! I can't remember the last time I made just a long post on a forum.

I think that this thread might make a suitable paper for the MHFJournal, all that is needed is a volunteer to pull everything together.

CB