April 2003
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
Challenge:
04/01/2003 @ 10:00 AM EST
Solution:
04/01/2003 @ 10:00 AM EST
List Updated:
04/01/2003 @ 10:00 AM EST
People who answered correctly:
Michael Brand (4.21.2003 @02:51:00 AM EDT)
Sunil S Nandihalli (4.21.2003 @06:01:32 PM EDT)
Hagen von Eitzen (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)
Attention: If your name is posted here and you wish it removed please send email to the ponder@il.ibm.com.