mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2021-08-30, 11:03   #12
uau
 
Jan 2017

12010 Posts
Default

Quote:
Originally Posted by retina View Post
Are you sure that some other shape, that is not a simple circle segment, won't give more area?
In any problem like this, each part should at least locally be a circle segment. If you have two points and a freely shaped path of a certain length between them, unless that path is a circle segment, you can make the area larger for the same path length.

Proof: if you claim to have a counterexample - that is, a path between two points points which is not a circle segment and which gives a larger area than a circle segment of equivalent length for the shape formed by the path and the line between the points - then you can take a circle where the corresponding circle segment appears, and switch it with your shape, getting a solution better than a circle for a totally free shape. This proves that a circle segment is optimal, unless you believe a circle is suboptimal for a totally free shape.
uau is offline   Reply With Quote
Old 2021-08-30, 11:04   #13
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

2·3·52·73 Posts
Default

Quote:
Originally Posted by retina View Post
Are you sure that some other shape, that is not a simple circle segment, won't give more area?
If you can't find a simple expression for the area of an arbitrary shape, part of the boundary of which is a concave circular arc, this sounds like an ideal problem for simulated annealing.
xilman is online now   Reply With Quote
Old 2021-08-30, 13:04   #14
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

23·5·157 Posts
Default

Quote:
Originally Posted by uau View Post
Proof: if you claim to have a counterexample - that is, a path between two points points which is not a circle segment and which gives a larger area than a circle segment of equivalent length for the shape formed by the path and the line between the points - then you can take a circle where the corresponding circle segment appears, and switch it with your shape, getting a solution better than a circle for a totally free shape. This proves that a circle segment is optimal, unless you believe a circle is suboptimal for a totally free shape.
Counterexamples are too easy. See attached. Green part is the enclosed field. Blue is a river. The perimeter of each area is the same length of fence when the river forms the other perimeter.
Attached Thumbnails
Click image for larger version

Name:	AreasAreHard.png
Views:	29
Size:	9.0 KB
ID:	25569  
retina is offline   Reply With Quote
Old 2021-08-30, 13:31   #15
uau
 
Jan 2017

23×3×5 Posts
Default

Quote:
Originally Posted by retina View Post
Counterexamples are too easy. See attached.
That is not a counterexample. The second image is wrong and does not have maximal area for that line length. An easy way to see that it must be wrong is that you could move the bases of the straight lines outwards, and for small changes the effect on line length is essentially 0*change (derivative is 0 while it's a right angle) while effect on area is c*change for some c>0.

You can get a larger area by placing a circle segment of suitable curvature against the river.
uau is offline   Reply With Quote
Old 2021-08-30, 14:03   #16
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

23×5×157 Posts
Default

Quote:
Originally Posted by uau View Post
You can get a larger area by placing a circle segment of suitable curvature against the river.
Now change the shape of the river into a non-straight line, say, like the lake would have.

What if the lake is really tiny? What if it is larger? What if it impinges just a little bit, or a lot. Do you always get the same result?
retina is offline   Reply With Quote
Old 2021-08-30, 14:25   #17
uau
 
Jan 2017

23·3·5 Posts
Default

Quote:
Originally Posted by retina View Post
Do you always get the same result?
You always get circle segments, that's what my proof showed. Compare this to a problem of finding the shortest path between two points that avoids obstacles. Any part of the path in free space must be a straight line - if it weren't, you could make it locally shorter by straightening it. This is similar - any part must be locally a circle segment, or you could get more area locally for the same path length. The curvature must also be the same for all the parts: if you have a pair of points somewhere with distance one and a path of length 1.2 between them, and another pair somewhere with distance also one and path of length 1.1, then you'd get more area for same total length by making both length 1.15 (which gives everything the same curvature).
uau is offline   Reply With Quote
Old 2021-08-30, 14:59   #18
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

188816 Posts
Default

Quote:
Originally Posted by uau View Post
You always get circle segments, that's what my proof showed.
I guess it is time to get explicit then.

The attached can't be maximal with a circle or a circle arc, right? The straight lines are better, right?

The point being you can't simply ignore the shape of the impinging object. What you say might be true, but is it absolutely always true for the problem as stated?
Attached Thumbnails
Click image for larger version

Name:	AlwaysConsiderTheShapeOfTheLakeCosYaJustNeverKnow.png
Views:	32
Size:	11.1 KB
ID:	25570  
retina is offline   Reply With Quote
Old 2021-08-30, 15:11   #19
uau
 
Jan 2017

1708 Posts
Default

Quote:
Originally Posted by retina View Post
The attached can't be maximal with a circle or a circle arc, right?
Not necessarily a circle arc, but all parts will be circle arcs of equal curvature. Note that I've consistently used plural. In the extreme case where the path is just long enough, you could approach straight lines.

Suppose you have an almost-complete fence with holes of length 4 and 5. If you have exactly 9 units to complete it, you'll get two straight lines. As the available length of fence increases, you start getting arcs instead, with the same curvature at both places.
uau is offline   Reply With Quote
Old 2021-08-30, 15:14   #20
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

23·5·157 Posts
Default

Okay, so what is your solution?
retina is offline   Reply With Quote
Old 2021-08-30, 17:44   #21
uau
 
Jan 2017

23·3·5 Posts
Default

For the circular lake case, I get for lake radius=1 and fence length=4:
lake sector angle for fence endpoints = 1.4362668
distance between fence endpoints = 1.3159604
fence circle radius = 0.8737708
fenced area outside lake = 1.90317905 (fence circle area = 2.3985, area of that outside endpoint line = 0.27270, additional area cut off by lake curve = 0.22265)

I didn't particularly sanity check the values, could have a simple error somewhere.

Last fiddled with by uau on 2021-08-30 at 17:45
uau is offline   Reply With Quote
Old 2021-08-30, 22:26   #22
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

215010 Posts
Default

Attached is the maximization-optimum I get using CAD and successive approximation to more than 1 m resolution.
Attached Thumbnails
Click image for larger version

Name:	EDH-100-A.jpg
Views:	45
Size:	117.5 KB
ID:	25572  
a1call is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Chernobyl -Fred Pohl kladner Reading 20 2021-03-23 17:05
Finite field extensions carpetpool Abstract Algebra & Algebraic Number Theory 3 2017-11-15 14:37
GCD of Polynomials over a finite field for NFS paul0 Programming 6 2015-01-16 15:12
Fred Flame Charges davar55 Lounge 9 2008-08-25 00:22
The Chicken farmer from Minsk Numbers Puzzles 10 2005-12-31 10:07

All times are UTC. The time now is 19:32.


Tue Oct 19 19:32:14 UTC 2021 up 88 days, 14:01, 0 users, load averages: 1.73, 1.67, 1.75

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.