Author |
Topic: Optimal Fence for Farmer Riddle (Read 1987 times) |
|
dudiobugtron
Uberpuzzler
Posts: 735
|
 |
Re: Optimal Fence for Farmer Riddle
« Reply #1 on: Aug 11th, 2014, 5:24pm » |
 Quote  Modify
|
I can't find a more optimum shape than the one proposed. I haven't really tried to prove it though, since I guess there is one. (otherwise they wouldn't have given it to you.)
|
|
 IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender: 
Posts: 2872
|
|
Re: Optimal Fence for Farmer Riddle
« Reply #2 on: Aug 12th, 2014, 8:42am » |
Quote Modify
|
There should be another thread on this question somewhere - though I'm not sure what search terms would get you there.
If each side of the field has length 1, then the given solution has length 2.828 or so. The best solution has total fence length less than e.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
It's indeed not trivial to find the other thread.
A solution found by a friend of mine. Is it the solution? How to prove it? 
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Optimal Fence for Farmer Riddle
« Reply #4 on: Aug 12th, 2014, 10:31am » |
Quote Modify
|
If memory serves me right the solution has a great many separate lines/points.
[edit]Hmm, well, I dunno about my memory, but here's a better solution in any case: http://cccg.ca/proceedings/2008/paper45.pdf (figure 4)
sqrt(2)+sqrt(6)/2 ~= 2.639
I should've thought of that improvement, at least.[/edit]
[edit2]Maybe I was thinking about preventing line-of-sight across a circle.[/edit2]
|
| « Last Edit: Aug 12th, 2014, 10:51am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Optimal Fence for Farmer Riddle
« Reply #5 on: Aug 12th, 2014, 10:42am » |
Quote Modify
|
on Aug 11th, 2014, 5:24pm, dudiobugtron wrote:| I can't find a more optimum shape than the one proposed. |
|
It's relatively easy to improve on 2*sqrt(2). I'm still busy with SWF's tessellations so I gave this problem to my son. His idea was:
Length(x) = 4*sqrt(1/4 + x^2) + 1 - 2*x
It's first derivative is L'(x) = (4*x)/sqrt(1/4 + x^2) - 2
Equate it to zero and all that. x(m) = 1/sqrt(12) minimizes it. L(x(m)) = 2.732050807 < 2.828427125.
His questions, however, were 1). is it the true minimum (obviously not) and 2). what is the analytic solution since the above improvement was just a "what if".
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2872
|
|
Re: Optimal Fence for Farmer Riddle
« Reply #6 on: Aug 13th, 2014, 5:44am » |
Quote Modify
|
The minimum fence-length which connects all 4 corners (which will obviously also block all sight-lines since any sight-line that passes through the square must separate at least one pair of corners) is the Steiner Tree - which is known to be the graph found by rlogunix.
According to Wikipedia, the Opaque Forest Problem is an open problem - the best known lower bound for a unit square is 2, though apparently 2+10-5 has been claimed but the proof had yet to be reviewed at the time that part was edited into Wikipedia.
|
|
IP Logged |
|
|
|
dudiobugtron
Uberpuzzler
Posts: 735
|
|
Re: Optimal Fence for Farmer Riddle
« Reply #7 on: Aug 13th, 2014, 3:27pm » |
Quote Modify
|
Although not a solution to the Opaque Forest Problem, here are some more fun solutions to the OP's problem:
One solution that uses less fence is to obscure the cows' view using something other than fence. For example, you could use plants, or walls, or build some dirt or hay mounds. Or, if you're interested in using minimal material, you could put eye patches over the cows' eyes. These solutions all use no fence, and so are optimal. Unless you consider negative fence length used to be more optimal - in which case you should use a fence factory to obscure the cows' views.
Another real-life solution to the problem which uses less fence is to build fence sections around the perimeter of your field, with numerous small gaps in between. As long as the gaps are too small to allow a cow to pass through, then it doesn't really matter if the cows can see each other, does it?
Mathematically, you could approach zero fence length using this solution. It's a practical solution though (since the mathematical cows probably have zero width), so you're probably best off by just using fence-posts spaced close enough together. And maybe run some number 8 wire in between them for good measure. 
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2872
|
|
Re: Optimal Fence for Farmer Riddle
« Reply #8 on: Aug 14th, 2014, 6:58am » |
Quote Modify
|
If you want practical considerations, there's also the question of what you use the field for - you may well be better off with a simple U-shape fence that allows you to move freely within the field...
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7526
|
|
Re: Optimal Fence for Farmer Riddle
« Reply #9 on: Aug 14th, 2014, 9:03am » |
Quote Modify
|
The field is used to build fences that prevent the cows to see the wrong other cows.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Optimal_Fence.pdf