Ponder This Challenge - April 2003 - Bounds on a Hamiltonian tour

Ponder This Challenge:

Update April 18: see bottom of page

Consider the disk of radius 1 in the plane. A "constellation" is a placement of N nodes arbitrarily in this disk. We describe a "Hamiltonian tour" on these nodes: start at one node, visit each of the other N-1 nodes exactly once, and finish at the starting node.

The "cost" of a single link on this tour is the _square_ of the Euclidean distance between the two nodes. (If the nodes are at distance 0.8 from each other, the cost of the link is 0.64.)

Notice that these "costs" do not satisfy the triangle inequality. So it is important that we are forbidden to visit any node twice (except the starting node, which doubles as the ending node).

The "cost" of the tour is the sum of the costs of the N individual links.

The "price" of the constellation is the smallest "cost" of any Hamiltonian tour on these N nodes.

We are interested in the largest "price" of any constellation. We are looking for upper and lower bounds on this price. That is, supply a number U and a proof that every constetllation (regardless of N) has price at most U; and supply a number L (as large as you can), and a constellation whose price is at least L. The object is to find U and L as close together as possible.

Update:
Several readers have given the inscribed equilateral triangle as evidence that L=9. Very few have given a proof of an upper bound U independent of N. Most attempted proofs have included the following argument, which I have trouble accepting: "The optimal tour cannot contain an obtuse angle ABC, because elimination of B will create a tour on N-1 nodes that is more expensive." The trouble is that this tour on N-1 nodes is not necessarily the optimal tour on those N-1 nodes; the optimal tour need not contain edge AC. So the cost of the N-1 node constellation is not necessarily larger than that of the original N node constellation.

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

  This was inspired by a result due to the Japanese mathematician Kakutani, and strengthened by Ralph Gomory (former head of IBM Research).

  L=9.
  An equilateral triangle inscribed in the circle, with vertices (1,0), (-1/2,sqrt(3)/2), (-1/2,-sqrt(3)/2) has three edges of length sqrt(3), so the cost of each link is 3, and the cost of any tour is 9.

  U=16.
  Gomory proved that the similar problem, with a unit square instead of a unit disk, has L=U=4.  Inscribe the unit disk in a square of side 2; costs quadruple when distances double, so the larger square has U=16, and the same upper bound holds for the disk.

  Gomory's proof:

  Let AC be the hypotenuse of a right triangle ABC.

  Lemma: given N nodes in ABC, there is a path starting at A, passing through each of the N nodes exactly once, and ending at C, whose cost is at most the square of the length (AC).(We will denote that as (AC)**2.)

  Proof: Construct BD perpendicular to AC with D on side AC. BD partitions ABC into two smaller right triangles. Suppose N1 nodes are in triangle ABD and the remaining N2=N-N1 points are in triangle BCD.  By induction, construct a path starting at A, passing through the N1 nodes, ending at B, with cost at most (AB)**2; and another path starting at B, passing through the N2 nodes, and ending at C, with cost at most (BC)**2. Pasting the two paths together we get a path starting at A, passing through the N nodes along with B, and ending at C, whose cost is at most (AB)**2+(BC)**2=(AC)**2.  It's illegal because it uses the extra node B.  But if E is the last node visited before B, and F is the next one visited after B, then angle EBF is acute or right, so that (EF)**2 is at most (EB)**2+(BF)**2, and replacing the two links (EB) and (BF) by the link (EF) we obtain a path whose cost is no worse, and which is legal (starts from A, passes through only the N nodes and not B, and ends at C). Start the induction with N=1, and observe that for a single interior node X, angle AXC is obtuse or right, so (AX)**2+(XC)**2 is at most (AC)**2.

  Theorem: For the square of side 2, we have U=16.

  Proof: Label the corners of the square ABCD in clockwise order. Given a constellation, temporarily append two nodes A,C at opposite corners of the square.  We can construct a path from A to C visiting all nodes in triangle ABC, with cost at most (AC)**2=8, and another from C to A visiting all the other nodes (which are in triangle CDA) with cost at most 8.  Concatenate the paths, and remove the spurious nodes A and C just as we did before, to obtain the desired Hamiltonian tour on the original N nodes with cost at most 16.

  The lower bound L=16 is obtained from the four corners of the square. Of course these corners are not in the disk, so the lower bound L=16 does not hold for the disk.  So our lower and upper bounds for the disk don't match (L=9, U=16); we're hoping a clever reader can do better than that.

Solvers

• Michael Brand (4.21.2003 @02:51:00 AM EDT)
• Sunil S Nandihalli (4.21.2003 @06:01:32 PM EDT)
• Hagen von Eit (4.23.2003 @12:54:49 AM EDT)
• zen (4.23.2003 @12:54:49 AM EDT)
• Bertram Felgenhauer (4.24.2003 @11:03:01 AM EDT)
• Dan Hoey (4.24.2003 @05:37:51 PM EDT)
• Rocke Verser (5.01.2003 @05:50:20 AM EDT)