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 23rd, 2003, 2:14am)

Title: Filling a Box With Cubes
Post by william wu on Aug 23rd, 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 23rd, 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 23rd, 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 25th, 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 25th, 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 6th, 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 11th, 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 12th, 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 12th, 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 21st, 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 21st, 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 22nd, 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 22nd, 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 22nd, 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 3rd, 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 4th, 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 4th, 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 4th, 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 Ac be the closure of A, then m(Ac) = 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(Ac), which is the volume of the box.

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

on 04/04/05 at 18:36:00, Icarus wrote:
(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.


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 Ac be the closure of A, then m(Ac) = 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/2i. 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 5th, 2005, 6:34pm

on 04/04/05 at 22:54:32, Deedlit 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.


Given a supposed filling of the box, put the cubes in a sequence with monotonically decreasing size. Let Cn be the union of the first n cubes. I think you can always choose an hn small enough that the set of all points in the box whose distance from Cn is at least hn  contains points that will fall outside of the n+1st cube. For each n, the set of all points at least hn away from Cn 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 hn>0 exists, but if it does, the result is proved.


on 04/04/05 at 22:54:32, Deedlit wrote:
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.


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 6th, 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 hn>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



Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board