[seqfan] Re: 100 cities to visit

[franktaw at netscape.net]

 The first thing I'm inclined to do withthis is to vary that number 100. In particular, the minimum number of cities such that such an itinerary is possible is 27. One path for 27 cities is:

8-18-1-11-12-2-22-23-3-13-14-4-24-25-5-15-16-6-26-27-7-17-10-20-21-19-9.

This has a total cost of 253. I don't know that it is optimal. With 27 cities, 8 must be at one end and 9 at the other; if 27 was dropped, 7 would also have to be at an end.

If you want a round trip, 29 cities will be required.

 

Franklin T. Adams-Watters
 

-----Original Message-----
From: Eric Angelini <Eric.Angelini at kntv.be>
 > There are 100 cities in this country.
> They are labelled "1","2","3",..."100".
> Travelling from one city to another
> is only permitted if the two cities
> share at least one digit in their label. The cost of the trip from city A to 
> city B is the absolute difference of 
> their labels.

> What is the minimal cost of a journey
> visiting all 100 cities exactly once?