[seqfan] 100 cities to visit

[Eric Angelini]

> 
> 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?
> 
> Here is a minimal journey un which
> one _has_ to visit cities 1, 2, and 3
> (the visiting order is not important):
> 2-12-1-13-3 with cost 43.
> 
> If we add city 4, the minimal cost 
> rises to 83 (I'm not sure this is
> minimal, though):
> 1-12-2-23-3-13-14-4
> 
> Note that the cost is the same
> for a longer journey meeting the
> minimal spending requirement:
> 1-12-2-20-21-22-23-3-13-14-4
> 
> Hope this is not old hat,
> Best,
> E.
> 
> 
>