[Prof. Templeton]

Prof. Templeton had purchased a 1 Km square plot of land. He was told by the Utility Company that their lines pass through his property somewhere, but they didn’t know exactly where they were and if the Prof. wanted to tap into the lines, he was responsible for paying to have them dug down to and determining where they ran through the property. All the Utility Company would tell him for certain was that the lines ran parallel to the ground and traveled in a straight line. So Prof. Templeton asked Doug the digger to come over and give him an estimate on finding the utility lines.

“The cost to dig is $1.00 per meter and I’ll have to dig around the perimeter to find those lines, so that’s four grand”, said Doug.

“I don’t think you need to do that”, said the Prof.

“You’re right. I can just dig around three sides and find those lines”, replied Doug

“You can still do better than that”, said the Prof.

What optimal digging path to find the utility lines did the Prof. have in mind and what is the least it will cost to have Doug dig?

[Guest]

a diagonal line wil find it, but not the direction

Right track?

[Prof. Templeton]

a diagonal line wil find it, but not the direction

Right track?

Not really.

If you were to dig in a diagonal line the utility lines could be 1 meter away parallel to your dig and you wouldn't find them.

[Guest]

digging diagonally in both directions though would find everything, and be slightly less than the 3000m (2828m±)

Edited September 2, 2008 by PoudreAvenger

[Prof. Templeton]

digging diagonally in both directions though would find everything, and be slightly less than the 3000m (2828m±)

We can do better still.

[Guest]

Two diagonal lines, corner to corner. Doing 1 diagonal will not find a point at all possible straight lines across the property given that the line doesn't necessarily run perpendicular to the side of the property. I could run a line from property edge to property edge and not cross the centerline. But with an X across the property, you cannot traverse 2 edges, without crossing a center X line. By then taking the point you find the wire at, dig a suitable area around it, you can discern line direction and extrapolate from there.

[HoustonHokie]

a diagonal line wil find it, but not the direction

Right track?

Right track, different location:

An inscribed diamond would find the utilities and their direction and only dig 2.82 km (2*root(2)). The same distance as diagonals both ways, but it gets the direction for a line straight through the middle of the property, which the diagonals both ways doesn't get.

Edited September 2, 2008 by HoustonHokie

[Guest]

Right track, different location:

An inscribed diamond would find the utilities and their direction and only dig 2.82 km (2*root(2)). The same distance as diagonals both ways, but it gets the direction for a line straight through the middle of the property, which the diagonals both ways doesn't get.

But again, I can cut off a corner and miss your diagonal entirely.

Edited September 2, 2008 by fish

[Prof. Templeton]

Right track, different location:

An inscribed diamond would find the utilities and their direction and only dig 2.82 km (2*root(2)). The same distance as diagonals both ways, but it gets the direction for a line straight through the middle of the property, which the diagonals both ways doesn't get.

All the Utility Company tells us is that the lines pass through the property, not how much. The lines could only cut across one corner.

[peace*out]

Is it on a grid/is there a certain length, or could it range from a centemeter to google times that??

[Guest]

He digs two corner to corner diagonal lines that cross each other at the middle. The total length will still be less than three sides, I believe.

[Prof. Templeton]

He digs two corner to corner diagonal lines that cross each other at the middle. The total length will still be less than three sides, I believe.

That would be less, but a shorter dig is still possible.

Edited September 2, 2008 by Prof. Templeton

[Guest]

Thinking it out some:

Any solution will have to reach the four corners (or else the lines might cut across the corners where the digging doesn't reach) as well as cross the entire middle of the plot. Any approach I take that starts with these principles ends with two diagonal lines... unless there is some lateral thinking involved that hasn't occurred to me yet.

[Guest]

I think I have the solution

The answer is 2.707 km

Let ABCD be the square and O be the centre.

You have to draw line AB then BC and then DO. It will find the lines.

[Guest]

aha! brilliant! Good puzzle. I came so close...and yet remained so far away

[peace*out]

I was far away the whole time!!

[Guest]

Lol I was just thinking they could dig a horizontal line across the area.

But i didn't feel like doing math so I'm sure there could be a more efficient way...

[Prof. Templeton]

I think I have the solution

The answer is 2.707 km

Let ABCD be the square and O be the centre.

You have to draw line AB then BC and then DO. It will find the lines.

The best so far! Can anyone do any better than this?

[Guest]

The best so far! Can anyone do any better than this?

*------	 *

|

|

		\

		   \

*			*

Edited September 3, 2008 by taliesin

[Guest]

I think I have the solution

The answer is 2.707 km

Let ABCD be the square and O be the centre.

You have to draw line AB then BC and then DO. It will find the lines.

Tell the guy to stop digging when he finds the line, then thanks to IMRAN, the maximum you will have to pay is $2707. But you might get lucky and find it after a few feet of trenching. Regardless, don't pay up front for unnecessary work!

[HoustonHokie]

*------	 *

|		\  

|		  \	

|		\

		   \

*			*

I thought about that exact arragement - but the line could cut off a corner and miss the trench. I added the line inside your code box to show what I mean. Edited September 3, 2008 by HoustonHokie

[Guest]

I thought about that exact arragement - but the line could cut off a corner and miss the trench. I added the line inside your code box to show what I mean.

How about

*-  ------  --*

.	   /		.

.		   \	 .

.   /			 .

.			 \   .

* . . . . . . . *

Why not something like this, with gaps.. hmm.

[Guest]

I think I have the solution

The answer is 2.707 km

Let ABCD be the square and O be the centre.

You have to draw line AB then BC and then DO. It will find the lines.

You can potentially only return a single point.. which, I'll agree that mine has the same flaw.

Are we agreeing as a community that since the trench is not going to be a single point wide, and once uncovered the line will dictate direction, or do we need to find 2 points along the cable, to mathematically define the line?

[Prof. Templeton]

You can potentially only return a single point.. which, I'll agree that mine has the same flaw.

Are we agreeing as a community that since the trench is not going to be a single point wide, and once uncovered the line will dictate direction, or do we need to find 2 points along the cable, to mathematically define the line?

We are looking for the optimal digging strategy that will discover the lines running through the property. Once the lines are discovered, we can tap into them without regard for direction. Our digging strategy has to be 100% certain of discovering the lines. Or, alternately, there may be more than one line and we have to discover them all. One solution has been posted that will discover all lines that pass through the square which will result

2,707 meters of digging

but, an optimal digging path still exists that will require even less digging and still discover all lines that pass through.

[Guest]

I'm totally stumped. I've been looking for a while, but I can't find anything better than the two adjacent sides + opposite half-diagonal. I think a hint might be in order.

[Guest]

I’ve been looking at this for a while and I think Imran has the best answer possible.

Being a landscape designer, this type of problem comes up every once in a while but the utility companies usually have a pretty decent grasp on where their lines are. If a client suggested one of the multiple broken and dotted lines solutions, I’d probably charge them twice as much per meter due to the increased labor costs of mapping the whole square kilometer off.

I better get back to work now.