wu :: forums - Print Page


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

        riddles >> hard >> Filling a Box With Cubes
        
(Message started by: william wu on Aug 23^rd, 2003, 2:14am)

Title: Filling a Box With Cubes
Post by william wu on Aug 23^rd, 2003, 2:14am

Call a set of cubes incongruent if they all have different side lengths. Prove that it is impossible to exactly fill a rectangular box with incongruent cubes.

Note: The phrase "exactly fill" means that there is no space in the box which is not occupied by a cube, and that the cubes themselves should be packed together to form the shape of the rectangular box that envelops them.

Title: Re: Filling a Box With Cubes
Post by tohuvabohu on Aug 23^rd, 2003, 6:00am

Unless my reasoning is bogus, I don't think this one belongs in Hard. [hide]Lay down your first layer of boxes so that they completely fill a rectangle on the floor. Somewhere in there you must have a smallest box, on top of which you have formed a well with walls on all four sides. Even if the walls are only a fraction of an inch higher than that smallest box, you'll have to fill that well with a layer of boxes of all different sizes. But that layer will also have a smallest box. Eventually you'll be trying to fill a well with infinitesimal sized boxes, but since they have no height, they'll never fill the well.[/hide]

Title: Re: Filling a Box With Cubes
Post by Lightboxes on Aug 23^rd, 2003, 6:40pm

Beautiful explanation...I finally understood a problem that may have had some funcion or calculus or probability expressions but did not.

Title: Re: Filling a Box With Cubes
Post by James Fingas on Aug 25^th, 2003, 9:39am

I'm not completely convinced. If the first layer you put down in the well raises its height above the height of the surrounding walls, then you don't have a confined well any more.

Title: Re: Filling a Box With Cubes
Post by tohuvabohu on Aug 25^th, 2003, 11:48am

I realized after I posted that my answer was not complete. But it only fails when the first layer of boxes on the first layer of boxes has its smallest cube somewhere along one edge, and nowhere in the interior is a small box surrounded by 4 larger boxes. In a real life situation with actual boxes that is virtually impossible, given the great difficulty of filling a perfect square with squares. And if the smallest box is along one edge, it’s still constrained on 3 sides, requiring a smaller layer of boxes just the same. I don’t believe the open 4th side will prevent the creation of smaller wells constrained on 3 or 4 sides ad infinitum (the very first row of boxes you set in the back will already create a 3 or 4 sided constrained area). If it’s at a corner, it’s only constrained on 2 sides, but only one of those two sides could be flush with the surrounding boxes from the original layer; so if you use a box larger than the corner box, you create a smaller constrained area beneath it.
On the other hand, if we move into the realm of fractal boxes, then all bets are off. Take a box that is 1.618 times as long as it is high or wide. One cube on the floor will leave a rectangle that is the same golden ratio of width to length. You could keep filling in one side of the rectangle down to infinity (Of course, it would never be filled, unless .99999...=1). The problem disproving the fractal situation is that, not only do you not create any interior constrained areas, not only do you not have any single smallest box in the first layer on which to build your second layer but you might even be able to create fractally smooth surfaces at a 45 degree angle, so all the boxes don’t even have to lie flat. And measuring these infinitely small boxes to prove they’re all different sizes could be a challenge even with an electron microscope.
And if we're permitted infinitely small boxes, then you can certainly approach a full load, because any open space that exists anywhere in your box, there is some box smaller than that space which hasn't been used yet that can partially fill it in. If .999...=1 then with an infinite number of boxes you will have succeeded.

Title: Re: Filling a Box With Cubes
Post by Grant Fikes on Nov 6^th, 2003, 11:25am

We can't have the smallest box in a rectangle or square at an edge, because then we couldn't surround it with larger boxes. [smiley=bfcq.gif] [smiley=bfce.gif] [smiley=bfcd.gif]

Title: Re: Filling a Box With Cubes
Post by Icarus on Nov 11^th, 2003, 6:55pm

That solves the finite case. Tohuvabohu's argument for the case of an infinite number of boxes (the problem statement does not disallow it) falls short let of proving that it is possible to completely fill the box.

In particular, it shows that if the boxes are added sequentially, you can get an increasing infinite sequences of filled volumes. But it does not show that the sequence converges to the volume of the box.

Title: Re: Filling a Box With Cubes
Post by visitor on Nov 12^th, 2003, 6:32am

Suppose the original box is 1 by 1 by 1.999999. In it you place one 1x1x1 box and one .999999x.999999x.999999 box. Now you have to fill the top and one side of the short box. Do it as completely as possible with boxes ranging in size from .000001 and .00000999999. (There was no stated requirement about "how" different the boxes sizes must be). Repeat, treating each box separately to fill in approximately 99.9999% of the remaining space on the top and 2 sides. You'll never run out of boxes that can fill up the same high percentage of open space unless you run out of irrational numbers. And every space will converge toward full as you repeat an infinite number of times.

Title: Re: Filling a Box With Cubes
Post by Icarus on Nov 12^th, 2003, 6:12pm

That's better! Now you have a complete proof that the theorem fails if an infinite number of boxes are used. Even if it required two of your many personalities! ;)

Title: Re: Filling a Box With Cubes
Post by Alfihar on Sep 21^st, 2004, 9:42am

Hola,

this may not be that important, but it bugs me a lil.. shouldn't the problem require non-cubie rectangular boxes?
an 1x1x1 box is rectangular and i can fill it with a single cube of 1x1x1 and the set of that single cube should be incongruent still.

apart from that i don't see how this should not be possible with an infinite number of cubes. like visitor's reasoning shows, it should be possible.

Title: Re: Filling a Box With Cubes
Post by Alfihar on Sep 21^st, 2004, 9:47am

Ooohh.. i misinterpreted Icarus' response.. "theorem fails", aye.. i thought the approach to do it fails, nvm me. =P

Title: Re: Filling a Box With Cubes
Post by rmsgrey on Sep 22^nd, 2004, 6:39am

Since this has been resurrected, I thought I'd fill in a small corner case - with a finite number of non-congruent squares filling a larger rectangle, you can't have the unique smallest square on an edge.
If you do, then either an edge of the parent rectangle or a larger square must be on either side of it so the edge of the small square opposite the parent edge is a line, bounded on both ends by larger squares, so it must be covered by smaller squares (can't be the same size since each square is unique). Therefore, the smallest square in a packing must be in the interior.

Title: Re: Filling a Box With Cubes
Post by John_Gaughan on Sep 22^nd, 2004, 7:50am

If the smallest must be in the interior, then what about the second smallest? By the same reasoning, it cannot be on the exterior. Using induction, would it be possible to prove this impossible using your reasoning?

Title: Re: Filling a Box With Cubes
Post by rmsgrey on Sep 22^nd, 2004, 9:22am

Yes, the second smallest must also be in the interior, but the reasoning fails for the third smallest, whose far edge can be covered by the two smaller squares, whose far edges can be continuous with the edges of the neighbours of the third smallest.

Title: Re: Filling a Box With Cubes
Post by Deedlit on Apr 3^rd, 2005, 10:24pm

Just saw this old thread - it seems to me that the problem depends on how you define "filling the box." I can think of three definitions:

1. The union of the cubes is the entire box.
2. The total volume of all the cubes is equal to the volume of the box.
3. Every point is either in a box or is approached by some sequences of boxes. ( or the closure of the union is the entire box)

We have 1 => 2 => 3, but neither of the reverse implications holds.

Proving the claim using 2 or 3 is not hard, but I don't think either tohuvabohu's answer or vistor's answer suffices. Continually adding volume doesn't necessarily take you to the volume of the box; and visitor's answer is too vague.

I have a feeling definition 1 is false, but I'm not sure. Any ideas?

Title: Re: Filling a Box With Cubes
Post by Barukh on Apr 4^th, 2005, 5:55am

on 04/03/05 at 22:24:49, Deedlit wrote:

I have a feeling definition 1 is false, but I'm not sure. Any ideas?

How can a definition be false?

Title: Re: Filling a Box With Cubes
Post by Deedlit on Apr 4^th, 2005, 6:48am

Oops. :-[ I meant the the claim that the box could be filled by cubes would be false using definition 1, of course.

Title: Re: Filling a Box With Cubes
Post by Icarus on Apr 4^th, 2005, 6:36pm

(1) just about has to be false for any possible filling of the cube. It should be possible to construct a sequence of nested closed sets each of which lies in the unfilled portion of the box at each step. The intersection of sequence has to contain at least one point, which cannot be a part of any of the small boxes.

However, you are wrong about this

on 04/03/05 at 22:24:49, Deedlit wrote:

We have 1 => 2 => 3, but neither of the reverse implications holds.

1 => 2 <=> 3 is how these statements are related.

To see that 3 => 2, let A be a measurable set and A^c be the closure of A, then m(A^c) = m(A) (for any topological measure, such as volume).

Let A be the union of all the cubes, and assume (3). Then the total volume of the cubes, m(A), is equal to m(A^c), which is the volume of the box.

Title: Re: Filling a Box With Cubes
Post by Deedlit on Apr 4^th, 2005, 10:54pm

on 04/04/05 at 18:36:00, Icarus wrote:

I was thinking along these lines; the trouble is, how do you pick a closed subset of the remainder that you know won't get filled up? The choice must be based on the collection of cubes somehow. Perhaps a Zorn's Lemma argument would work here.

Quote:

However, you are wrong about this

1 => 2 <=> 3 is how these statements are related.

To see that 3 => 2, let A be a measurable set and A^c be the closure of A, then m(A^c) = m(A) (for any topological measure, such as volume).

Not true in general. Take, for instance, a generalized Cantor set in [0,1] that is nowhere dense and has positive measure. Then [0,1] minus the set will have measure less than 1, but the closure will be the whole interval. The example I was thinking for this problem: Take an enumeration of the rational points in the box, and, if the ith point is not already covered by the first i-1 cubes, make the ith cube surround the ith point and have a side less than 1/2ⁱ. Then the total volume of the cubes can be no more than 1/7. (I should have said assume the box to have volume 1.)

Title: Re: Filling a Box With Cubes
Post by Icarus on Apr 5^th, 2005, 6:34pm

on 04/04/05 at 22:54:32, Deedlit wrote:

Given a supposed filling of the box, put the cubes in a sequence with monotonically decreasing size. Let C_n be the union of the first n cubes. I think you can always choose an h_n small enough that the set of all points in the box whose distance from C_n is at least h_n contains points that will fall outside of the n+1^st cube. For each n, the set of all points at least h_n away from C_n provides the needed sequence of nested closed sets.

Of course, this is just an idea, and I haven't run with it to see if you really can prove that h_n>0 exists, but if it does, the result is proved.

on 04/04/05 at 22:54:32, Deedlit wrote:

No - any generalized Cantor set is the intersection of a sequence of finite unions of closed intervals. As such it is closed. So it's closure is itself, not all of [0,1].

However, there is a simple counterexample to my faux pas: The rationals in [0,1] have measure 0 (being countable), but their closure is all of [0,1].

Sorry - you are right, 3 does not necessarily imply 2.

Title: Re: Filling a Box With Cubes
Post by Deedlit on Apr 6^th, 2005, 1:44am

on 04/05/05 at 18:34:05, Icarus wrote:

Of course, this is just an idea, and I haven't run with it to see if you really can prove that h_n>0 exists, but if it does, the result is proved.

Right, but I'm rather less sanguine about this approach. This fixes a margin of error for the remaining cubes, and I'm guessing that it's enough for success.

Quote:

No - any generalized Cantor set is the intersection of a sequence of finite unions of closed intervals. As such it is closed. So it's closure is itself, not all of [0,1].

I was talking about [0,1] minus the Cantor set, which has closure [0,1] since the Cantor set is nowhere dense.

Quote:

However, there is a simple counterexample to my faux pas: The rationals in [0,1] have measure 0 (being countable), but their closure is all of [0,1].

Yeah, that would have been simpler. :P