# Ernie and the Grand Tour

It had sounded like a great idea at the time. Ernie had been gifted a travel package for himself plus eight companions (he chose to bring along seven friends from his Wine Club, plus me) by the President of Lighter Than Air Tours - which was using his artificial spider silk technology in their modern take on airship travel. "21st Century Zeppelins!" the advertising blurb had exclaimed, "All the benefits of a 4 star Hotel combined with the convenience of safe and rapid air travel". "!!!Nine Cities in Nine Days!!!" - it had promised.

The plan was that the air-ship would pick us all up from a central location and then, over nine nights, fly us to nine "Exciting and Adventurous Destinations". We would arrive at each location at dawn - spend the day "Exploring the Delights of the Environs" - then re-board the airship to be "Whisked Overnight, in Luxurious Comfort along the most direct great circle path" to the next destination. At the end of the tour we would all be returned to the starting-point. And the list of destinations (provided in alphabetical order) had sounded rather interesting...

 In no particular order, you will visit the delights of:
Aksaray, Turkey
Denver, USA
Germiston, South Africa
Ilheus, Brazil
Moriguchi, Japan
Odessa, Ukraine
Perth, Australia
Toulouse, France
Warangal, India


...especially as some of the places appeared a little off the track for normal tourist travel.

After pick-up we were shown our (rather luxurious) individual cabin rooms (each with a "Port-hole View of the Skies"), given a quick itinerary (the order that we would visit the cities), then informed that each night, because we were special guests, there would be bottomless complimentary Champagne for all.

Unfortunately, the combination of high-altitude air-ship travel, jet-lag and (to be honest) far too much free alcohol left us feeling more than a little under the weather. On one morning the following conversation took place around the breakfast table (shortly before we were to arrive at our next destination).

"Oh my God", said George, who looked a little fragile after the drinking races the night before, "I can't remember where we were yesterday, where we are going today, the order in which we were to visit the cities or, for that matter, how many days we have been travelling". The rest of us, also regretting the night before's excesses, all made similar comments.

"The only thing I remember", said Marg, "is that in the ordered sequence of cities, no more than three formed an alphabetically increasing sub-sequence (based on the first letters of the city's names)".

"Are you sure of that?", replied Jeff. "My memory is that in the same ordered sequence, no more than three formed an alphabetically increasing sub-sequence (based on the last letters of the city's names)".

"That can't be right!", exclaimed Harriet. "I'm positive that no more than three cities formed an alphabetically decreasing sub-sequence ((based on the first letters of the city's names)".

"You are all miss-remembering, exclaimed Wilbur. "No more than three cities formed an alphabetically decreasing sub-sequence (based on the last letters of the city's names)".

"Well you can't all be right", said the always argumentative Fred with a grimace.

"But what if you are...?", continued Dorothy, who hated conflict.

"Well, even if you are all correct in your recollections", said Ernie, "there still isn't enough information to determine the correctly ordered sequence of cities. Does anyone else have more information?".

At that point I remembered a conversation I had with the Second Officer, when we were dining at the Captain's Table the previous night (before the drinking races began). "I was told", I explained, "that the combined flying distance between the first and second cities and the second and third cities, was 'substantially' less than the combined flying distance between the seventh and eighth cities and the eighth and ninth cities. And furthermore", I continued "last night's flight was to be the shortest 'inter-city' flight on the whole tour".

"In that case, - assuming all your recollections are correct - the order is obvious...", retorted Ernie, "...and in a few minutes we should be arriving at the city of ...".

But at that very moment Ernie's voice was drowned out by the airship's intercom announcing our destination for the morning and also the ordered list of cities visited so far and still to visit. After that, Ernie still asserted that he had already worked out the itinerary from the clues provided but none of us were convinced. Can anyone help me. Is it possible to calculate the itinerary or was he just guessing?

• Note that a sub-sequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements (as described, for example, in en.wikipedia.org/wiki/Subsequence). Note that Ernie's final comment relies not only on the distance information but also in the premise that the four 'sub-sequence' memories are also correct. – Penguino Oct 5 '15 at 22:24
• So note the clarification added in Ernie's last statement. – Penguino Oct 5 '15 at 22:29

With the updated definition of subsequence there are still multiple solutions. The shortest is:

Germiston, Toulouse, Denver, Odessa, Aksaray, Warangal, Ilheus, Perth, Moriguchi

The distances between the cities are (in $m$):

8229026, 8168594, 9463389, 939396, 4941708, 13487561, 14170226, 7696249

This gives a ratio of about $1.33$ between the sums of both last and both first distances, with a total distance of $67,096,149 m$.

• For your first solution, "Aksaray, Warangal, Moriguchi" forms a decreasing subsequence by last letter and also "Ilheus, Germiston, Perth" does. It's true that each sequence is only three cities, but it is more than three cities total. I guess it depends on how to interpret "no more than three" in Wilbur's statement. – Daphne B Oct 5 '15 at 17:32
• The first solution fails in that (among other things) the sequence [Toulouse, Odessa, Aksaray, Warangal, Moriguchi, Denver, Ilheus, Germiston, Perth] contains a four element sub-sequence [Aksaray, Denver, Germiston, Perth] which is alphabetically increasing (based on the first letters of the city's names) - so doesn't match Marg's recollection. The second solution fails for a similar reason. – Penguino Oct 5 '15 at 22:34
• Why is this downvoted? – Sleafar Oct 7 '15 at 17:12
• A correct answer Sleafar (although not what I had expected), The multiple solutions is my fault. I designed the problem to only have two solutions after the 'sub-sequence' statements, then the distance comments would choose the valid one (and where in it the air-ship was). Unfortunately I made a one-off error in transliterating a table - so produced the wrong set of city names. ...and compounded thatby not resolving with the names I used.. – Penguino Oct 13 '15 at 20:05