Author 
Topic: Filling a Box With Cubes (Read 6435 times) 

william wu
wu::riddles Administrator
Gender:
Posts: 1291


Filling a Box With Cubes
« on: Aug 23^{rd}, 2003, 2:14am » 
Quote Modify

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.

« Last Edit: Aug 23^{rd}, 2003, 2:19am by william wu » 
IP Logged 
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com



tohuvabohu
Junior Member
Gender:
Posts: 102


Re: Filling a Box With Cubes
« Reply #1 on: Aug 23^{rd}, 2003, 6:00am » 
Quote Modify

Unless my reasoning is bogus, I don't think this one belongs in Hard. 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.


IP Logged 



Lightboxes
Full Member
Gender:
Posts: 203


Re: Filling a Box With Cubes
« Reply #2 on: Aug 23^{rd}, 2003, 6:40pm » 
Quote Modify

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


IP Logged 
A job is not worth doing unless it's worth doing well.



James Fingas
Uberpuzzler
Gender:
Posts: 949


Re: Filling a Box With Cubes
« Reply #3 on: Aug 25^{th}, 2003, 9:39am » 
Quote Modify

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.


IP Logged 
Doc, I'm addicted to advice! What should I do?



tohuvabohu
Junior Member
Gender:
Posts: 102


Re: Filling a Box With Cubes
« Reply #4 on: Aug 25^{th}, 2003, 11:48am » 
Quote Modify

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.

« Last Edit: Aug 25^{th}, 2003, 12:28pm by tohuvabohu » 
IP Logged 



Grant Fikes
Guest


Re: Filling a Box With Cubes
« Reply #5 on: Nov 6^{th}, 2003, 11:25am » 
Quote Modify
Remove

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]


IP Logged 



Icarus
wu::riddles Moderator Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863


Re: Filling a Box With Cubes
« Reply #6 on: Nov 11^{th}, 2003, 6:55pm » 
Quote Modify

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.


IP Logged 
"Pi goes on and on and on ... And e is just as cursed. I wonder: Which is larger When their digits are reversed? "  Anonymous



visitor
Guest


Re: Filling a Box With Cubes
« Reply #7 on: Nov 12^{th}, 2003, 6:32am » 
Quote Modify
Remove

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.


IP Logged 



Icarus
wu::riddles Moderator Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863


Re: Filling a Box With Cubes
« Reply #8 on: Nov 12^{th}, 2003, 6:12pm » 
Quote Modify

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!

« Last Edit: Nov 12^{th}, 2003, 6:23pm by Icarus » 
IP Logged 
"Pi goes on and on and on ... And e is just as cursed. I wonder: Which is larger When their digits are reversed? "  Anonymous



Alfihar
Newbie
Gender:
Posts: 5


Re: Filling a Box With Cubes
« Reply #9 on: Sep 21^{st}, 2004, 9:42am » 
Quote Modify

Hola, this may not be that important, but it bugs me a lil.. shouldn't the problem require noncubie 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.


IP Logged 



Alfihar
Newbie
Gender:
Posts: 5


Re: Filling a Box With Cubes
« Reply #10 on: Sep 21^{st}, 2004, 9:47am » 
Quote Modify

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


IP Logged 



rmsgrey
Uberpuzzler
Gender:
Posts: 2818


Re: Filling a Box With Cubes
« Reply #11 on: Sep 22^{nd}, 2004, 6:39am » 
Quote Modify

Since this has been resurrected, I thought I'd fill in a small corner case  with a finite number of noncongruent 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.


IP Logged 



John_Gaughan
Uberpuzzler
Behold, the power of cheese!
Gender:
Posts: 767


Re: Filling a Box With Cubes
« Reply #12 on: Sep 22^{nd}, 2004, 7:50am » 
Quote Modify

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?


IP Logged 
x = (0x2B  ~0x2B) x == the_question



rmsgrey
Uberpuzzler
Gender:
Posts: 2818


Re: Filling a Box With Cubes
« Reply #13 on: Sep 22^{nd}, 2004, 9:22am » 
Quote Modify

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.


IP Logged 



Deedlit
Senior Riddler
Posts: 476


Re: Filling a Box With Cubes
« Reply #14 on: Apr 3^{rd}, 2005, 10:24pm » 
Quote Modify

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?


IP Logged 



Barukh
Uberpuzzler
Gender:
Posts: 2276


Re: Filling a Box With Cubes
« Reply #15 on: Apr 4^{th}, 2005, 5:55am » 
Quote Modify

on Apr 3^{rd}, 2005, 10:24pm, Deedlit wrote:I have a feeling definition 1 is false, but I'm not sure. Any ideas? 
 How can a definition be false?


IP Logged 



Deedlit
Senior Riddler
Posts: 476


Re: Filling a Box With Cubes
« Reply #16 on: Apr 4^{th}, 2005, 6:48am » 
Quote Modify

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


IP Logged 



Icarus
wu::riddles Moderator Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863


Re: Filling a Box With Cubes
« Reply #17 on: Apr 4^{th}, 2005, 6:36pm » 
Quote Modify

(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 Apr 3^{rd}, 2005, 10:24pm, 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.


IP Logged 
"Pi goes on and on and on ... And e is just as cursed. I wonder: Which is larger When their digits are reversed? "  Anonymous



Deedlit
Senior Riddler
Posts: 476


Re: Filling a Box With Cubes
« Reply #18 on: Apr 4^{th}, 2005, 10:54pm » 
Quote Modify

on Apr 4^{th}, 2005, 6:36pm, 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 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 i1 cubes, make the ith cube surround the ith point and have a side less than 1/2^{i}. 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.)

« Last Edit: Apr 4^{th}, 2005, 11:10pm by Deedlit » 
IP Logged 



Icarus
wu::riddles Moderator Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863


Re: Filling a Box With Cubes
« Reply #19 on: Apr 5^{th}, 2005, 6:34pm » 
Quote Modify

on Apr 4^{th}, 2005, 10:54pm, 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 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 Apr 4^{th}, 2005, 10:54pm, 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.


IP Logged 
"Pi goes on and on and on ... And e is just as cursed. I wonder: Which is larger When their digits are reversed? "  Anonymous



Deedlit
Senior Riddler
Posts: 476


Re: Filling a Box With Cubes
« Reply #20 on: Apr 6^{th}, 2005, 1:44am » 
Quote Modify

on Apr 5^{th}, 2005, 6:34pm, 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.


IP Logged 



