MM Problem 1654

all at all at
Tue Mar 23 23:34:01 CET 2004


The following problem, which I found on a webpage was presumably
published in Mathematical Magazine (I guess in 2002 or 2003 - I don't
have access to MM):
Proposed by David Singmaster, London, England. A salesman's office is
located on a straight road. His N customers are all located along this
road to the east of the office, with the office of customer k at
distance k from the salesman's office. The salesman must make a driving
trip whereby he leaves the office, visits each customer exactly once,
then returns to the office. Because he makes a profit on his mileage
allowance, the salesman wants to drive as far as possible during his
trip. What is the maximum possible distance he can travel on such a trip
and how many different such trips are there? Assume that if the travel
plans call for the salesman to visit customer j immediately after he
visits customer i, then he drives directly from i to j.

This description enticed me to write a short program (as pastime during
a train journey last weekend) that looked for solutions for n<14 (which
is the largest number for which my computer can check all permutations
in a reasonable time).
The maximum possible distance the salesman can travel visiting n
customers is (starting at n=1):
2 4 8 12 18 24 32 40 50 60 72 84 98 112
If we divide this by 2, we get   a(n)=A002620(n-1)
Quarter-squares: floor(n/2)*ceiling(n/2). Equivalently, floor(n^2/4).

A002620 contains an overwhelming number of comments. Can anybody point
out if one of those comments already describes the "maximum possible sum
of absolute differences between successive elements in a permutation of
1..n starting from and returning to 0" problem?

The solution to the second questions seems to be not in the OEIS:

Number of different trips of maximum possible distance, counting a trip
and its reversal as one (e.g. 0-1-2-0, 0-2-1-0 -> 1 trip), starting at
1 1 4 6 36 72 576 1440 14400 43200 518400 1814400 25401600
Example: a(4)=4: Trips of maximum lenght=12
0,2,3,1,4,0; 0,2,4,1,3,0; 0,3,1,2,4,0; 0,3,2,1,4,0 and their reversals.

Is there a known formula for this sequence, e.g. from the published
solution of the MM problem?

Hugo Pfoertner

More information about the SeqFan mailing list