### Random Post

### Recent Posts

### Recent Comments

### Archives

### Categories

- article (11)
- enigma (1,149)
- misc (2)
- project euler (2)
- puzzle (38)
- site news (44)
- tantalizer (40)
- teaser (3)

### Site Stats

- 175,242 hits

Advertisements

Programming Enigma Puzzles

19 January 2018

Posted by on **From New Scientist #1582, 15th October 1987** [link]

Alan and Susan recently spent eight days among the six Oa-Oa islands, which are shown on the map as Os.

Only two of the islands, Moa-Moa and Noa-Noa, have names and hotels. The lines indicate the routes of the four arlines: Airways, Byair, Smoothflight and Transocean.

Alan and Susan started their holiday on the morning of the first day on Moa-Moa or Noa-Noa. On each of the eight days they would fly out to an unnamed island in the morning and then on to a named island in the afternoon and spend the night on that island. They each had eight airline tickets and each ticket was a single one-island-to-the next journey for two passengers. Alan had two Airways and six Byair tickets, while Susan had three Smoothflight and five Transocean tickets. They noticed that whatever island they were on, only one of them would have tickets for the flights out and so they agreed that, each time, that person should choose which airline to use.

Now Alan preferred that they should spend the nights on Moa-Moa, while Susan preferred Noa-Noa. However, they are an inseparable couple. So they each worked out the best strategy for the use of their tickets in order to spend the maximum number of nights on their favourite island.

How many nights did they spend on each island?

[enigma432]

Advertisements

%d bloggers like this:

The puzzle has been carefully constructed so that at each island only one person holds possible onward tickets. So, (numbering the unnamed islands 1, 2, 3, 4 from left to right) Alan makes the choice at islands M, 2, 3, and Susan makes the choice at N, 1, 4.

This Python program computes example itineraries where both players are seeking to maximise their respective goals. It runs in 237 ms.

Run:[ @repl.it ]Solution:They spent 5 nights on Moa-Moa and 3 nights on Noa-Noa.A possible itinerary starting on M is:

And starting on N:

They only differ on day 1, but both itineraries end up on M at the end of day 1.

I augmented my program to find all possible maximal itineraries, and I found there are 246 starting on M and 136 starting on N (giving 382 in total). But they all involve spending 5 nights on Moa-Moa and 3 nights on Noa-Noa.

There are only two which have 2 day visits to each of the unnamed islands, they both start from N:

@Jim I am getting different answers here but I could be misunderstanding how you define ‘maximal itineraries’. This could mean that all islands are visited at least once or that all twelve airline routes are used at least once (or both). Or something else maybe?

@Brian: I’m talking about the number of different itineraries that could be outcomes of the situation described in the puzzle (where each person is seeking to maximise the number of nights spent of their preferred island, by making the appropriate ticket choice). I found 382 different itineraries (destination islands and ticket orders).

There may be a bug in this code that is giving erroneous itineraries but I found 36 paths covering all islands at least twice with (M, N) = (5, 3):

@Brian: But would all these show up as itineraries in a game where each player is playing optimally?

For instance, your code outputs itineraries that start “1: N (S) 2 (B) N”, but my tests indicate that if we started on island N and Susan choose to fly to island 2 (via S), then Alan would choose to fly to island M (via A), and in the end they would have stayed 6 nights on M and only 2 nights on N. But if Susan chooses to fly to island 3 (via T), then they would end up staying 5 nights on M and 3 nights on N, which is what Susan would prefer, and as she’s making the choice at N this is what would happen.

It looks like Susan is better off not using S to fly to island 2 until Alan has used up both his A tickets, and then he is forced to fly them back to N on a B ticket.

It feels like I really ought to know more about Game Theory to get a proper understanding of this kind of puzzle.

There’s a book that I first encountered at school some 55 years ago:

The Compleat Strategyst, being a primer on the theory of games of strategy

by J.D. Williams (McGraw-Hill, 1954).

I picked up a copy in the 1980s when the library at the IBM labs near Stuttgart was having a clear-out. It’s quite entertaining to read, but I can’t promise it would help with this puzzle.

@Hugh: A copy is also available on the Internet:

https://www.rand.org/content/dam/rand/pubs/commercial_books/2007/RAND_CB113-1.pdf

I am not sure that Game Theory will help here since the difference is caused by two different approaches in applying the strategy.

If, as you suggest, they each apply an non co-operative strategy during the holiday, they will then only find two tours that visit all the islands (I get the same results as you do here). And, of course, they would be very unlikely to visit all the islands twice unless they planned for this in advance.

But if they plan a co-operative optimal route planning strategy in advance, they will then find 36 ‘all islands’ routes.