Fencing without fights...
A farmer, one Mr. S, owns an uncultivated square field of green grass surrounded on all sides by pastures owned by his friends. Annoyingly for Mr. S, the cows grazing in the surrounding pastures often travel across Mr. S 's land to one of the other pastures.
Mr. S decides to stop this nonsense and considers isolating his field with a fence, but then a brainwave strikes him: "Instead of making the field impassible for these cows, what if I simply fool them into thinking it's impassible? I could build the fencing in such a way that they cannot see the other pastures and therefore won't try to walk across my field!"
At first, Mr. S considers building two fences in the shape of an 'X' across his field, which would block the view from any side of the square field to any other, thereby preventing the cows from trying to cross while saving on the amount of fencing needed.
But then he realizes that he could accomplish the same goal with even less fencing...
Can you determine the minimum amount of fencing required to block the view from any side of Mr. S's field to any of the other three sides?
This one is a big guy and carries 2.0 points!
Mr. S decides to stop this nonsense and considers isolating his field with a fence, but then a brainwave strikes him: "Instead of making the field impassible for these cows, what if I simply fool them into thinking it's impassible? I could build the fencing in such a way that they cannot see the other pastures and therefore won't try to walk across my field!"
At first, Mr. S considers building two fences in the shape of an 'X' across his field, which would block the view from any side of the square field to any other, thereby preventing the cows from trying to cross while saving on the amount of fencing needed.
But then he realizes that he could accomplish the same goal with even less fencing...
Can you determine the minimum amount of fencing required to block the view from any side of Mr. S's field to any of the other three sides?
This one is a big guy and carries 2.0 points!
posted by littlecow at 12/17/2005 09:04:00 PM
14 Comments:
arete, this solution will still allow visibility across sides. for eg, there is line of sight from the second half of side 1 to the second half of side 2.
@arete: lenscrafter is right. this problem carries 2 points for a good reason!
Assuming that the fence need not be fixed, I suggest that Mr.S anchor one end of the fence at the center of the plot, make it's length = a*sqrt(2), where a is the side of the square, and make it rotate at high speed about the center of the square. Not only will this give the optical illusion of a circular fence of radius sqrt(2) * a about the center of the square, but it will also teach a lesson to anyone venturing close to Mr.S's plot. Of course, you didn't mention anything about the cost of the motor that would rotate the damn thing, but I would imagine it has to be pretty torquey, needs some serious radial bearings, and would be rather expensive. This is not a cost-optimized solution, but an attempt to vent out my frustration after discovering that all my fixed-fence solution paths led to the X solution :(
Balakumar, thanks for inviting me to this group. I have a fencing scheme better than X. But I am not sure whether the scheme I have is the best. At any rate, the calculations I did are back of the envelope calculations. I dont know what the protocol is for posting the answers. (Please let me know or direct to me a posting exlpaining the same.). I am not posting my current approach for now, lest I spoil the puzzle-solving experience for others. But the best answer I have uses ~2.66a length of fence where a is the length of the square plot.
Arete is right, it gives (sqrt(3)+1)*a, which is 2.732a. I'm not able to get an explicit solution, but I was thinking of 4-way symmetry, if the square is ABCD, there are 4 equal length fences AP,BQ,CR and DS rotated inwards at the same angle such that PQC is collinear and so on symmetrically. There will be an additional + shaped fence in the center to prevent views across the center. My reasoning was based on viewing angles from each end of a side to the adjacent side (for the fence from the corner) and viewing angles from one end of a side towards the center. Can't prove that it is less than or equal to niranjan's soln.
@arete: you have stumbled upon a solution close to the minimum surface solution. infact, if your intersection angles were 120 degrees, it would be the best way of connecting 4 cities situated at the four corners of the square with roads. however, the present solution does not require all connections to exist. good try though!
@lenscrafter: arete's solution gave me ~2.76 which is slightly larger than the minimum surface solution of 2.732. how could PQC be collinear without Q extending atleast until the middle of the square?
@niranjan: welcome and good job on the first try! your answer looks promising. now tell me what does your fence look like?!
The fence looks like this
\ /
\___ /
|
|
|
| ___
/ \
/ \
where the slanted lines are at 45 degrees to the edges of the square. All the slanted lines are of equal length and the horizantal and vertical lines are of equal length. Assume that the slanted line is sqrt(2)*x long. Now, find the least length y of the vertical line as a function of x which impairs vision. The length of the fence needed is 4(sqrt(2)*x + y). I minimized this from x in [0:0.5]
I was kind of thinking like arnie. There is a plus at the center of the square. Additionally there are 4 fences from the vertices towards the center (part of the diagonals). The 4 slanted fences obviously don't extend upto the center of the square. The plus would be of sufficient length to block of the farms to the side.
However, I couldn't get the minimum length of such an arrangement though. I was missing a condition that has to be imposed to get some numerical solution.
Sorry about the earlier post. The figure I drew did not render properly. Let me try again
.\_../
.....|
.|.._.
./...\
This is the figure for the earlier explanation.
balaks: i meant the minimum surface solution, sorry. as for the explanation of the collinear stuff, i have sent u a mail with the drawing. can one post drawings on comments ?
niranjan: maybe i'm not visualizing correctly, but the total length of the vertical/horizontal line at the end of the 45 degree line + the 45 degree line would be longer than connecting the corner to the end of 'y' (third side of a triangle = less than sum of the other two), and the third side of this triangle would provide the same amount of visual obstruction ?
lenscrafter: I see your point and I get the feeling that you are visualizing the solution right. However, regarding the point you make, if one were to consider one horizontal line and one 45 degree line and replace them with the "third side" as tyou describe, the amount of visual obstruction is the same. But, it seems like (from rudimentary images I drew, again, on the back of an envelope) that replacing all four of such structures is not the same. Well, I am not entirely clear about this yet. And I agree with you that it would be darn convenient to be able to post images with comments.
@niranjan: you were close! but there is an even more efficient way of covering up that field!
@arni, raju, arete: your solutions stand out in its simplicity. however, the last i checked, 2.7 was still larger than 2.66. give it another shot! :-)
CLUE: The best solution I know of is 2.6389584338. The one who finds it or surpasses it gets the 2 points!
grenade, first, are u claiming to know the solutionm but giving others a chance to solve it ?
second, totally lost u on ur second-last paragraph. can u please clarify ? an infimum is the largest number smaller than a set of numbers, so isn't that like a minimum ?
@grenade: fine job! you move into the top spot. note that the points are transferable if someone comes up with a better solution.
Post a Comment
<< Home