Ponder This Challenge - August 2004 - Longest way to come home

Ponder This Challenge:

Puzzle for August 2004.

This month's puzzle comes from Joe Fendel, who writes:

Here's a puzzle I remember coming up with in high school. It was inspired by a request made one day that I come home immediately to do my chores, whereupon I would start walking home at a constant pace (I wasn't one to disobey), but I would try to find the longest possible route home (so as to put off doing my chores). Of course, I couldn't really walk in the opposite direction and claim to be "walking home." So I thought of the following problem:

Part 1:
Points A and B are on a plane surface, 1 mile apart. Suppose you must walk in a path consisting of N straight lines from point A to point B, such that at all times your (Euclidean) distance to point B is decreasing. What is the longest possible route length (as a function of N)?

Part 2:
Suppose the house is due north of the starting point, and on the way home, I always turn left (by less than 180 degrees). I still take a longest path according to the rules of Part 1. On the last leg of this longest path, I'm walking both northward and eastward (mostly eastward). What's the smallest possible value of N?

And of course your puzzlemaster has to add a "Part 3":
Suppose that in the setup of part 1, we have N=3; point A is 1 mile due east of point B; and the path is subject to the additional constraint that the last (third) line must be directed due south. Now what is the longest possible route?

Correct answers to all parts must be given.

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solution

• Click here to view the solution

  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

Solvers

• Tomas G. Rokicki (8.02.2004 @02:38:26 PM EDT)
• Patrick J. LoPresti (8.02.2004 @03:20:00 PM EDT)
• Colin Bell (8.02.2004 @07:44:32 PM EDT)
• Alex Naverniouk and I (8.03.2004 @01:40:20 AM EDT)
• gor Naverniouk (8.03.2004 @01:40:20 AM EDT)
• Abhiman Chatra (8.03.2004 @04:29:00 AM EDT)
• Vincent Vermaut (8.03.2004 @10:29:00 AM EDT)
• Gaurav Agarwal (8.03.2004 @10:37:27 AM EDT)
• Jose H. Nieto (8.03.2004 @10:39:00 AM EDT)
• Hagen von Eitzen (8.03.2004 @12:05:51 PM EDT)
• Dan Dima (8.03.2004 @12:53:05 PM EDT)
• Kalyana Cha (8.03.2004 @01:31:00 PM EDT)
• kravarthy (8.03.2004 @01:31:00 PM EDT)
• Joseph DeVincentis (8.04.2004 @12:08:24 AM EDT)
• Hao Wu (8.04.2004 @12:30:55 AM EDT)
• Li Jian (8.04.2004 @06:23:14 AM EDT)
• Kevin Kenny (8.04.2004 @09:13:31 AM EDT)
• C (8.04.2004 @09:35:00 AM EDT)
• hris Hills (8.04.2004 @09:35:00 AM EDT)
• Zaiyong Yang (8.04.2004 @11:30:00 AM EDT)
• Jonathan Derryberry (8.04.2004 @12:59:03 PM EDT)
• Karl D. Souz (8.04.2004 @02:41:31 PM EDT)
• Prakash Chandra (8.04.2004 @03:17:34 PM EDT)
• Gyozo Nagy (8.04.2004 @05:08:24 PM EDT)
• Bhaskara Aditya (8.05.2004 @12:29:49 AM EDT)
• Jayavel Sounderpandian (8.05.2004 @06:51:48 AM EDT)
• aman_cc (8.05.2004 @12:25:13 PM EDT)
• Vince Lynch (8.05.2004 @01:23:00 PM EDT)
• Narayanan Rajamani (8.05.2004 @10:53:43 PM EDT)
• Alan O'Donnell (8.06.2004 @06:39:00 AM EDT)
• J. Lewandowski (8.06.2004 @11:57:24 AM EDT)
• Chris Shannon (8.06.2004 @02:56:00 PM EDT)
• Sedong Kwonyeon Kimyu (8.07.2004 @11:20:12 AM EDT)
• Dr. John G. (8.08.2004 @06:51:59 PM EDT)
• Fletcher (8.08.2004 @06:51:59 PM EDT)
• Mayank M Kabra (8.09.2004 @02:57:22 AM EDT)
• David McQuillan (8.09.2004 @05:21:30 PM EDT)
• Guler Amos (8.10.2004 @10:01:24 AM EDT)
• Ari (8.10.2004 @10:29:00 AM EDT)
• Siva Dirisala (8.10.2004 @03:16:28 PM EDT)
• Don Rice (8.10.2004 @06:00:00 PM EDT)
• Michael Mendelsohn (8.10.2004 @06:37:00 PM EDT)
• Jean-Pierre Battaille (8.11.2004 @12:42:08 AM EDT)
• Maria Rodionova (8.11.2004 @06:05:00 AM EDT)
• Nathaniel Litton (8.11.2004 @07:46:31 AM EDT)
• John Ritson (8.11.2004 @08:15:52 AM EDT)
• Dharmadeep Muppalla (8.11.2004 @09:22:28 AM EDT)
• Nachiket Bapat (8.11.2004 @07:15:39 PM EDT)
• Victor Chang (8.12.2004 @03:27:44 AM EDT)
• Clive Tong (8.12.2004 @12:41:08 PM EDT)
• Libin Shen (8.12.2004 @02:40:00 PM EDT)
• Nicholas Kleszczewski (8.12.2004 @04:40:00 PM EDT)
• Steve Powell (8.13.2004 @10:26:01 AM EDT)
• Kim (8.13.2004 @10:32:06 AM EDT)
• Jinhong (8.13.2004 @10:32:06 AM EDT)
• Joe Riel (8.13.2004 @09:09:48 PM EDT)
• Frank Mullin (8.15.2004 @10:39:45 AM EDT)
• Renaud Bauvin (8.18.2004 @01:24:45 PM EDT)
• Bill Webb (8.18.2004 @06:06:21 PM EDT)
• Markus Nauroth (8.21.2004 @05:09:26 PM EDT)
• Jimmy He (8.22.2004 @02:56:36 PM EDT)
• Irem Koprulu and Atilla Eryilmaz (8.22.2004 @08:20:54 PM EDT)
• Dion K Harmon (8.25.2004 @10:49:00 AM EDT)
• Avnish Miduthuri (8.25.2004 @02:35:00 PM EDT)
• Atif Hussain (8.26.2004 @02:10:42 AM EDT)
• Daniel Bitin (8.26.2004 @04:02:05 AM EDT)
• Raicho Tchalkov (8.26.2004 @06:41:28 AM EDT)
• R. Nandakumar (8.26.2004 @10:33:50 AM EDT)
• Divyesh Dixit (8.26.2004 @11:19:31 AM EDT)
• Blake Eastman (8.26.2004 @03:26:33 PM EDT)
• Renato Fonseca (8.27.2004 @10:21:49 PM EDT)
• Ariel Flat (8.29.2004 @06:22:44 AM EDT)
• Fabio Negroni (8.29.2004 @06:29:09 PM EDT)
• Vedpal Singh (8.30.2004 @02:52:54 AM EDT)
• Paul Botham (8.30.2004 @12:56:23 PM EDT)
• Wolfgang Kais (8.31.2004 @02:48:35 AM EDT)
• Andy Lowry (8.31.2004 @03:08:48 PM EDT)
• Forrest Mcclellan (8.31.2004 @06:23:06 PM EDT)