wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> easy >> Perfect Cubes
        
(Message started by: Whiskey Tango Foxtrot on Jun 6^th, 2006, 12:11pm)

Title: Perfect Cubes
Post by Whiskey Tango Foxtrot on Jun 6^th, 2006, 12:11pm

Given a perfect cube and the ability to cut a perfectly straight line, it would take 3 cuts to make 8 perfect cubes, each of exactly the same size.

How many cuts would it take to make 27 cubes?

How many to make 64 cubes?

How many to make n cubes?

Title: Re: Perfect Cubes
Post by JohanC on Jun 6^th, 2006, 1:49pm

It depends whether or not [hide]you are allowed to rearrange the pieces before each subsequent cut[/hide].

Title: Re: Perfect Cubes
Post by rmsgrey on Jun 6^th, 2006, 2:30pm

I'd want to be able to make a perfect plane cut - cutting along a line would offer no guarantees about the other end of the knife.

For making 27 cubes, [hide]it requires at least 6 cuts since the central cube needs to be cut on each face, and each cut can expose at most one face of the central cube[/hide]

For 64, JohanC's point is significant [hide]with rearrangement, you can get it down to 6 cuts - bisect and then stack the two pieces and bisect parallel to the largest faces. Restore to the original arrangement and repeat for the other directions. Without rearrangement, you obviously need 3 in each direction to form the 4*4*4 array[/hide]

For larger cube numbers, k³, I have partial results: [hide]without rearrangement, you need 3(k-1) cuts. With rearrangement, it looks like 3(ceiling(log₂k)), but I don't have a full proof[/hide]

Title: Re: Perfect Cubes
Post by Whiskey Tango Foxtrot on Jun 18^th, 2006, 3:24pm

Yes, I was more interested in the case where the cubes can be moved. If they can't, this becomes very simple.

I have yet to prove the answer as well, by the way. I thought this up one morning and was interested if anyone had any techniques for finding a solution. My efforts have been fruitless thus far.

This might be too difficult for the easy section, though. If so, my mistake administrators.

Title: Re: Perfect Cubes
Post by Grimbal on Jun 19^th, 2006, 7:17am

It is not that difficult.

[hide]Just consider the size of the largest remaining piece so far. The best you can do in a cut is to divide one dimension by 2, rounded up. This gives a minimum number of cuts of [log2(size x)] + [log2(size y)] + [log2(size z)], where [] is rounding up. And that number can be reached with the simple method of halving and stacking.

PS: the above is actually how to cut a block of a given size into unit cubes. For the problem at hand, the unit size would be 1/k of the size of the original cube, where k³=n, making the number of cuts 3·ceiling(log2(k)).
[/hide]

Title: Re: Perfect Cubes
Post by Whiskey Tango Foxtrot on Jun 19^th, 2006, 2:23pm

Thanks guys. That was banging around in my head for a while.