19
$\begingroup$

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!

  • 4
    Go to the county register and ask to see the archival copy of the utility company's RoW easement?2011-09-21
  • 0
    Less whimsically, my intuition is that the mininum will be a [Steiner tree](http://en.wikipedia.org/wiki/Steiner_tree_problem) connecting the four corners.2011-09-21
  • 1
    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.2011-09-21
  • 0
    @Henning: That is very good idea! Keep in might though that we are allowed to use disconnected lines. The idea I have right now is one line from corner 1 directly to the center. Then connected the other three corners, but having the point where the meet up to be as far away from corner 1 as possible. (I used some calculus to find the maximum) What I got was $\sqrt{2}+\sqrt{3/2}$2011-09-21
  • 0
    Yes, the full Steiner tree is a bit longer than your solution (assuming that your calculation of its length is correct). So unfortunately it can't be used to argue optimality.2011-09-21
  • 0
    Your solution is the one that @Rahul mentioned.2011-09-21
  • 0
    If I'm not mistaken, this is equivalent to a problem I heard put this way: Find a minimal-total-length set of lines that is "as good as" a solid square with regard to blocking lines-of-sight. (In OP's scenario, the pipe takes the place of an arbitrary line-of-sight.) I *think* the problem was still open when I heard about it, but this was 20 years ago. Anyway, this re-phrasing of the problem may help with reference searches.2012-01-27
  • 0
    My hypothesis is the length is zero. Suppose you order all points in the square that have rational coordinates, and then dig lines centered at each of these rational points with length $\frac{\epsilon}{2^k}$, in random directions. The total line length cut is $\epsilon$, but intuitively it seems very unlikely that any line could pass through this square undetected. My guess is that this can be proved rigorously with the probabilistic method though I'm not sure and the details aren't immediately obvious.2012-01-27
  • 1
    http://www.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 http://arxiv.org/pdf/1005.2218.pdf2012-01-27
  • 0
    It's possible I imagined "optimal" where the hazily-remembered paper said "best known". Sorry for the misinformation.2012-01-27
  • 0
    @Nick, the paper referenced at the end of Gerry's comment has a proof that $2$ is a lower bound. In particular, your scheme does not work because if the total length of your segments is $\epsilon < 1$, you cannot even cover the whole width of the square, so there is some vertical line that will pass through undetected.2012-01-27
  • 0
    @Rahul, ahh, you're right my approach doesn't work. Thanks for the response.2012-01-28
  • 0
    I feel I need more information. How about the length of the straight pipe?2012-05-14
  • 0
    It's infinite. The length that's actually under the farmer's land is unknown. (Imagine a straight line that intersects a square.)2012-05-14
  • 1
    @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]."2012-05-16
  • 0
    @ShreevatsaR, will do, tomorrow, if I can.2012-05-16

2 Answers 2