Tuesday, July 10, 2007

Ponder this in July 2007

Ponder This Challenge: Given a square piece of property of unit side you wish to build fences so that it is impossible to see through the property, ie there is no sightline connecting two points outside the property and passing through the property that does not intersect a fence. The fences do not have to be connected and several fences can come together at a point. What is the minimum total length of fencing required and how is it arranged. For example you could place fencing along all four sides. This would have total length 4 but is not the best possible.

I do not have a proof that my answer is minimal. I will accept as correct any answer that does at least as well.

Since there is no constraint on whether the fences can be laid within the property, right now my solution is - if the fences are laid on the diagonals of the property, it prevents any line of sights from 2 points outside the property, which results in a 2.828 unit fence. I'm sure I'm missing something very obvious, but am not able to figure out what.

In the case that the fences can be laid only on the boundaries, I've not thought enough. But my instinctive answer currently is 3 units, covering 3 sides of the property. But I'm NOT going to pursue much on these lines since the constraint is imaginary.

Update: The above solution is incorrect and there is a marginally better solution to the above 'ponder this'.


Anonymous said...
This comment has been removed by a blog administrator.
oLi said...

@ Anon - I already solved it and did not want to post the right solution. May be I should update the post - sorry I did not earlier.

Thanks for pointing me to the website.

oLi said...

I deleted the post by an Anonymous since it linked to the solutions page. I don't want to spoil the fun you may have :)

### site tracker BEGIN ### site tracker END