# The Farmyard problem

Problem:

There is a farmer who has a $1\text{ mile}\times 1\text{ mile}$ square piece of land. He knows that there is a completely straight pipe underneath some part of his property, but it could be going in any direction. He wants to dig some ditches to find it. He knows that if he digs all around the property we will find it, but that requires 4 miles of digging! What choice of lines minimizes the amount of required digging, and what is that minimum amount?

Just three lines around the perimeter will suffice, cutting the digging down to only 3 miles. After more thought one sees that only 2 diagonal lines are needed, which is 2.82 miles of digging.

I don't think coming up with examples is that hard, it's just that proving it seems impossible. At the moment I found something with length $\sqrt{2}+\sqrt{3/2}$ but I just can't prove it is optimal. It is worth noting that the lines can be disconnected, and can have finitely many pieces. The solution I had above was made up of two different pieces.

Any help is greatly appreciated!

-
Go to the county register and ask to see the archival copy of the utility company's RoW easement? –  Henning Makholm Sep 21 '11 at 22:15
Less whimsically, my intuition is that the mininum will be a Steiner tree connecting the four corners. –  Henning Makholm Sep 21 '11 at 22:17
I'm positive I've seen this very question on math.SE before, but I can't find it now. As I recall, someone linked to a paper that addressed generalizations of this problem to regular polygons; the optimal solution for the square was the union of a Steiner tree on three corners with a perpendicular dropped from the fourth to the diagonal. –  Rahul Sep 21 '11 at 22:22
susqu.edu/brakke/opaque/opaqsq.html gives the solution Rahul gave, but says it hasn't been proved optimal. See also Asimov and Gerver, Minimum opaque manifolds, Geometriae Dedicata 133 (2008) 67-82. Maybe the best reference is arxiv.org/pdf/1005.2218.pdf –  Gerry Myerson Jan 27 '12 at 12:18
@GerryMyerson: I think you should post the arxiv paper as an answer, because it seems to be the best known result and says of the $\sqrt{2} + \sqrt{3/2}$ solution that "The shortest barrier known for the square, of length 2.639... is conjectured to be optimal. The current best lower bound is 2, established by Jones [24]." –  ShreevatsaR May 16 '12 at 8:26
show 11 more comments

Reposting from the comments so this question will have an answer:

This problem appears to be unsolved. This paper (dated 1/25/2012) provides an example with total length $\sqrt{2}+\frac{\sqrt{6}}{2} = 2.638958433764...$ which is conjectured to be optimal. I believe this uses a Steiner tree to connect 3 vertices of the square and then a diagonal line from the 4th vertex to the center of the square. Quoting:

The diagonal segment $[(\frac{1}{2}, \frac{1}{2}),(1, 1)]$ together with three segments connecting the corners $(0,1), (0,0), (1,0)$ to the ￼￼point $(\frac{1}{2}−\frac{\sqrt{3}}{6},\frac{1}{2}−\frac{\sqrt{3}}{6})$ yield a barrier of length $\sqrt{2}+\frac{\sqrt{6}}{2}$ =2.639

This is illustrated by this drawing derived from http://www.susqu.edu/brakke/opaque/opaqsq.html

The paper R.E.D. Jones, Opaque sets of degree α, American Mathematical Monthly, May 1964, p. 535-537, establishes a lower bound of 2.

-