Author |
Topic: Filling a Box With Cubes (Read 7294 times) |
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
Filling a Box With Cubes
« on: Aug 23rd, 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 23rd, 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 23rd, 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 23rd, 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 25th, 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 25th, 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 25th, 2003, 12:28pm by tohuvabohu » |
IP Logged |
|
|
|
Grant Fikes
Guest
|
|
Re: Filling a Box With Cubes
« Reply #5 on: Nov 6th, 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 11th, 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 12th, 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 12th, 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 12th, 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 21st, 2004, 9:42am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Alfihar
Newbie
Gender:
Posts: 5
|
|
Re: Filling a Box With Cubes
« Reply #10 on: Sep 21st, 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: 2873
|
|
Re: Filling a Box With Cubes
« Reply #11 on: Sep 22nd, 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 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.
|
|
IP Logged |
|
|
|
John_Gaughan
Uberpuzzler
Behold, the power of cheese!
 
Gender:
Posts: 767
|
|
Re: Filling a Box With Cubes
« Reply #12 on: Sep 22nd, 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: 2873
|
|
Re: Filling a Box With Cubes
« Reply #13 on: Sep 22nd, 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 3rd, 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 4th, 2005, 5:55am » |
Quote Modify
|
on Apr 3rd, 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 4th, 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 4th, 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 3rd, 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 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.
|
|
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 4th, 2005, 10:54pm » |
Quote Modify
|
on Apr 4th, 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 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.)
|
| « Last Edit: Apr 4th, 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 5th, 2005, 6:34pm » |
Quote Modify
|
on Apr 4th, 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 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 Apr 4th, 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 6th, 2005, 1:44am » |
Quote Modify
|
on Apr 5th, 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 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. 
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print