wu :: forums « wu :: forums - Optimal Fence for Farmer Riddle » Welcome, Guest. Please Login or Register. Dec 2nd, 2021, 4:59pm RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    hard (Moderators: Icarus, Grimbal, SMQ, ThudnBlunder, william wu, towr, Eigenray)    Optimal Fence for Farmer Riddle « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: Optimal Fence for Farmer Riddle  (Read 1885 times)
k2xl
Newbie

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

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

 IP Logged
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: 2844
 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
 Re: Optimal Fence for Farmer Riddle   Optimal_Fence.pdf « Reply #3 on: Aug 12th, 2014, 9:42am » Quote 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?
 IP Logged
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13729
 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.

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
Uberpuzzler

Posts: 1026
 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: 2844
 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: 2844
 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: 7517
 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
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium => hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »