In the Eternal Forest, the trees are perfectly circular, each having a diameter of exactly one meter. They are arranged in a flat, infinite rectangular grid. The center of each tree is ten meters away from the centers of each of its closest neighbors.

There are many paths through the Eternal Forest. Each path is infinite in length, constant in width, and perfectly straight. Trees don't grow on the paths, but every path will have tree trunks touching it on either side.

What is the narrowest possible path through the Eternal Forest?

I am going on the assumption that more than one tree trunk must touch either side. If you have only one touching each side, for example, the limit approaches a length of 1/��. 

It looks like there is a limit that is nonzero, however. The fact that each tree trunk has a width affects the calculations. This is easy enough to visualize, and I think Jer has the right idea.

Consider some point (0,0) in the grid. If you take the tree trunk directly next to it and vertically offset by one (1,1), you get a path. If you take instead the one next to it (2,1) you get a narrower path. Based on points, you can do this indefinitely. Basically, you make a road with the points (0,0) and (1,0) as starting points and the points (1,n) and (1,n+1) as the directional points. By definition, each 'road' line goes through the center of the tree trunks. Once the difference between the centers drops below 1, you cannot make it through on a straight line.

I'm going to agree with Jer that the solution is 0.104315. This I worked out in an Excel spreadsheet based on a triangle with legs of ((n*10),(10/n)). The area of this triangle and the Pythagorean Theorem can be used to get the height, or the width of the paths between the trees' centers. You subtract 1, since the radius of each tree is 0.5 and by definition you need to avoid each tree. At a slope of (1/9) you reach the minimum, and at (1/10) you will hit a tree.

Edited on May 26, 2005, 9:12 pm

Edited on May 26, 2005, 9:13 pm

Posted by Eric on 2005-05-26 21:01:25