fixedpoint.jp




2018/07/14

The right answer of "The Shipman's Puzzle" from "The Canterbury Puzzles"

The Canterbury Puzzles and Other Curious Problems is a great heritage for those who love fascinating brain teasers. These days its whole text is freely available thanks to the Project Gutenberg.

Here we show that the answer described in the book for its 18th puzzle called "Shipman's Puzzle", i.e. 264, is wrong, and provide the right answer: 528. The original publication dated to 1907, so this seems to correct a 111-year-old misinformation.

The following Prolog program defines predicate complete_voyage/1 which generates all the possible complete voyages. We have confirmed it works with SWI-Prolog Version 7.2.3.

shipmans.pl
island(a). % "a" represents the initial island
island(b).
island(c).
island(d).
island(e).

edge(I,J) :- island(I),island(J),I\=J.

course(I-J) :- edge(I,J),sort([I,J],[I,J]).

count_course(N) :- findall(C,course(C),Cs),length(Cs,N).

taken(I,J,X) :- member(I-J,X);member(J-I,X).

voyage(I,[],[I-a]) :- edge(I,a).
voyage(I,[I1-I2|X],[I-I1,I1-I2|X]) :- edge(I,I1),edge(I1,I2),voyage(I1,X,[I1-I2|X]),\+taken(I,I1,[I1-I2|X]).

complete_voyage(X) :- count_course(N),length(X,N),voyage(a,_,X).

answer(N) :- setof(X,complete_voyage(X),Xs),length(Xs,N).

compact([],[]).
compact([_-J|X],[J|Y]) :- compact(X,Y).

print_all_complete_voyage :- forall(complete_voyage(V),
                                    (print(a),
                                     compact(V,X),
                                     forall(member(E,X),print(E)),
                                     nl)).

Our speculation of the reason why the author and many others overlooked the mistake is simple; it is well-known that 264 is the number of Eulerian circuits in \(K_5\), the complete graph with five vertices [1], which is a formal representation of the "CHART of ye MAGDALEN". However, when counting Eulerian circuits, a cyclic permuation of the already-counted one is skipped. For example, the circuit "a -> b -> c -> a -> d -> b -> e -> c -> d -> e -> a" and "a -> d -> b -> e -> c -> d -> e -> a -> b -> c -> a" are regarded as equivalent. On the other hand, the puzzle in problem asks the number of different ways to pass along all courses, thus the above two should be counted separately.

[1] B. D. McKay and R. W. Robinson, Asymptotic enumeration of Eulerian circuits in the complete graph, Combin. Prob. Comput., 7 (1998) 437-449.

#permalink

Archives

2018: Jun / May / Apr / Mar / Feb / Jan

2017: Dec / Nov / Oct / Sep / Aug / Jul / Jun / May / Apr / Mar / Feb / Jan

2016: Dec / Nov / Sep / Aug / Jul / Mar / Feb / Jan

2015: Dec / Oct / Sep / Jul / May / Mar / Feb

2014: Dec / Nov / Oct / Aug / Apr / Mar / Feb / Jan

2013: Dec / Nov / Oct / Sep / Aug / Jun / May / Apr / Mar

2012: Nov / Oct / Sep / Jul / Jun / May / Mar / Feb / Jan

2011: Dec / Nov / Oct / Sep / Jul / Jun / Apr / Mar / Feb / Jan

2010: Dec / Nov / Oct / Sep / Aug / Jul / Jun / May / Apr / Mar / Feb / Jan

2009: Dec / Nov / Oct / Sep / Aug / Jul / Jun / May / Apr / Mar / Feb / Jan

2008: Dec / Nov / Oct / Sep / Aug / Jul / Jun / May / Apr / Mar / Feb / Jan

2007: Dec / Nov / Oct / Sep / Aug / Jul / Jun / May / Apr / Mar / Feb / Jan

2006: Dec / Nov / Oct / Sep


© 2006-2018 fixedpoint.jp