wu :: forums
« wu :: forums - Optimal Fence for Farmer Riddle »

Welcome, Guest. Please Login or Register.
Oct 10th, 2024, 3:47am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   hard
(Moderators: Grimbal, Eigenray, Icarus, towr, william wu, ThudnBlunder, SMQ)
   Optimal Fence for Farmer Riddle
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Optimal Fence for Farmer Riddle  (Read 1999 times)
k2xl
Newbie
*






  kiggyd12345   scratchfromstart
Email

Posts: 17
Optimal Fence for Farmer Riddle  
« on: Aug 11th, 2014, 5:18am »
Quote Quote Modify Modify

Riddle listed here
http://k2xl.com/wordpress/optimal-fence-riddle
 
Please post pictures of your shapes!
IP Logged
dudiobugtron
Uberpuzzler
*****





   


Posts: 735
Re: Optimal Fence for Farmer Riddle  
« Reply #1 on: Aug 11th, 2014, 5:24pm »
Quote Quote Modify 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
*****





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2873
Re: Optimal Fence for Farmer Riddle  
« Reply #2 on: Aug 12th, 2014, 8:42am »
Quote Quote Modify 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: male
Posts: 2276
Re: Optimal Fence for Farmer Riddle   Optimal_Fence.pdf
« Reply #3 on: Aug 12th, 2014, 9:42am »
Quote Quote Modify Modify

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?  Huh
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: Optimal Fence for Farmer Riddle  
« Reply #4 on: Aug 12th, 2014, 10:31am »
Quote Quote Modify 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 Quote Modify 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
*****





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2873
Re: Optimal Fence for Farmer Riddle  
« Reply #6 on: Aug 13th, 2014, 5:44am »
Quote Quote Modify 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 Quote Modify 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. Wink
IP Logged
rmsgrey
Uberpuzzler
*****





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2873
Re: Optimal Fence for Farmer Riddle  
« Reply #8 on: Aug 14th, 2014, 6:58am »
Quote Quote Modify 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: male
Posts: 7527
Re: Optimal Fence for Farmer Riddle  
« Reply #9 on: Aug 14th, 2014, 9:03am »
Quote Quote Modify Modify

The field is used to build fences that prevent the cows to see the wrong other cows.
IP Logged
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board