[seqfan] 100 cities to visit
Eric.Angelini at kntv.be
Tue Aug 16 01:11:34 CEST 2011
> 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):
> Note that the cost is the same
> for a longer journey meeting the
> minimal spending requirement:
> Hope this is not old hat,
More information about the SeqFan