August 2004
<<July August September>>
ANSWER:
Part 1:
The longest path is sqrt(N) miles.
Proof by induction:
It is clearly true for N=1, since with one straight line, you have no choice but to walk straight from A to B.
Let's denote by p(0), p(1), ... p(N) the endpoints of our journey-lines, so that p(0) = A, and p(N) = B. In other words, we always walk in a straight line from p(i) to p(i+1). Then we first show that the lines (A, p(1)) and (p(1), B) are perpendicular. To see this, consider the disk defined by (A,B) as a diameter (i.e. the center is the midpoint of (A,B) and the radius is a half-mile). Then placing p(1) anywhere outside this disk would violate the "decreasing distance" rule. Thus p(1) must be in the disk. But if we place p(1) in the interior of the disk, we can consider the point p'(1) which is the projection of p(1) onto the circumference away from (and perpendicular to) the diameter (A,B), and since this is strictly further away from both A and B, the total route distance is also made strictly larger by replacing p(1) with p'(1). Thus p(1) is on the circumference, so (A, p(1)) is perpendicular to (p(1), B).
Let x be the distance from A to p(1) and y be the distance from p(1) to B. So x^2 + y^2 = 1. ("x^2" means x squared.) The total distance of the route is, by the induction step, x + y*sqrt(N-1). This distance is at most sqrt(N): the dot product of the vector (x,y) of length 1 and the vector (1,sqrt(N-1)) of length sqrt(N) is a most 1*sqrt(N), and this is achieved when x=1/sqrt(N) and y=sqrt((N-1)/N).
An interesting note is that since the line from A to p(1) is 1/N of the total route length, this means that all lines that comprise the route are of equal length, which isn't immediately obvious. Joe Riel and John Fletcher independently sent in the following explanation: Let x(i) be the vector representing the (N-i+1)th step and |x(i)| its length, and let * represent the dot product. The total distance is 1, so that [x(1)+...+x(N)]*[x(1)+...+x(N)]=1. We know x(i) is orthogonal to x(1)+x(2)+...+x(i-1), so that x(i)*[x(1)+...+x(i-1)]=0. Substituting that in, our equation becomes [x(1)*x(1)] + [x(2)*x(2)] + ... + [x(N)*x(N)] = 1. So we are trying to maximize the sum of |x(i)|, subject to the sum of |x(i)|^2=1. This happens when all |x(i)| are equal, at 1/sqrt(N).
Part 2:
The "turning left" condition forces a counter-clockwise spiral, rather than a zigzag or clockwise spiral. In other words, the path takes us around the house to the east, and then to the north. The "walking north-east" condition means that p(N-1) lies somewhere to the south-west of the house, so that we've traveled at least 3*pi/2 radians (=270 degrees) around the house. From part 1, we see that when walking an optimal path, the angle we go around the house in path k is arctan(1/sqrt(N-k)) - with the exception of the final path N, which of course doesn't add anything to the angular distance around the house. Therefore the total angular distance around the house can be calculated by looking at the paths in reverse order to get sum(i=1,...,N-1) arctan(1/sqrt(i)). We find N=12 as the smallest possible value: sum(n=1,...,11) arctan(1/sqrt(n))=4.81833=1.53372*pi.
Part 3:
Use rectangular coordinates, so that A=p(0)=(1,0), B=p(3)=(0,0). p(2)=(0,C), because the last leg heads south. By reasoning similar to part 1, we can show that the second leg is perpendicular to the third (so that p(1)=(D,C)), and that the first leg is perpendicular to the sum of the last two, so that C^2 + D^2 - D = 0. Subject to those conditions, we wish to maximize the length of the path, namely C + D + sqrt((1-D)^2+C^2). Substituting C=sqrt(D-D^2), we want to maximize sqrt(D-D^2) + D + sqrt(1-D). Standard calculus gives D=0.6017008128 as a root of 1 - 17D + 64D^2 - 64D^3 = 0, and C=0.489547694, with the total length of 1.722357996.
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com