wu :: forums - Print Page


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

        riddles >> medium >> Minimum Cut Length
        
(Message started by: ThudanBlunder on Sep 26^th, 2007, 10:06am)

Title: Minimum Cut Length
Post by ThudanBlunder on Sep 26^th, 2007, 10:06am

What is the minimum total cut-length required in order to divide
1) an equilateral triangle of unit side-length into four equal parts?
2) a unit square into five equal parts?

Title: Re: Minimum Cut Length
Post by hiyathere on Sep 26^th, 2007, 11:54am

With some very quick calculations, I get:

1) [hide]3 cuts, total 1 1/2 units length.[/hide]

2) [hide]4 cuts, total 4 units length.[/hide]

I'm not so sure about the second one, though.

Title: Re: Minimum Cut Length
Post by Grimbal on Sep 26^th, 2007, 1:06pm

Equal in area only, or equal in shape?

Title: Re: Minimum Cut Length
Post by ThudanBlunder on Sep 26^th, 2007, 2:21pm

on 09/26/07 at 11:54:24, hiyathere wrote:

With some very quick calculations, I get:
1) [hide]3 cuts, total 1 1/2 units length.[/hide]
2) [hide]4 cuts, total 4 units length.[/hide]

Not bad, hiyathere.
But for 1) my answer is about 10% less and for 2) considerably less.

on 09/26/07 at 13:06:55, Grimbal wrote:

Equal in area only, or equal in shape?

Area only.

Title: Re: Minimum Cut Length
Post by Joe Fendel on Sep 26^th, 2007, 3:14pm

Well, for 1) I can see a way to do it with [hide](1 + sqrt(3))/2[/hide] total cut length, by [hide]cutting off a corner into an equilateral triangle with a 1/2-cut and then cut the remaining trapezoid into two trapezoids and a rectangle with two (sqrt(3)/4)-cuts[/hide], which is consistent with the "about 10% less" that TaB mentions.

For 2), I might take the same basic approach, and [hide]cut off two opposite corners into 45-45-90 triangles with legs of sqrt(2/5) and the diagonal (cuts) of sqrt(4/5). This leaves a hexagon in the middle, with a width of sqrt(2) - sqrt(4/5). This hexagon can be cut into two pentagons and a rectangle across its width, which means two more cuts of (sqrt(2) - sqrt(4/5)).[/hide] This totals [hide]2*sqrt(2)[/hide] total cut-length.

Is that what you had in mind, TaB?

Title: Re: Minimum Cut Length
Post by ThudanBlunder on Sep 26^th, 2007, 7:17pm

Welcome to the forum, Joe!

Although your answers are quite close to mine, the dissections are dissimilar.

Title: Re: Minimum Cut Length
Post by FiBsTeR on Sep 26^th, 2007, 8:36pm

on 09/26/07 at 19:17:26, ThudanBlunder wrote:

Although your answers are quite close to mine, the dissections are dissimilar.

By "quite close", do you mean his solutions can be bettered?

Title: Re: Minimum Cut Length
Post by ThudanBlunder on Sep 26^th, 2007, 8:42pm

on 09/26/07 at 20:36:21, FiBsTeR wrote:

By "quite close", do you mean his solutions can be bettered?

Of course.
I have an answer in decimal and the construction.
I have tried to calculate the exact answer for 1) but it gets a bit messy.
But 2) looks more tractable. I will have a look later.

Title: Re: Minimum Cut Length
Post by FiBsTeR on Sep 26^th, 2007, 8:54pm

on 09/26/07 at 20:42:05, ThudanBlunder wrote:

Of course.
I have an answer in decimal and the construction.
I have tried to calculate the exact answer but it gets a bit messy.

Gahhh, it's midnight and I should be doing homework, not wasting paper drawing triangles!

~~One last question: I guess it's safe to assume that your constructions are optimal since you said minimum?~~ <-- Stupid question, of course it is. ::)

Title: Re: Minimum Cut Length
Post by ThudanBlunder on Sep 26^th, 2007, 9:01pm

on 09/26/07 at 20:54:07, FiBsTeR wrote:

Stupid question, of course it is. ::)

That's what the question says. How it has been proved to be optimal I don't know. I omitted a third part of the question (to divide an equilateral triangle in five equal areas) because it said the answer is not known.

Title: Re: Minimum Cut Length
Post by Barukh on Sep 26^th, 2007, 9:42pm

Are there any restrictions on the cuts?

Title: Re: Minimum Cut Length
Post by Grimbal on Sep 27^th, 2007, 12:45am

For the triangle, I can do [hide]1.428469[/hide]
For the square, it is [hide]a bit messy[/hide]

ps: allowing non-straight cuts.

Oops, not even better as previous solutions.

Title: Re: Minimum Cut Length
Post by Barukh on Sep 27^th, 2007, 12:58am

Are only straight cuts allowed?

Title: Re: Minimum Cut Length
Post by ThudanBlunder on Sep 27^th, 2007, 4:13am

on 09/27/07 at 00:58:30, Barukh wrote:

Are only straight cuts allowed?

I don't see why straight lines should get preferential treatment, do you? :P

Title: Re: Minimum Cut Length
Post by Grimbal on Sep 27^th, 2007, 4:42am

Intermediate result:
2) [hide]6/sqrt(5) = 2.68[/hide] with straight cuts

Title: Re: Minimum Cut Length
Post by Barukh on Sep 27^th, 2007, 6:12am

on 09/27/07 at 04:13:04, ThudanBlunder wrote:

I don't see why straight lines should get preferential treatment, do you? :P

Well, I don't see as far as you do. :P

2) [hide]2.576[/hide]?

Title: Re: Minimum Cut Length
Post by hiyathere on Sep 27^th, 2007, 10:08am

Equal in area only...

Makes it so much easier now. I'm gonna start calculating, and see what I can get.

Title: Re: Minimum Cut Length
Post by FiBsTeR on Sep 27^th, 2007, 10:12am

Shhh, don't tell my physics teacher I've been working on puzzles in his class. It's been eating at me all day. :-X

[hide]Construct an arc intersecting the triangle with a vertex of the triangle as the center and radius sqrt[ 3sqrt(3)/(4pi) ]. Construct a similar arc on another vertex.[/hide]

Title: Re: Minimum Cut Length
Post by Sameer on Sep 27^th, 2007, 10:15am

on 09/27/07 at 10:12:33, FiBsTeR wrote:

Shhh, don't tell my physics teacher I've been working on puzzles in his class. :-X

This will make your math formula posting easier:
http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_suggestions;action=display;num=1171644142

And SMQ just put a new version of the script!!

Title: Re: Minimum Cut Length
Post by FiBsTeR on Sep 27^th, 2007, 10:17am

~~I have the script, but I like MathType better. :P~~

Can you make complex fractions using that script?

Title: Re: Minimum Cut Length
Post by hiyathere on Sep 27^th, 2007, 10:30am

OK. I redid question 1, keeping in mind that I only have to have the same area, and I got [hide]1/2 + sqrt(3/4) = 1.366[/hide].

Title: Re: Minimum Cut Length
Post by ThudanBlunder on Sep 27^th, 2007, 12:07pm

FiBsTeR, your answer simplifies to http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif/http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif3), which is slightly more than mine.
What is your value for one arc length in surds?

on 09/27/07 at 10:17:26, FiBsTeR wrote:

Can you make complex fractions using that script?

Yes, but only when you have to. :P

Title: Re: Minimum Cut Length
Post by Joe Fendel on Sep 27^th, 2007, 12:31pm

I think I need some soap...

Title: Re: Minimum Cut Length
Post by FiBsTeR on Sep 27^th, 2007, 2:25pm

on 09/27/07 at 10:30:46, hiyathere wrote:

OK. I redid question 1, [...]

Your answer is higher than mine...

on 09/27/07 at 12:07:34, ThudanBlunder wrote:

FiBsTeR, your answer simplifies to \sqrt(\pi/\sqrt3)

I'm no good at simplifying: too messy, but I think the way I put it makes it clear how I got the answer.

on 09/27/07 at 12:07:34, ThudanBlunder wrote:

What is your value for one arc length in surds?

If you could clarify what a surd is I'd appreciate it: the Wiki article (http://en.wikipedia.org/wiki/Nth_root#Working_with_surds) wasn't all too clear; the MathWorld one was even more vague.

EDIT: Arc length in my next post...

Title: Re: Minimum Cut Length
Post by ThudanBlunder on Sep 27^th, 2007, 2:39pm

on 09/27/07 at 14:25:01, FiBsTeR wrote:

If you could clarify what a surd is I'd appreciate it: [/i]

In the form that you posted using MathType, ie. radicals (square roots in this case).
That is, the exact, non-decimal form.

Title: Re: Minimum Cut Length
Post by FiBsTeR on Sep 27^th, 2007, 3:05pm

on 09/27/07 at 14:39:19, ThudanBlunder wrote:

In the form that you posted using MathType

(The following refers to the figure in the next post.)

Title: Re: Minimum Cut Length
Post by FiBsTeR on Sep 27^th, 2007, 3:05pm

Obviously not to scale...

Title: Re: Minimum Cut Length
Post by ThudanBlunder on Sep 27^th, 2007, 4:32pm

Nice work, FiBsTeR!

But for this construction (with three arcs) I get
http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif3/16 = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif r²/6
Giving r² = (3 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif3 /(8http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif))
and
r = 0.45469587...
and
http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gifr = total cut length = 1.4284692...

Edit: Corrected formula for r²

Title: Re: Minimum Cut Length
Post by FiBsTeR on Sep 27^th, 2007, 4:44pm

on 09/27/07 at 16:32:07, ThudanBlunder wrote:

Nice work, FiBsTeR!

But for this construction (with three arcs) I get
[...]
Giving r² = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif(3 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif3 /(8http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif))
and
r = 0.45469587...
and
3r = total cut length = 1.36408761...

Don't you mean "Giving r² = 3 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif3 /(8http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif)"?

on 09/27/07 at 12:07:34, ThudanBlunder wrote:

Doesn't your construction yield a cut length greater than mine?

Title: Re: Minimum Cut Length
Post by ThudanBlunder on Sep 27^th, 2007, 4:56pm

on 09/27/07 at 16:44:57, FiBsTeR wrote:

Doesn't your construction yield a cut length greater than mine?

Quite right, yours is less. Venny nice, too. I thought you had made an error.
However, the construction I was referring to does not use three arcs; only one.
I have tried to verify it, but it gets a little messy.

Title: Re: Minimum Cut Length
Post by RandomSam on Sep 27^th, 2007, 4:58pm

For the square, I've got some very complicated trig using arcs of radius
r = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif¹/₁₀ / http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif( 7http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif/6 - http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif2 cos{http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif/12} ) which is approximately 0.7966, and the total line length is
l = 2 + r ( 4http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif2 sin(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif/12) - 2http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif/3 ), which is approximately 2.5021.

Unfortunately, whenever I repeat the calculation, I get a different result.

ThudanBlunder's
Quote:

...and 3r = total cut length = 1.36408761...

Surely each arc length is pi.r/3, so the total length is pi.r, which is 1.428, which Grimbal mentioned and crossed out.

Title: Re: Minimum Cut Length
Post by FiBsTeR on Sep 27^th, 2007, 5:24pm

on 09/27/07 at 16:56:03, ThudanBlunder wrote:

However, the construction I was referring to does not use three arcs; only one.
I have tried to verify it, but it gets a little messy.

Let's see it! :o

Title: Re: Minimum Cut Length
Post by ThudanBlunder on Sep 27^th, 2007, 5:32pm

on 09/27/07 at 16:58:09, RandomSam wrote:

ThudanBlunder's
Surely each arc length is pi.r/3, so the total length is pi.r, which is 1.428, which Grimbal mentioned and crossed out.

Of course, thanks. And welcome to the forum.

You have the the same answer as me for 2) - well done on working out the exact answer.
I will post both constructions soon. See if you can find the exact form for 1). :P

Title: Re: Minimum Cut Length
Post by FiBsTeR on Sep 27^th, 2007, 5:38pm

Looking back at my construction, I think my solution is completely wrong, since it only shows that Y=Z, but not X=Y or X=Z. I'm not sure what I was thinking at the time; I knew it seemed to easy to be a solution! :'(

Title: Re: Minimum Cut Length
Post by ThudanBlunder on Sep 27^th, 2007, 5:46pm

on 09/27/07 at 17:38:13, FiBsTeR wrote:

Never mind, chew on this.

Title: Re: Minimum Cut Length
Post by RandomSam on Sep 28^th, 2007, 2:57am

Well it's easy when the picture's there! I get length:
l = [hide]¹/₂ http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif3 + http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif( http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif / 16http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif3 )[/hide], which is approximately [hide]1.2027[/hide].

Title: Re: Minimum Cut Length
Post by ThudanBlunder on Sep 28^th, 2007, 4:38am

on 09/28/07 at 02:57:03, RandomSam wrote:

Well it's easy when the picture's there! I get length:
l = [hide]¹/₂ \sqrt3 + \sqrt( \pi / 16\sqrt3 )[/hide], which is approximately [hide]1.2027[/hide].

1.2027... is way less than the answer I have.
What is the length of your base bisector?

Title: Re: Minimum Cut Length
Post by FiBsTeR on Sep 28^th, 2007, 7:10am

I don't have any paper in front of me, but I believe the cut length of (a) is:

[sqrt(3) / 2] + (pi)sqrt[3sqrt(3) / (8pi)] / 3 = 1.342

When I get to my other school and get sketchpad/MathType out I'll double-check it and make the fractions neater.

on 09/28/07 at 04:38:48, ThudanBlunder wrote:

What is the length of your base bisector?

The sum of the lengths of the three cuts below the arc should be equal to the height of the triangle.

Title: Re: Minimum Cut Length
Post by ThudanBlunder on Sep 28^th, 2007, 7:45am

on 09/28/07 at 07:10:06, FiBsTeR wrote:

The sum of the lengths of the three cuts below the arc should be equal to the height of the triangle.

Hmm...I didn't notice that.
Anyway, your answer squares with mine.

Title: Re: Minimum Cut Length
Post by RandomSam on Sep 28^th, 2007, 9:40am

on 09/28/07 at 04:38:48, ThudanBlunder wrote:

1.2027... is way less than the answer I have.
What is the length of your base bisector?

Ooops... the 16 in my fraction should have been an 8. Now I get the same answer!

Title: Re: Minimum Cut Length
Post by Barukh on Sep 28^th, 2007, 12:01pm

on 09/27/07 at 16:58:09, RandomSam wrote:

I confirm this result. The derivation is not so complicated.

How do you know 120 degrees gives the optimum?

Title: Re: Minimum Cut Length
Post by ThudanBlunder on Sep 28^th, 2007, 12:56pm

on 09/28/07 at 12:01:31, Barukh wrote:

How do you know 120 degrees gives the optimum?

I don't. But if it is good enough for bees, it is good enough for me. ;)
Nor do I have a proof that 1.342... is the minimum for the triangle.

Title: Re: Minimum Cut Length
Post by Joe Fendel on Sep 28^th, 2007, 4:06pm

on 09/28/07 at 12:56:29, ThudanBlunder wrote:

Nor do I have a proof that 1.342... is the minimum for the triangle.

I don't think it is. I think I've found a method with about 1.3195 of total cut length.

Title: Re: Minimum Cut Length
Post by FiBsTeR on Sep 29^th, 2007, 6:39am

Describe the construction that you did.

Title: Re: Minimum Cut Length
Post by mikedagr8 on Sep 29^th, 2007, 6:59am

on 09/26/07 at 21:01:42, ThudanBlunder wrote:

I omitted a third part of the question (to divide an equilateral triangle in five equal areas) because it said the answer is not known.

Is anyone going to attempt this? I'm putting something together with the help of TB. See if you guys can better me when I post my answer.

Title: Re: Minimum Cut Length
Post by FiBsTeR on Sep 29^th, 2007, 7:33am

on 09/29/07 at 06:59:53, mikedagr8 wrote:

Is anyone going to attempt this? I'm putting something together with the help of TB. See if you guys can better me when I post my answer.

Here's one of the more obvious solutions to start with:

(correction made to image -- 11:40 AM 9/29/07)

Title: Re: Minimum Cut Length
Post by Joe Fendel on Sep 29^th, 2007, 7:35am

on 09/29/07 at 06:39:58, FiBsTeR wrote:

Describe the construction that you did.

It only uses straight lines, so it's probably sub-optimal.

Not sure if this image import will work, though...

Title: Re: Minimum Cut Length
Post by FiBsTeR on Sep 29^th, 2007, 7:37am

~~The total cut length in that image is 1.578... Nice construction, though!~~

:-[

Title: Re: Minimum Cut Length
Post by Joe Fendel on Sep 29^th, 2007, 7:50am

on 09/29/07 at 07:37:27, FiBsTeR wrote:

The total cut length in that image is 1.578... Nice construction, though!

Is it? I was adding 0.2585 + 2*(0.4188 + 0.1117) to get 1.3194. (With extra precision, it's closer to 1.3195.) Is my arithmetic off, or my reasoning?

Also, I think if we bulge that middle bar to an arc which makes 120-degree angles with the other lines, we can cut this down to about 1.3173. However, I'm still not certain that this is optimal.

Title: Re: Minimum Cut Length
Post by mikedagr8 on Sep 29^th, 2007, 7:53am

on 09/29/07 at 07:50:49, Joe Fendel wrote:

~~Arithmetic. You only added 1 lot of '0.2585' .~~

Title: Re: Minimum Cut Length
Post by FiBsTeR on Sep 29^th, 2007, 8:00am

The cut length is:

2(0.2585 + 0.4188 + 0.1117) = 1.578 :-[

EDIT: On a different note, I've bettered my solution for the 5-area triangle problem by about 0.019:

Title: Re: Minimum Cut Length
Post by FiBsTeR on Sep 29^th, 2007, 8:59am

Here's the construciton:

Note that, as before, the non-arc cuts sum to the length of the height of the triangle. (This is simply because 2 cos(30⁰) = 1.)

Title: Re: Minimum Cut Length
Post by Joe Fendel on Sep 29^th, 2007, 9:28am

on 09/29/07 at 06:59:53, mikedagr8 wrote:

Is anyone going to attempt this? I'm putting something together with the help of TB. See if you guys can better me when I post my answer.

Well, I can do about 1.6247 in the 5-areas triangle, but my arithmetic is apparently suspect. (Though I'm afraid I'm having trouble seeing my error in the 4-areas triangle. Where are the two cuts of length 0.2585 in my construction? I'm still only seeing one.)

My construction for the 1.6247 is virtually identical to the 1.3173 for the 4-areas, but adding an arc to the top.

Title: Re: Minimum Cut Length
Post by FiBsTeR on Sep 29^th, 2007, 10:15am

on 09/29/07 at 09:28:56, Joe Fendel wrote:

Where are the two cuts of length 0.2585 in my construction?

1) There are 6 total line segments in your cut; two segments for three distinct lengths.

2) The rectangle in the center of the triangle has four sides, two of which have length 0.2585.

:-[

Title: Re: Minimum Cut Length
Post by ThudanBlunder on Sep 29^th, 2007, 10:18am

on 09/29/07 at 10:15:11, FiBsTeR wrote:

2) The rectangle in the center of the triangle has four sides, two of which have length 0.2585.

That is true, but one side of the rectangle is perimeter and therefore not a cut, duh.

Title: Re: Minimum Cut Length
Post by FiBsTeR on Sep 29^th, 2007, 10:49am

lol, oops, sorry! Well, in that case, nice work! :-[

Title: Re: Minimum Cut Length
Post by Grimbal on Sep 29^th, 2007, 3:53pm

on 09/29/07 at 08:59:11, FiBsTeR wrote:

Here's the construciton:

Note that, as before, the non-arc cuts sum to the length of the height of the triangle. (This is simply because 2 cos(30⁰) = 1.)

If you keep just the Y cut, you can see that the way to cut the sides in 2 is not optimal. It would be shorter to replace the arcs left and right with a single arc centered on the top vertex, cutting 3/5 area from the top. The arc would cut the Y at the vertical line.

Title: Re: Minimum Cut Length
Post by ThudanBlunder on Sep 29^th, 2007, 4:42pm

on 09/29/07 at 15:53:56, Grimbal wrote:

Then I get
r² = 9http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif3/10http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif
r = 0.704412...
Arc length = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gifr/3

Total Cut = ~~(1 + http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif/3)r = 1.442070521...~~

EDIT: Should be http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gifr/3 + http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif3/2 = 1.60368...

Title: Re: Minimum Cut Length
Post by FiBsTeR on Sep 29^th, 2007, 5:01pm

If you are referring to the following figure, the cut length is in fact equal to what I have above. No matter how you draw the Y-cut, the length of those three segments is always the length of the height. The remaining cut(s), whether you do it as two arcs on the bottom-left and -right or as one arc from the top, are also equal.

My construction is shown in red, Grimbal's proposed construction in black.

Nevermind, I calculated the radius wrong. My numbers don't agree with T&B's, though: I get total cut length of 1.60368...

Title: Re: Minimum Cut Length
Post by FiBsTeR on Sep 29^th, 2007, 5:09pm

~~And if you don't trust the picture, here's the cut lengths; the first is mine, the second is Grimbal's.~~

EDIT: (images removed)

Title: Re: Minimum Cut Length
Post by ThudanBlunder on Sep 29^th, 2007, 6:34pm

on 09/29/07 at 17:01:33, FiBsTeR wrote:

[s]Nevermind, I calculated the radius wrong. My numbers don't agree with T&B's, though: I get total cut length of 1.60368...

Yes, I agree.

It is http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gifr/3 + http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif3/2

Title: Re: Minimum Cut Length
Post by mikedagr8 on Sep 29^th, 2007, 6:46pm

Never Mind, I was beaten before I even started. Haha, I tried. :)

My answer is 1.736995

Title: Re: Minimum Cut Length
Post by Barukh on Sep 30^th, 2007, 11:36am

on 09/28/07 at 12:56:29, ThudanBlunder wrote:

I don't. But if it is good enough for bees, it is good enough for me. ;)

For this particular configuration, the minimum does occur at 120^o, but I fail to prove it...

Can anybody show that the following function has a minimum at http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif/6?

(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif - http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif2 sin(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif/2))²
-----------------------------
http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif + 1 - http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif2 cos(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif - http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif/4)

Besides, bees don’t build circular cells, do they?

Title: Re: Minimum Cut Length
Post by ThudanBlunder on Sep 30^th, 2007, 2:07pm

on 09/30/07 at 11:36:13, Barukh wrote:

Besides, bees don’t build circular cells, do they?

I conjecture that for circles that enclose a given area while intersecting in this way, ones that intersect at 120^o have the least perimeter. For example, in 3D when soap bubbles partly merge I believe they do so at 120^o.

My graphing software (Graphmatica) confirms that the minimum is at x = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif/6.

Title: Re: Minimum Cut Length
Post by SWF on Sep 30^th, 2007, 3:25pm

Minimizing length of these lines is analgous to the problem how to divide the shape into chambers by soap films (or since we are working in 2-D, the line equivalent). The condition of equilibrium of force at any point on the line applies. Thus, you have various necessary conditions including:

1. Where more than 2 cuts meet at point internal to the shape, they equally divide 360 degrees. i.e. where three cuts meet at a point, the angle is 120 degrees; 90 degrees where four cuts meet, ...

2. If a single cut meets a single boundary of the shape at a single point, it will be perpendicular to that boundary.

3. Each segment of cut will have a constant curvature (it will be a line or a circular arc).

4. The curvature of each cut should be consistent with each area having a constant pressure inside. i.e. the pressure difference between two areas equals 1/R, where R is the radius of curvature of the line between the two areas.

One method of solution might be to start with a topology that does not give equal sized areas. Then if an area is too small, increase its pressure and recalculate the equilibrium configuration of that topology, until it has the right area. Similarly, change the pressures in each region until they all have the same area. I suppose the topology could change while doing that. This should at least give a local minimum cut length.

Title: Re: Minimum Cut Length
Post by Grimbal on Oct 1^st, 2007, 1:49am

on 09/30/07 at 15:25:37, SWF wrote:

1. Where more than 2 cuts meet at point internal to the shape, they equally divide 360 degrees. i.e. where three cuts meet at a point, the angle is 120 degrees; 90 degrees where four cuts meet, ...

I think you can never have more than 3 lines meeting. The meeting point where 4 lines meet can be replaced by \__/ / \ if it is small enough, the saving in length is higher than the length you need to spend compensate for the difference in area

Title: Re: Minimum Cut Length
Post by Joe Fendel on Oct 1^st, 2007, 4:20pm

Just trying to get a status check for this problem. Let me know if I'm wrong:

A) Triangle-into-four: Best so far is my 1.3173, I think. (The construction is shown in reply #46, except bulging the middle bar into an arc.)

B) Square-into-five: Best so far is ThudandBlunder's 2.5021, from the "round square" construction as shown in reply #34.

C) Triangle-into-five: Best so far is Grimbal's 1.6037, described in reply #56 and illustrated by FiBsTeR in reply #58.

Is that right?

Title: Re: Minimum Cut Length
Post by ThudanBlunder on Oct 1^st, 2007, 5:37pm

on 10/01/07 at 16:20:46, Joe Fendel wrote:

A) Triangle-into-four: Best so far is my 1.3173, I think. (The construction is shown in reply #46, except bulging the middle bar into an arc.)

Are the 0.117 lines bisectors of the sides?

Title: Re: Minimum Cut Length
Post by Grimbal on Oct 2^nd, 2007, 3:32am

Not bisectors. It seems it is at 0.5481 from the bottom corners.

It seems that Joe's straight cut solution is better than Richard Hess's solution of 1.3422. ;)

Title: Re: Minimum Cut Length
Post by Joe Fendel on Oct 2^nd, 2007, 8:59am

on 10/02/07 at 03:32:07, Grimbal wrote:

Not bisectors. It seems it is at 0.5481 from the bottom corners.

It seems that Joe's straight cut solution is better than Richard Hess's solution of 1.3422. ;)

Yes, that's correct - 0.5481 from the bottom.

BTW, who is Richard Hess?

Title: Re: Minimum Cut Length
Post by Joe Fendel on Oct 2^nd, 2007, 10:23am

on 10/02/07 at 03:32:07, Grimbal wrote:

It seems that Joe's straight cut solution is better than Richard Hess's solution of 1.3422. ;)

Ah, found him. Richard I. Hess. Apparently the problem came to him from Robert T. Wainwright, the Life guru.

And yes, I think my answer is better. Neat! I haven't found a "mathtype" form for it yet, though. Only a decimal approximation.

Title: Re: Minimum Cut Length
Post by FiBsTeR on Oct 2^nd, 2007, 2:25pm

I've expressed it in MathType, but it's really of little value, since it's a sea of radicals, trig functions, etc., that really won't help you at all. ::) Not to mention it's like one page on Word, landscape, 8-font, in length...

In all of my classes today I've been trying to better your 4-area triangle solution; my math notebook is like half-full of murdered triangles now. :'(

Title: Re: Minimum Cut Length
Post by SWF on Oct 7^th, 2007, 6:26pm

Edited to correct errors pointed out by Grimbal- the picture is unchanged.

Since nobody else tried using the tips I gave previously, here is how the triangle can be cut into 4 pieces with cut length of ~~1.295898~~ 1.305113. In the figure below, the radii of the yellow lines are ~~0.509518~~0.549619 and have center lying on sides ~~.065633~~ 0.016340 away from the bottom vertices. Radii of red lines are ~~1.422117~~ 1.452121 with centers ~~1.765845~~ 1.799440 from the bottom vertices. Green line has radius of ~~0.375120~~ 0.398710 with center ~~0.041847 below~~ 0.010265 above center of the base.

Title: Re: Minimum Cut Length
Post by Grimbal on Oct 13^th, 2007, 9:47am

I don't seem to be able to reconstruct your diagram.

I am especially suspicious about "Radii of red lines are 1.422117 with centers 1.765845 from the bottom vertices." which would mean they are completely outside of the triangle! Even if I take a center 1.765845 right of the left bottom vertex, the 3 circles don't seem to cross in a single line. I tried the yellow circle above or below the left vertex.

Title: Re: Minimum Cut Length
Post by Grimbal on Oct 13^th, 2007, 12:47pm

If I say nothing, that is not because I am not trying. It is just that it takes more time that I thought to write the program that will optimize a diagram numerically and display the result nicely.

http://florian.net/puzzle/pic/mincut_T4c.gif http://florian.net/puzzle/pic/mincut_T4b.gif http://florian.net/puzzle/pic/mincut_T4a.gif
http://florian.net/puzzle/pic/mincut_T5a.gif http://florian.net/puzzle/pic/mincut_T5b.gif http://florian.net/puzzle/pic/mincut_T5c.gif
http://florian.net/puzzle/pic/mincut_S5a.gif

Note: the top right design has a very short vertical segment at the junction, so that in fact all lines join at 120°.

~~And I don't know yet why my result doesn't match SWF's. That is why I wanted to reproduce his/her result.~~

Title: Re: Minimum Cut Length
Post by Michael_Dagg on Oct 14^th, 2007, 8:21am

Those are pretty nice Grimbal.

Title: Re: Minimum Cut Length
Post by SWF on Oct 15^th, 2007, 5:42pm

Thanks for pointing that out Grimbal. I hadn't bothered to verify that all three arcs meet at the same point, but adding that constraint now gives the same thing as Grimbal for a triangle into 4 pieces. Previously my green curve was resulting in the correct y coordinate but was off in x coordinate of intersection point by 0.01.

To avoid confusion by future readers, I have corrected the text of the original post. The picture was left the same, since the corrections don't change the appearance.

Title: Re: Minimum Cut Length
Post by Joe Fendel on Oct 16^th, 2007, 7:53am

Wow! :o Really pretty pics, SWF and Grimbal!