wu :: forums
ę wu :: forums - Filling a Box With Cubes Ľ

Welcome, Guest. Please Login or Register.
Sep 23rd, 2018, 4:32pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   hard
(Moderators: Icarus, towr, william wu, SMQ, Grimbal, ThudnBlunder, Eigenray)
   Filling a Box With Cubes
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Filling a Box With Cubes  (Read 6435 times)
william wu
wu::riddles Administrator
*****





   
WWW

Gender: male
Posts: 1291
Filling a Box With Cubes  
« on: Aug 23rd, 2003, 2:14am »
Quote Quote Modify 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: male
Posts: 102
Re: Filling a Box With Cubes  
« Reply #1 on: Aug 23rd, 2003, 6:00am »
Quote Quote Modify 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: male
Posts: 203
Re: Filling a Box With Cubes  
« Reply #2 on: Aug 23rd, 2003, 6:40pm »
Quote Quote Modify 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
*****





   
Email

Gender: male
Posts: 949
Re: Filling a Box With Cubes  
« Reply #3 on: Aug 25th, 2003, 9:39am »
Quote Quote Modify 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: male
Posts: 102
Re: Filling a Box With Cubes  
« Reply #4 on: Aug 25th, 2003, 11:48am »
Quote Quote Modify 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

Email

Re: Filling a Box With Cubes  
« Reply #5 on: Nov 6th, 2003, 11:25am »
Quote Quote Modify Modify Remove 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: male
Posts: 4863
Re: Filling a Box With Cubes  
« Reply #6 on: Nov 11th, 2003, 6:55pm »
Quote Quote Modify 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

Email

Re: Filling a Box With Cubes  
« Reply #7 on: Nov 12th, 2003, 6:32am »
Quote Quote Modify Modify Remove 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: male
Posts: 4863
Re: Filling a Box With Cubes  
« Reply #8 on: Nov 12th, 2003, 6:12pm »
Quote Quote Modify 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! Wink
« 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: male
Posts: 5
Re: Filling a Box With Cubes  
« Reply #9 on: Sep 21st, 2004, 9:42am »
Quote Quote Modify 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: male
Posts: 5
Re: Filling a Box With Cubes  
« Reply #10 on: Sep 21st, 2004, 9:47am »
Quote Quote Modify Modify

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





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2818
Re: Filling a Box With Cubes  
« Reply #11 on: Sep 22nd, 2004, 6:39am »
Quote Quote Modify 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!

5187759 5187759   john23874   SnowmanJTG
WWW Email

Gender: male
Posts: 767
Re: Filling a Box With Cubes  
« Reply #12 on: Sep 22nd, 2004, 7:50am »
Quote Quote Modify 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
*****





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2818
Re: Filling a Box With Cubes  
« Reply #13 on: Sep 22nd, 2004, 9:22am »
Quote Quote Modify 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 Quote Modify 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: male
Posts: 2276
Re: Filling a Box With Cubes  
« Reply #15 on: Apr 4th, 2005, 5:55am »
Quote Quote Modify 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 Quote Modify Modify

Oops.  Embarassed 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: male
Posts: 4863
Re: Filling a Box With Cubes  
« Reply #17 on: Apr 4th, 2005, 6:36pm »
Quote Quote Modify 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 Quote Modify 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: male
Posts: 4863
Re: Filling a Box With Cubes  
« Reply #19 on: Apr 5th, 2005, 6:34pm »
Quote Quote Modify 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 Quote Modify 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.  Tongue
IP Logged
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

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