wu :: forums - Print Page


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

        riddles >> hard >> Optimal Fence for Farmer Riddle
        
(Message started by: k2xl on Aug 11^th, 2014, 5:18am)

Title: Optimal Fence for Farmer Riddle
Post by k2xl on Aug 11^th, 2014, 5:18am

Riddle listed here
http://k2xl.com/wordpress/optimal-fence-riddle

Please post pictures of your shapes!

Title: Re: Optimal Fence for Farmer Riddle
Post by dudiobugtron on Aug 11^th, 2014, 5:24pm

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.)

Title: Re: Optimal Fence for Farmer Riddle
Post by rmsgrey on Aug 12^th, 2014, 8:42am

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.

Title: Re: Optimal Fence for Farmer Riddle
Post by Barukh on Aug 12^th, 2014, 9:42am

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? ???

Title: Re: Optimal Fence for Farmer Riddle
Post by towr on Aug 12^th, 2014, 10:31am

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)
[hide]sqrt(2)+sqrt(6)/2 ~= 2.639[/hide]

I should've thought of that improvement, at least.[/edit]

[edit2]Maybe I was thinking about preventing line-of-sight across a circle.[/edit2]

Title: Re: Optimal Fence for Farmer Riddle
Post by rloginunix on Aug 12^th, 2014, 10:42am

on 08/11/14 at 17:24:41, 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:

http://www.ocf.berkeley.edu/~wwu/YaBBAttachments/rlu_sqfence.png

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".

Title: Re: Optimal Fence for Farmer Riddle
Post by rmsgrey on Aug 13^th, 2014, 5:44am

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.

Title: Re: Optimal Fence for Farmer Riddle
Post by dudiobugtron on Aug 13^th, 2014, 3:27pm

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. [hide]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.[/hide]

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. ;)

Title: Re: Optimal Fence for Farmer Riddle
Post by rmsgrey on Aug 14^th, 2014, 6:58am

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...

Title: Re: Optimal Fence for Farmer Riddle
Post by Grimbal on Aug 14^th, 2014, 9:03am

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