wu :: forums - Print Page


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

        riddles >> hard >> Filling a flat bag
        
(Message started by: Leonid Broukhis on May 30^th, 2007, 5:20pm)

Title: Filling a flat bag
Post by Leonid Broukhis on May 30^th, 2007, 5:20pm

You're given a 2x1 flat bag (similar to a wastebasket or a green grocery bag) that is made of two 2x1 rectangles fused at both long edges and one short edge. Assuming the material of the bag is non-elastic (no area-preserving shear allowed either) but infinitely thin and perfectly flexible, what is the maximum volume can it contain when sealed, i.e. when the remaining edges are fused?

I know one thing: the answer is greater than 0.135 (putting a sphere in the bag), but I don't have a slightest idea how to approach this problem except numerically by simulating heated gas in a sealed bag.

A related question: for which smallest k, if any, a maximally filled bag of the k x 1 shape will have circular cross-cut in the middle?

Title: Re: Filling a flat bag
Post by Eigenray on May 30^th, 2007, 7:21pm

This is known as the "paper bag" or "tea bag" problem, and is surprisingly difficult. There's a discussion [link=http://www.ics.uci.edu/~eppstein/junkyard/teabag.html]here[/link], and [link=http://en.wikipedia.org/wiki/Paper_bag_problem]Wikipedia[/link] has an approximate general solution with some references.

Title: Re: Filling a flat bag
Post by Leonid Broukhis on May 30^th, 2007, 8:03pm

on 05/30/07 at 19:21:39, Eigenray wrote:

Thanks. I've guessed right that someone has considered it already. Surprisingly, the infinite case was not considered, and there is a disagreement among my co-workers whether the number k I mentioned in the problem statement exists.

Title: Re: Filling a flat bag
Post by SWF on May 30^th, 2007, 8:16pm

Those links by Eigenray appear to restrict the manner in which the last edge is sealed to an inefficient shape. For the problem Leonid Broukhis poses, my first guess is the volume formed when you seal the remaining edges so that the 4 corners of the two rectangle on the originally open end of the bag all touch at a point. This seems like it should give a large volume since there is no wrinkling or sharp folds of the surfaces. There is one fold on a short edge of each rectangle.

Frozen juice snacks sometimes come in a container of this shape, which is basically a cylinder with the ends pinched shut, with the two pinched ends 90 degrees apart.

Title: Re: Filling a flat bag
Post by Leonid Broukhis on May 30^th, 2007, 8:55pm

on 05/30/07 at 20:16:37, SWF wrote:

When buying bulk gardening soil - that's what prompted posing of the problem - I'd contemplated it, but it did not feel like improving things. I guess 2x1 shape is not enough for the central cross-cut to be circular - a necessary condition for the 90 degrees pinching to be beneficial.

Title: Re: Filling a flat bag
Post by Leonid Broukhis on May 30^th, 2007, 8:58pm

Shoot! But if the cross-cut is ever circular, the relative angle of the pinch would not matter!

Title: Re: Filling a flat bag
Post by towr on May 31^st, 2007, 12:48am

I think I could put a .5x.5x1.5 box in the bag.. that's a volume of 0.375
It can probably be improved on, since some are of the bag isn't used to hold anything (although that will always necessarily be the case in the end)

Title: Re: Filling a flat bag
Post by Leonid Broukhis on May 31^st, 2007, 1:12am

towr, it looks like with the (somewhat pessimistic) formula given by Wikipedia the lower bound can now be safely assumed to be about 0.496.

Title: Re: Filling a flat bag
Post by Grimbal on May 31^st, 2007, 1:17am

on 05/30/07 at 20:58:27, Leonid Broukhis wrote:

Shoot! But if the cross-cut is ever circular, the relative angle of the pinch would not matter!

That would be, assuming the circular cut cuts the rectangles along a line which, unfolded, is perfectly parallel to the short side. But it is not necessarily so.

Title: Re: Filling a flat bag
Post by Leonid Broukhis on May 31^st, 2007, 1:52am

on 05/31/07 at 01:17:22, Grimbal wrote:

That would be, assuming the circular cut cuts the rectangles along a line which, unfolded, is perfectly parallel to the short side. But it is not necessarily so.

How so?

Title: Re: Filling a flat bag
Post by Grimbal on May 31^st, 2007, 3:10am

Imagine a circular stripe around a horizontal circle. If you consider the 4 cardinal points N, S, E and W around the circle, push the stripe up at N and S, and down at W and E. The stripe will slant at the same time.

Now if the stripe was taken around the belly of the bag (or the stripe is in fact 2 units long and 2 units wide), the rest of the bag will naturally close in a way more like a tetrahedron than a pillow. And you cannot convert one configuration to the other by using the circular cut.

Title: Re: Filling a flat bag
Post by Leonid Broukhis on May 31^st, 2007, 9:08am

For a shape to look like a tetrahedron (old Tetrapak milk packaging), the pinches have to be perpendicular.

What I meant was "If the cross-cut of a bag with aligned pinches is ever circular, the relative angle of the pinch would not matter"

Speaking of the tetrahedral shape for a square bag, it will be interesting to know if it really improves things.

Title: Re: Filling a flat bag
Post by SWF on May 31^st, 2007, 8:35pm

If you like this problem you will probably like this thread from a couple of years ago: Designing a baseball (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1124994244)

Title: Re: Filling a flat bag
Post by Leonid Broukhis on May 31^st, 2007, 9:05pm

Thank you, SWF. One thing I did not understand: how strict was the planarity constraint? As far as I see it, the shape to reach should be two circular shapes stitched together and "inflated" the same way as in this problem. An approximation to that shape with a finite number of folds would do.

Title: Re: Filling a flat bag
Post by Barukh on Jun 1^st, 2007, 3:36am

on 05/30/07 at 17:20:55, Leonid Broukhis wrote:

I know one thing: the answer is greater than 0.135 (putting a sphere in the bag)

My imagination is not enough to grasp this. How would you do this?

Title: Re: Filling a flat bag
Post by SWF on Jun 1^st, 2007, 7:17pm

For the baseball problem, I suppose you are allowed to let it wrinkle, and try to figure out the result for two circles stitched together, but I don't think it would beat the other solutions proposed. Those wrinkles would greatly reduce the efficiency.

Two 2x1 rectangles could be stitched together like a baseball to cover a 1x1x0.5 block, which gives a volume greater than the 0.496 in the Wikipedia bound. However neither of satisfies the conditions of this question: this is not the stitching pattern asked for in this problem, and the Wikipedia bounds appear to be allowing shear.

Title: Re: Filling a flat bag
Post by Grimbal on Jun 3^rd, 2007, 12:58pm

While I was occupied with a task that left my brain idle, I came up with the following explicit solution: make a cylinder and close the ends by folding along the line where the cylinder would intersect a perpendicular cylinder, making the ends a negative cylinder.

The volume is 0.464612 or 2/pi - 16/3/pi³.

http://florian.net/puzzle/pic/fillbag.jpg

Title: Re: Filling a flat bag
Post by Leonid Broukhis on Jun 3^rd, 2007, 8:37pm

Grimbal, this is an easy to understand solution, but it is far from optimal, even the pessimistic formula on wikipedia gives 0.496.

Title: Re: Filling a flat bag
Post by Leonid Broukhis on Jun 3^rd, 2007, 8:39pm

on 06/01/07 at 03:36:30, Barukh wrote:

My imagination is not enough to grasp this. How would you do this?

Make the opening round (circumference 2), drop a sphere with radius 1/pi into the bag, close the bag.

Title: Re: Filling a flat bag
Post by Grimbal on Jun 4^th, 2007, 1:39am

on 06/03/07 at 20:37:30, Leonid Broukhis wrote:

Grimbal, this is an easy to understand solution, but it is far from optimal, even the pessimistic formula on wikipedia gives 0.496.

Yes, I know. The corners would probably be near conical in an optimal solution.
But if what SWF says is true

on 06/01/07 at 19:17:46, SWF wrote:

... and the Wikipedia bounds appear to be allowing shear.

it is not a reliable lower bound. So I wanted to provide an explicit shape that gives a lower bound better than dropping a ball in the bag.

Note that I checked the article, it doesn't seem to allow streching, and shear implies stretchng in some direction.

Title: Re: Filling a flat bag
Post by Icarus on Jun 4^th, 2007, 4:02pm

I've seen real-life examples that seem to back Grimbal's idea, though in that case there was some stretching, and the dimensions were not necessarily 2x1.

Title: Re: Filling a flat bag
Post by SWF on Jun 4^th, 2007, 8:54pm

Grimbal's shape seems quite good to me. I had considered that one briefly, but must have messed up in my estimate of its volume. At first I had some reservations about whether it is possible to put a curved fold in a material that cannot stretch or shear, but I guess that is OK.

The tetrahedron-like shape with pinched ends looks like its volume is less than .4. I made the estimate by assuming elliptical cross-sections where the ellipse aspect ratio varies along the length.

Title: Re: Filling a flat bag
Post by Leonid Broukhis on Jun 4^th, 2007, 11:16pm

I don't have a toilet paper tube handy, but it seems to me that if you pinch the ends without pressing them inwards, the volume (a cylinder minus two cylinders at 45 degrees to the first at each end) will be greater than of Grimbal's figure.

Title: Re: Filling a flat bag
Post by SWF on Jun 5^th, 2007, 5:54pm

I wish there was more time for me to work on this, because this is a nice problem. But I did have a couple of minutes to make a tube out of paper, flatten it, tape one end shut, and blow into the other end. Use thin paper instead of cardboard so it can easily flex, make it longer than 2x1 aspect ratio so it is easy to blow into, and don't do it in a public place.

The resulting shape is similar to Grimbal's, except the points get inflated a bit for more volume. It is hard to see if there should be any sharp creases, since the paper is not perfectly flexible, but it looks like it might have a sharp crease as a perpendicular bisector of the short seam- right between the inflated lobes. The rest of the shape, except for the corners of the rectangles, looks like a smooth curvature.

Title: Re: Filling a flat bag
Post by SWF on Jun 7^th, 2007, 10:18pm

I think I have a new lower bound, although it still needs to be checked more carefully. If the rectangle is h by w (with h>=w), volume is at least:

w²/pi*( h - 2w/(3*pi) - 4w/(3*pi²) )

For 2 by 1 rectangles that gives a volume of 0.5261.

Will try to explain better when I get a chance, but basically the shape is a cylinder of length (h-2w/pi) with two pointy tips on each end as in Grimbal's shape, but this has different points. Each point is made up of three segments of conical surface. The three cones defining these surfaces are not right circular cones, but have an elliptical cross-section such that when cut at the proper angle to the axis leave a circle with same radius as the cylinder.

(Edit:) After checking this, there is an error here. The shape I was thinking of does not quite flatten to the rectangle. What I was thinking was the surface of an elliptical cone cut at an angle so its base is a circle, should be a portion of a cylinder's surface.