wu :: forums - Print Page


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

        riddles >> hard >> pack the gift
        
(Message started by: inexorable on Feb 15^th, 2007, 3:46am)

Title: pack the gift
Post by inexorable on Feb 15^th, 2007, 3:46am

As a Valentine's Day present, Alice got Bob a set of infinitely many cubes, having side-lengths 1, 1/2, 1/3, ..., one cube of each side. But how to gift-wrap them? Alice knows that the harmonic series diverges, so she cannot stack one on top of another in finite space. But she also knows that the total volume of the cubes is finite, since

1 + 1/(2^3) + 1/(3^3) + ... < integral of (1+ 1/x^3) dx with x limits from 1 to infinity = 1.5

So the total volume is less than 1.5 and it seems as if she could just pack them all into a gift-box of dimensions 1 × 1 × 3/2. At this point she realized that a better idea would be to give Bob the cubes and the gift box and make him do the packing.

Show how to arrange the cubes so that they fit into a 1 × 1 × 3/2 box.

Title: Re: pack the gift
Post by Grimbal on Feb 15^th, 2007, 6:11am

The first cube is easy :)
The second probably also.
But then... :(

Title: Re: pack the gift
Post by towr on Feb 15^th, 2007, 6:16am

Why should they fit?
The volume may correspond, but if I had a sphere with volume 1 I wouldn't eb able to put in an a box with volume 1, even thought he volumes are equal.

Title: Re: pack the gift
Post by inexorable on Feb 15^th, 2007, 6:29am

on 02/15/07 at 06:16:05, towr wrote:

Why should they fit?
The volume may correspond, but if I had a sphere with volume 1 I wouldn't be able to put in an a box with volume 1, even thought he volumes are equal.

True. But one box A does not fit in another box B only if there does not exist any combination of dimensions of A such that they are less than or equal to dimensions of B. and at each step of placing one box in box of 1X1X3/2 and considering the dimensions of remaining space it seems there is space for new box to fit.

Title: Re: pack the gift
Post by Grimbal on Feb 15^th, 2007, 9:53am

OK. How to pack:
[hide]
- Cube n is 1/n on a side.
- Cube 1 fills most of the box.
- The remaining space is 1x1x0.5 that can be split into 2 spaces of 1x0.5x0.5.
- Pack the even cubes 2,4,6,... in the one space by using the same method recursively, but scaled down 1/2 size. With some space left.
- Pack the remaining odd cubes 3,5,7,... in the other space as if they were as large as the even cubes 2,4,6,..., with lots of gaps everywhere.
[/hide]

Title: Re: pack the gift
Post by towr on Feb 15^th, 2007, 10:29am

Not so hard, seeing it like that.. Well done.

I also hadn't noticed the '<'. About 19.9% of the box is left free.