最長のスタンプラリー・ルートを探せ！（解答）
この問題を最初に聞いたとき，悪名高い難問「巡回セールスマン問題」を連想された読者がおられるかもしれない。これは，セールスマンがいくつかの営業拠点を全部回るときに，移動コストが最小になるような経路を求める問題であり，本パズルの問題とかなり似ている面がある。回る拠点が2～3カ所ならば手計算でも解けるが，4カ所，5カ所と増えるにつれ計算量が飛躍的に増大していく。
ここでは詳しい説明をしないが，巡回セールスマン問題は，「NP完全」であることが知られている問題で，証明はされていないものの計算量が多くなりすぎて，高性能コンピューターを使っても現実的な時間内に計算が終わらないタイプの問題だと信じられている。つまり，数学用語を使って言い換えると，「多項式時間で解ける」とは誰も信じていない問題といってよい。
多項式時間とは,計算量を表す言い方で，n（ここでは拠点の数）が増えると計算量がどのように増えていくかを示す。線形時間ならば2nや3nといった増え方なので，nが大きくても十分に解ける。多項式時間ならばn2やn3のように増えていったりするが，これでも手に負える。一方，2nや3nのように指数関数的に計算量が増えていくと，お手上げとなってしまう。
本パズルは，全観光ポイントを巡り，移動距離が最長になるようなルートを求める問題だから，他の条件がなければ，実質的に巡回セールスマン問題に帰着できる大変な難問になりそうだが，実は多項式時間どころか線形時間で解けるやさしい問題である。問題をやさしくしている条件とは，全観光ポイントが1本の山道の上に一列に並んでいることであり，その山道から外れるルートが存在しないことだ。例えば，最短のルートであれば一番南のポイントから順次北に進むか，その逆コースであることは誰の目にも明らかだ。
しかし，求めるものが最短ルートではなく最長ルートだから，そのことが問題を少し難しくしている。実際に歩き回ってみれば，最長ルートの候補はすぐに見つかるのだが，それより長いルートが存在しないことを証明するのが難題だと感じるかもしれない。それこそ巡回セールスマン問題を難しくしているのとまさに同じ事情なのだが，山道が一本道だということを利用すれば，最長ルートがどういうものにならねばならないかがわかる。
ルートは8つのポイントを1回ずつ巡ればよいのだが，最後のポイントからまた起点のポイントまで戻る周遊ルートを考えた方が，考えやすくなりそうなので，まずはそうすることにしよう。そのような周遊ルートで最長のものはどういうものだろうか？
周遊ルートを考えることで，全部で8！通りあったルートの総数が円順列の7！通りに減るが，それが重要なのではない。隣接する観光ポイント間を最大何回通ることになるか，それが見積もりやすくなるのがツボだ。
例えば，AB間は0.4kmだが，周遊ルートではこの区間を最大何回通れるだろうか？ そこを通るのはAより北のポイントからAに来て，Aより北の別のポイントに進んだときの2回だけだ。それ以外の移動はすべてAより北で行われているのでAB間を通ることはない。同様にGH間の0.6kmの区間も最大2回しか通ることはない。では0.3kmのBC間はどうだろう？ この場合は，観光ポイントを南のA，Bと北のC，D，E，F，G，Hとの2つのグループに分けて考えると，区間BCを通るのは北のグループから南のグループへ進んだ場合とその逆の場合だけだから，周遊ルートでは最大4回しか通ることがないことがわかる。以下同様に考えていくと，隣接する各観光ポイント間を通ることができる最大回数は周遊ルートの場合，南から順に2，4，6，8，6，4，2回だとわかる。よって，周遊ルートは最長でも
2×0.4＋4×0.3＋6×0.6＋8×0.5＋6×0.9＋4×0.5＋2×0.6＝18.2km
を超えないことが証明された。
そして実際にこの最長を達成するルートが存在するのだ。それは簡単で，観光ポイントを南グループのA～Dと北グループのE～Hとに分けて，南グループに属するポイントと北グループに属するポイントとを（どういう順でもよいから）交互に訪問するルートだ。読者は，これで上の最長の周遊が達成されることを確認されたい。
さて，我々の実際の目標は周遊ルートではないので，最終ポイントから起点ポイントに戻る経路が不要だ。そこで起点と終点をどこに定めるかが問題になるが，実はこの問題は簡単に解決される。最長周遊ルートでは0.5kmのDE間を8回通るが，周遊ルートでない限り，観光ポイントを行ったり来たりすることがそもそも全体で7回しかないから，DE間を通る回数は7回に制限されることになる。
よって，すべての観光ポイントを巡る周遊ではないルートは最長でも18.2－0.5＝17.7kmである。実際，起点をDとし，北グループに属する観光ポイントと南グループに属する観光ポイントとを交互に訪問して，Eで終わるルート，またはその逆ルートがこの最長を達成することを確認するのは容易だろう。
上の考え方は，観光ポイント数が偶数の場合に一般に有効だが，最後に観光ポイント数が奇数の場合について述べておこう。この場合に同じ問題を考えると，真ん中の観光ポイントMを起点として，そこから南北のポイントを交互に訪問し，最後にMに一番近い観光ポイントで終わるルート，あるいはその逆ルートが最長になる。そのことの証明は，少しだけ複雑になるが，ほぼ上と同様の議論で可能である。
