Author 
Topic: Optimal Fence for Farmer Riddle (Read 1999 times) 

dudiobugtron
Uberpuzzler
Posts: 735


Re: Optimal Fence for Farmer Riddle
« Reply #1 on: Aug 11^{th}, 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: 2873


Re: Optimal Fence for Farmer Riddle
« Reply #2 on: Aug 12^{th}, 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 12^{th}, 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 lineofsight across a circle.[/edit2]

« Last Edit: Aug 12^{th}, 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 12^{th}, 2014, 10:42am » 
Quote Modify

on Aug 11^{th}, 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: 2873


Re: Optimal Fence for Farmer Riddle
« Reply #6 on: Aug 13^{th}, 2014, 5:44am » 
Quote Modify

The minimum fencelength which connects all 4 corners (which will obviously also block all sightlines since any sightline 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 13^{th}, 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 reallife 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 fenceposts spaced close enough together. And maybe run some number 8 wire in between them for good measure.


IP Logged 



rmsgrey
Uberpuzzler
Gender:
Posts: 2873


Re: Optimal Fence for Farmer Riddle
« Reply #8 on: Aug 14^{th}, 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 Ushape fence that allows you to move freely within the field...


IP Logged 



Grimbal
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 7527


Re: Optimal Fence for Farmer Riddle
« Reply #9 on: Aug 14^{th}, 2014, 9:03am » 
Quote Modify

The field is used to build fences that prevent the cows to see the wrong other cows.


IP Logged 



